Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p03804 (python)

Fixed submission:
N,M=map(int,input().split())
A=[input() for _ in range(N)]
B=[input() for _ in range(M)]
ans="No"
for i in range(N-M+1):
  for j in range(N-M+1):
    if [a[j:j+M] for a in A[i:i+M]]==B:    
      ans="Yes"
print(ans)

Buggy submission (verdict: Runtime Error):
N,M=map(int,input().split())
A=[input() for _ in range(N)]
B=[input() for _ in range(M)]
ans="No"
for i in range(N-M+1):
  for j in range(len(A[0])-len(B[0])+1):
    t = 0
    for k in range(len(B[0])):
      for l in range(M):
        if A[k+q][l+p] == B[q][p]:
          t += 1
    if t==len(B[0])*M:
      ans="Yes"
      exit()
print(ans)

Buggy submission (verdict: Runtime Error):
N,M=map(int,input().split())
A=[input() for _ in range(N)]
B=[input() for _ in range(M)]
ans="No"
for i in range(N-M+1):
  for j in range(len(A[0])-len(B[0])+1):
    t = 0
    for k in range(len(B[0])):
      for l in range(M):
        if A[k+q][l+p] == B[q][p]:
          t += 1
    if t==len(B[0])*M:
      ans="Yes"
      break
print(ans)
Problem p02659 (python)

Fixed submission:
import math

A, B = input().split()
C = int(B[0:1])
D = int(B[2:])
print(int(A) * C + int(A) * D // 100)

Buggy submission (verdict: Runtime Error):
#include <bits/stdc++.h>
using namespace std;

int main() {
  long long A; cin >> A;
  double B; cin >> B;
  double ans = A * B;
  cout << fixed << setprecision(0);
  cout << floor(ans) << endl;
}
Problem p02682 (python)

Fixed submission:
a,b,c,k = map(int,input().split())
 
if k <= a:
  print(k)
elif a < k and k <= a+b:
  print(a)
else:
  print(a-k+a+b)

Buggy submission (verdict: Runtime Error):
a,b,c,k = map(int,input().split())
 
if k <= a:
  print(a)
elif a < k and k <= a+b:
  print(a)
elif a+b < k and k <= a+b+c
  print(a-k+a+b)

Buggy submission (verdict: Runtime Error):
a,b,c,k = map(int,input().split())

if k <= a:
  print(a)
elif a < k and k <= a+b:
  print(a)
else:
  print(a-k+a+b))
Problem p02688 (python)

Fixed submission:
n,k = map(int,input().split())
a = [i for i in range(n+1)]
d = []
A = []

for j in range(k):
  d.append(int(input()))
  A.append(list(map(int,input().split())))
  
  
for i in A:
  for j in i:
    if j in a:
      a.remove(j)
      
      
print(len(a)-1)

Buggy submission (verdict: Runtime Error):
n,k = map(int,input(),split())
a = [0 for i in range(n)]

for i in range k:
  d = int(input())
  A = list(map(int,input(),split()))
    for j in A:
      a[j-1] += 1
      
print(a.count(0))
Problem p02725 (python)

Fixed submission:
k,n = map(int,input().split())
a = list(map(int,input().split()))
tm = a[0]
a.append(tm)
m = -9878789894545656
 
for i in range(n-1):
  m = max(m,a[i+1]-a[i])
  
m = max(m,a[0]+k-a[n-1])
  
print(k-m)

Buggy submission (verdict: Runtime Error):
k,n = map(int,input(),split())
a = list(map(int,input().split()))
tm = a[0]
a.append(tm)
m = -9878789894545656
 
for i in range(n):
  m = max(m,a[i+1]-a[i])
  
print(k-m)

Buggy submission (verdict: Runtime Error):
k,n = map(int,input(),split())
a = list(map(int,input().split()))
tm = a[0]
a.append(tm)
m = 11414114514
 
for i in range(n):
  m = min(m,a[i+1]-a[i])
  
print(k-m)

Buggy submission (verdict: Runtime Error):
k,n = map(int,input(),split())
a = list(map(int,input().split()))
a.append(a[0])
m = 11414114514
 
for i in range(n):
  m = min(m,a[i+1]-a[i])
  
print(k-m)

Buggy submission (verdict: Runtime Error):
k,n = map(int,input(),split())
a = list(map(int,input().split()))
a += [a[0]]
m = 11414114514

for i in range(n):
  m = min(m,a[i]-a[i+1])
  
print(k-m)
Problem p02726 (python)

Fixed submission:
n,x,y = map(int,input().split())
k = [0]*(n)

for i in range(1,n):
  for j in range(i+1,n+1):
    if i < x and j <= x:
      k[j-i] += 1
    elif i >= y and j > y:
      k[j-i] += 1
    elif x <= i < y and x<j<=y:
      ind = min(j-i,abs((i-x))+abs((y-j))+1)
      k[ind] += 1
    elif i < x and x<j<=y:
      ind = min(j-i,abs((x-i))+abs((y-j))+1)
      k[ind] += 1
    elif x<=i<y and y<j:
      ind = min(j-i,abs((i-x))+1+abs((j-y)))
      k[ind] += 1
    elif i< x and j > y:
      ind = (x-i) + 1 + (j-y)
      k[ind] += 1
      
for i in range(1,n):
  print(k[i])

Buggy submission (verdict: Runtime Error):
n,x,y = map(int,input().split())
k = [0]*(n)

for i in range(1,n):
  for j in range(i+1,n+1):
    ind = abs(x-i) + abs(j-y) + 1
    k[ind] += 1
      
for i in range(1,n):
  print(k[i])
Problem p02759 (python)

Fixed submission:
n = int(input())
print(n//2 + 1 if n%2 != 0 else n//2)

Buggy submission (verdict: Runtime Error):
n,m = map(int,input().split())
s = []
c = []
if m == 0:
  if n==1:
    print(0)
    exit()
  elif n==2:
    print(10)
    exit()
  else:
    print(100)
    exit()


for i in range(m):
  S,C =  map(int,input().split())
  s.append(S)
  c.append(C)
  
num = [1] + [0]*(n-1)
ans = ''
 
for i in range(m):
  if n != 1 and s[i] == 1 and c[i] == 0:
    print(-1)
    exit()
  elif n == 1 and s[i] == 1 and c[i] == 0:
    print(-1)
    exit()
for i in range(m-1):
  for j in range(i+1,m):
    if s[i] == s[j] and c[i] != c[j]:
      print(-1)
      exit()
      
for i in range(m):
  num[s[i]-1] = c[i]
  
for i in range(n):
  ans += str(num[i])
  
print(ans)
Problem p02779 (python)

Fixed submission:
n = int(input())
a = list(map(int,input().split()))
se = set(a)
 
if len(se) == len(a):
  print('YES')
else:
  print('NO')

Buggy submission (verdict: Runtime Error):
n = int(input())
a = list(map(int,input().split()))
se = set(n)

if len(se) == len(a):
  print('YES')
else:
  print('NO')
Problem p02833 (python)

Fixed submission:
import math

n = int(input())
ans = 0
if n== 0:
  print(0)
  exit()
m = math.floor(math.log(n,5))

if n%2 == 1:
  print(0)
else:
  for j in range(1,m+1):
    ans += n//((5**j)*2)
    
    
  print(ans)

Buggy submission (verdict: Runtime Error):
import math

n = int(input())
ans = 0
if n== 0:
  print(0)
  exit()
m = math.floor(math.log(n//2,5))

if n%2 == 1:
  print(0)
else:
  for j in range(1,m+1):
    ans += n//((5**j)*2)
    
    
  print(ans)

Buggy submission (verdict: Runtime Error):
import math

n = int(input())
ans = 0
m = math.floor(math.log(n,5))

if n%2 == 1:
  print(0)
else:
  for j in range(1,m+1):
    ans += n//((5**j)*2)
    
    
  print(ans)
Problem p02847 (python)

Fixed submission:
s =input()
l = ['SUN','MON','TUE','WED','THU','FRI','SAT'] 
 
for i in range(7):
  if l[i] == s:
    print(7-i)

Buggy submission (verdict: Runtime Error):
s = input()
l = ['SUN','MON','TUE','WED','THU','FRI','SAT'] 
 
for i in range(7):
  if l[i] == s
    print(7-i)

Buggy submission (verdict: Runtime Error):
s = input()
l = ['SUN','MON','TUE','WED','THU','FRI','SAT'] 

for i in rangr(7):
  if l[i] ==s
    print(7-i)
Problem p02912 (python)

Fixed submission:
import heapq

n,m = map(int,input().split())
a = list(map(int,input().split()))
a = list(map(lambda x: x*(-1), a))  # 各要素を-1倍することで，最小最大を逆転

heapq.heapify(a)#優先度付きキューに変換

for i in range(m):
  tmp = heapq.heappop(a)
  heapq.heappush(a,(-tmp//2)*(-1))#負の剰余では切り捨て方向が異なってしまうので，いったんプラスにする．
  
print(-sum(a))

Buggy submission (verdict: Runtime Error):
n = int(input())
a = list(map(int,input().split()))
aabs = [i if i>=0 else i*(-1) for i in a]
MIN = min(aabs)
ans = 0
mcount = 0

for i in range(n):
  if a[i] < 0:
    mcount += 1
    
if mcount%2 == 0:
  for i in a:
    ans += abs(i)
    print(ans)
else:
  for i in a:
    ans += abs(i)
  print(ans - 2*MIN)

Buggy submission (verdict: Runtime Error):
import heapq

n,m = map(int,input().split())
a = list(map(int,input().split()))

a = []#数字のリスト
a = list(map(lambda x: x*(-1), a))  # 各要素を-1倍することで，最小最大を逆転

heapq.heapify(a)#優先度付きキューに変換

for i in range(m):
  tmp = heapq.heappop(a)
  heapq.heappush(a,(-tmp//2)*(-1))#負の剰余では切り捨て方向が異なってしまうので，いったんプラスにする．
  
print(-sum(a))

Buggy submission (verdict: Runtime Error):
import bisect 
n,m = map(int,input().split())
a = sorted(list(map(int,input().split())))
b = a[-1]

for i in range(m):
  if int(b/2) >= a[-2]:
    b = int(b/2)
  else:
    bisect.insort(a,b)
    b = a[-1]
    b = int(b/2)

a.append(b)
print(sum(a))

Buggy submission (verdict: Runtime Error):
import bisect 
n,m = map(int,input().split())
a = sorted(list(map(int,input().split())))
 
for i in range(m):
  b = a[-1]
  a.remove(b)
  b = int(b/2)
  for j in range(99*99):
    if b >= a[-1]:
      b = int(b/2)
    else:
      break
  bisect.insort(a,b)
  
print(sum(a))

Buggy submission (verdict: Runtime Error):
inport bisect 
n,m = map(int,input().split())
a = sorted(list(map(int,input().split())))

for i in range(m):
  b = a[-1]
  a.remove(b)
  b = int(b/2)
  bisect.insort_left(a,b)
  
print(sum(a))
Problem p02933 (python)

Fixed submission:
a = int(input())
s = input()
if a >=3200:
  print(s)
else:
  print("red")

Buggy submission (verdict: Runtime Error):
n = int(input())
m = list(map(int,input().split()))
o = []
c  = 0
for i in m:
  o.append(1/m[c])
  c += 1
s = sum(o)
print(1/s)

Buggy submission (verdict: Runtime Error):
n = int(input())
m = list(map(int,input().split()))
o = []
c  = 0
for i in m:
  o.append(1/m[c])
  c += 1
s = sum(o)
print(1/s)

Buggy submission (verdict: Runtime Error):
n = int(input())
m = list(map(int,input().split()))
o = []
for i in m:
  o.append(float(1/m[i]))
p = sum(o) 
print(1/p)

Buggy submission (verdict: Runtime Error):
n = int(input())
m = list(map(int,input().split()))
o = []
for i in m:
  o.append(float(1/a[i]))
p = sum(o) 
print(1/p)
Problem p02951 (python)

Fixed submission:
a,b,c = map(int,input().split())
yoyuu = a-b
nokori = c- yoyuu

if nokori < 0:
  print(0)
else:
  print(nokori)

Buggy submission (verdict: Runtime Error):
n = int(input())
h = list(map(int,input().split()))
submax = 0

for i in range(n-1):
  for j in range(i+1,n):
    if h[i] - h[j] >= 2:
      submax = 1
      break
  if submax == 1:
    break

if submax == 1:
  print("No")
else:
  print("Yes")
Problem p02959 (python)

Fixed submission:
n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = 0

for i in range(n):
  if a[i] >= b[i]:
    c += b[i]
  else:
    c += a[i]
    c += min(a[i+1],b[i]-a[i])
    if a[i+1] >= b[i]-a[i]:
      a[i+1] = a[i+1] - (b[i] - a[i])
    else:
      a[i+1] = 0
     
print(c)

Buggy submission (verdict: Runtime Error):
n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = 0

for i in range(n):
  c += min(a[i],b[i])
  tmp = min(a[i+1],b[i]-min(a[i],b[i]))
  c += tmp
  if tmp == a[i+1]:
    del a[i+1]
    a.insert(i+1,0)
  else:
    del a[i+1]
    a.insert(i+1,a[i+1]+a[i]-b[i])

print(c)
Problem p03012 (python)

Fixed submission:
n = int(input())
w = list(map(int,input().split()))
a=0
b=0
li = []
for i in range(1,n):
  for j in range(1,i+1):
    a += w[j-1]
  for k in range(i+1,n+1):
    b += w[k-1]
  li.append(abs(a-b))
  a = 0
  b = 0
  
print(min(li))

Buggy submission (verdict: Runtime Error):
n = int(input())
w = list(map(int,input().split()))
a=0
b=0
li = []
for i in range(1,n):
  for j in range(1,i+1):
    a += w[j-1]
  for k in range(i+1,n+1):
    b += w[k]
  li.append(abs(a-b))
  a = 0
  b = 0
  
print(min(li))
Problem p03041 (python)

Fixed submission:
n,k = map(int,input().split())
s = list(input())
ans = ''

if s[k-1] == 'A':
  s[k-1] = 'a'
elif s[k-1] == 'B':
  s[k-1] = 'b'
else:
  s[k-1] = 'c'
  
for i in s:
  ans += i
  
print(ans)

Buggy submission (verdict: Runtime Error):
lst = list(input())
lst1 = []
lst1.append(lst[0]+lst[1])
lst1.append(lst[2]+lst[3])

if (int(lst1[0]) >=13 and int(lst1[1]) >=13) or (int(lst1[0]) >=13 and lst1[1] =="00") or (lst1[0] =="00" and int(lst1[1]) >=13) or (lst1[0] =="00" and lst1[1] == "00"):
  print("NA")
  
elif (0<int(lst1[0])<=12 and 0<int(lst1[1])<=12):
      print("AMBIGUOUS")
      
elif 0<int(lst1[0]) <=12 and int(lst1[1])>=13:
      print("MMYY")
elif 0<int(lst1[1])<=12 and int(lst1[0])>=13:
      print("YYMM")

Buggy submission (verdict: Runtime Error):
lst = list(input())
lst1 = []
lst1.append(lst[0]+lst[1])
lst1.append(lst[2]+lst[3])

if (int(lst1[0]) >=13 and int(lst1[1]) >=13) or (int(lst1[0]) >=13 and lst1[1] =="00") or (lst1[0] =="00" and lst1[1] >=13):
  print("NA")
  
elif (0<int(lst1[0])<=12 and 0<int(lst1[1])<=12):
      print("AMBIGUOUS")
      
elif 0<int(lst1[0]) <=12 and int(lst1[1])>=13:
      print("MMYY")
elif 0<int(lst1[1])<=12 and int(lst1[0])>=13:
      print("YYMM")
Problem p03042 (python)

Fixed submission:
lst = list(input())
lst1 = []
lst1.append(lst[0]+lst[1])
lst1.append(lst[2]+lst[3])

if (int(lst1[0]) >=13 and int(lst1[1]) >=13) or (int(lst1[0]) >=13 and lst1[1] =="00") or (lst1[0] =="00" and int(lst1[1]) >=13) or (lst1[0] =="00" and lst1[1] == "00"):
  print("NA")
  
elif (0<int(lst1[0])<=12 and 0<int(lst1[1])<=12):
      print("AMBIGUOUS")
      
elif 0<int(lst1[0]) <=12:
      print("MMYY")
elif 0<int(lst1[1])<=12:
      print("YYMM")

Buggy submission (verdict: Runtime Error):
lst = list(input())
lst1 = []
lst1.append(lst[0]+lst[1])
lst1.append(lst[2]+lst[3])

if (int(lst1[0]) >=13 and int(lst1[1]) >=13) or (int(lst1[0]) >=13 and lst1[1] =="00") or (lst1[0] =="00" and lst1[1] >=13):
  print("NA")
  
elif (0<int(lst1[0])<=12 and 0<int(lst1[1])<=12):
      print("AMBIGUOUS")
      
elif 0<int(lst1[0]) <=12 and int(lst1[1])>=13:
      print("MMYY")
elif 0<int(lst1[1])<=12 and int(lst1[0])>=13:
      print("YYMM")

Buggy submission (verdict: Runtime Error):
lst = list(input())
lst1 = []
lst1.append(lst[0]+lst[1])
lst1.append(lst[2]+lst[3])

if (int(lst1[0]) >=13 and int(lst1[1]) >=13) or (int(lst1[0]) >=13 and lst1[1] =="00") or (lst1[0] =="00" and lst1[1] >=13):
  print("NA")
  
elif (0<int(lst1[0])<=12 and 0<int(lst1[1])<=12):
      print("AMBIGUOUS")
      
elif 0<lst1[0] <=12 and int(lst1[1])>=13:
      print("MMYY")
elif 0<lst1[1]<=12 and int(lst1[0])>=13:
      print("YYMM")

Buggy submission (verdict: Runtime Error):
lst = list(input())
lst1 = []
lst1.append(lst[0]+lst[1])
lst1.append(lst[2]+lst[3])

if (int(lst1[0]) >=13 and int(lst1[1]) >=13) or (int(lst1[0]) >=13 and lst1[1] =="00") or (lst1[0] =="00" and lst1[1] >=13):
  print("NA")
  
elif (0<int(lst1[0])<=12 and 0<int(lst1[1])<=12):
      print("AMBIGUOUS")
      
elif 0<lst1[0] <=12:
      print("MMYY")
elif 0<lst1[1]<=12:
      print("YYMM")
Problem p03135 (python)

Fixed submission:
t,x = map(int,input().split())
print(float(t/x))

Buggy submission (verdict: Runtime Error):
n = int(input())
l = sorted(list(map(int,input().split())))
s = 0

for i in l[:-1]:
  s += i
  
if l[0] < s:
  print("Yes")
else:
  print("No")
Problem p03137 (python)

Fixed submission:
n,m = map(int,input().split())
x = list(map(int,input().split()))
x.sort()
if m <= n:
  print(0)
  exit()

l = []

for i in range(len(x)-1):
  l.append(x[i+1] - x[i])
  
l.sort(reverse = True)

for i in range(n-1):
  l[i] = 0
  
print(sum(l))

Buggy submission (verdict: Runtime Error):
n,m = map(int,input().split())
x = list(map(int,input().split()))
x.sort()
if m <= n:
  print(0)
  exit()

if n%2 == 0:
  cutl = n//2 - 1
  cutr = len(x)+1-(n//2)
else:
  cutl = (n//2)
  cutr = len(x)-1+(n//2)

lis = x[cutl:cutr]
l = []

for i in range(len(lis)-1):
  l.append(abs(lis[i] - lis[i+1]))

print(lis[-1] - lis[0] -max(l))

Buggy submission (verdict: Runtime Error):
n,m = map(int,input().split())
x = list(map(int,input().split()))
x.sort()
if m == 1:
  print(0)
  exit()

if n%2 == 0:
  cutl = n//2 - 1
  cutr = len(x)+1-(n//2)
else:
  cutl = (n//2)
  cutr = len(x)-1+(n//2)

lis = x[cutl:cutr]
l = []

for i in range(len(lis)-1):
  l.append(abs(lis[i] - lis[i+1]))

print(lis[-1] - lis[0] -max(l))
Problem p03242 (python)

Fixed submission:
a = input()
print(a.replace("1","x").replace("9","1").replace("x","9"))

Buggy submission (verdict: Runtime Error):
a = list(input())
b = []
for i in a:
  if i = "1":
    b.append("9")
  else:
    b.append("1")
print("".join(b))

Buggy submission (verdict: Runtime Error):
a =input()
print(a.replace("1","x"),replace("9","1").replace("x","9"))

Buggy submission (verdict: Runtime Error):
a = int(input())
print(a.replace(1,x).replace(9,1).replace(x,9))

Buggy submission (verdict: Runtime Error):
a = int(input())
print(a.replace(1,x),replace(9,1).replace(x,9))
Problem p03272 (python)

Fixed submission:
n,i = map(int,input().split())
print(n-i+1)

Buggy submission (verdict: Runtime Error):
n,i = map(int(),input().split())
print(n-i+1)
Problem p03307 (python)

Fixed submission:
N = int(input())
if N%2 == 0:
  print(N)
else:
  print(2*N)

Buggy submission (verdict: Runtime Error):
N = int(input())
if N%2 == 0:
  print(N)
else:
  print(2N)
Problem p03327 (python)

Fixed submission:
n = int(input())
if 1 <= n <= 999:
  print("ABC")
else:
  print("ABD")

Buggy submission (verdict: Runtime Error):
n = int(input())
if 1 <= n <= 999:
  print(ABC)
else:
  print(ABD)

Buggy submission (verdict: Runtime Error):
n = input()
if 1 <= n <= 999:
  print(ABC)
else:
  print(ABD)

Buggy submission (verdict: Runtime Error):
n = input()
if 1 <= n <= 999:
  print(n)
else:
  print(n-999)
Problem p03835 (python)

Fixed submission:
k,s = map(int,input().split())
a = 0
for x in range(k+1):
  for y in range(k+1):
      if s-(x+y) <= k and s-(x+y) >= 0:
        a += 1
        
print(a)

Buggy submission (verdict: Runtime Error):
k,s = map(int(),input().split())
a = 0
for x in range(k+1):
  for y in range(k+1):
    for z in range(k+1):
      if x+y+z == s:
        a += 1
        
print(a)
Problem p02685 (python)

Fixed submission:
N, M, K = list(map(int, input().split()))

mod = 998244353


fac = [0] * (N+1)
fac[0] = 1
fac[1] = 1
for i in range(2, N+1):
    fac[i] = (fac[i-1] * i) % mod


def comb(a, b, p):
    if a < 0 or b < 0:
        return 0
    elif a < b:
        return 0
    c = fac[a]
    c *= pow(fac[b], p - 2, p)
    c *= pow(fac[a-b], p - 2, p)
    return c % p


ans = 0
ans += M * pow(M-1, N-1, mod)
ans %= mod

for k in range(1, K+1):
    ans += comb(N-1, k, mod) * M * pow(M-1, N-1-k, mod)
    ans %= mod

print(ans)

Buggy submission (verdict: Runtime Error):
N, M, K = list(map(int, input().split()))

mod = 998244353


def factorial(x, p):
    a = 1
    for i in range(1, x + 1):
        a *= i
        a %= p
    return a


def comb(a, b, p):
    if a < 0 or b < 0:
        return 0
    elif a < b:
        return 0
    c = 1
    c *= factorial(a, p)
    c *= pow(factorial(b, p), p - 2, p)
    c *= pow(factorial(a - b, p), p - 2, p)
    return c % p


ans = 0
ans += M * pow(M-1, N-1)
ans %= mod

for k in range(1, K+1):
    ans += comb(N-1, k, mod) * (M * pow(M-k, N-1-k)

print(ans % mod)

Buggy submission (verdict: Runtime Error):
N, M, K = list(map(int, input().split()))

mod = 998244353


def factorial(x, p):
    a = 1
    for i in range(1, x + 1):
        a *= i
        a %= p
    return a


def comb(a, b, p):
    if a < 0 or b < 0:
        return 0
    elif a < b:
        return 0
    c = 1
    c *= factorial(a, p)
    c *= pow(factorial(b, p), p - 2, p)
    c *= pow(factorial(a - b, p), p - 2, p)
    return c % p


ans = 0
ans += M * pow(M-1, N-1)
ans %= mod

for k in range(1, K+1):
    ans += comb(N-1, k, mod) * (M * pow(M-k, N-1-k)

print(ans % mod)
Problem p03013 (python)

Fixed submission:
import sys

N, M = list(map(int, input().split()))
A = set()

sys.setrecursionlimit(N * 10)

Z = 1000000007

for _ in range(M):
    a = int(input())
    A.add(a)


B = [-1] * (N + 1)
B[0] = 0


def d(n):
    if n < 1:
        return 0
    if n in A:
        B[n] = 0
        return 0

    if B[n] != -1:
        return B[n]
    if n == 1:
        return 1
    if n == 2:
        if 1 in A:
            return 1
        return 2

    if n - 1 in A and n - 2 in A:
        return 0

    if n - 1 in A:
        B[n] = d(n-2)
        return B[n]

    if n - 2 in A:
        B[n] = d(n-1)
        return B[n]

    B[n] = (d(n-2) + d(n-1)) % Z
    return B[n]


print(d(N))

Buggy submission (verdict: Runtime Error):
import sys

N, M = list(map(int, input().split()))
A = set()

sys.setrecursionlimit(N * 2)

Z = 1000000007

for _ in range(M):
    a = int(input())
    A.add(a)


B = [-1] * (N + 1)


def d(n):
    if n < 1:
        return 0
    if n in A:
        B[n] = 0
        return 0

    if B[n] != -1:
        return B[n]
    if n == 1:
        return 1
    if n == 2:
        if 1 in A:
            return 1
        return 2

    if n - 1 in A and n - 2 in A:
        return 0

    if n - 1 in A:
        B[n] = d(n-2)
        return B[n]

    if n - 2 in A:
        B[n] = d(n-1)
        return B[n]

    B[n] = (d(n-2) + d(n-1)) % Z
    return B[n]


print(d(N))

Buggy submission (verdict: Runtime Error):
import sys

N, M = list(map(int, input().split()))
A = set()

sys.setrecursionlimit(N * 2)

Z = 1000000007

for _ in range(M):
    a = int(input())
    A.add(a)


B = [-1] * (N + 1)


def d(n):
    if n in A:
        B[n] = 0
        return 0

    if B[n] != -1:
        return B[n]

    if n == 1:
        return 1
    if n == 2:
        if 1 in A:
            return 1
        return 2

    if n - 1 in A and n - 2 in A:
        return 0

    if n - 1 in A:
        B[n] = d(n-2)
        return B[n]

    if n - 2 in A:
        B[n] = d(n-1)
        return B[n]

    B[n] = (d(n-2) + d(n-1)) % Z
    return B[n]


print(d(N))

Buggy submission (verdict: Runtime Error):
import sys

N, M = list(map(int, input().split()))
A = set()

sys.setrecursionlimit(N * 2)

Z = 1000000007

for _ in range(M):
    a = int(input())
    A.add(a)


B = [-1] * (N + 1)


def d(n):
    if B[n] != -1:
        return B[n]

    if n in A or n < 0:
        return 0
    if n <= 2:
        return n

    B[n] = (d(n-1) + d(n-2)) % Z
    return B[n]


print(d(N))
Problem p03045 (python)

Fixed submission:
N, M = list(map(int, input().split()))


class UnionFind():
    def __init__(self, n):
        self.rank = [1 for _ in range(n)]
        self.parent = [i for i in range(n)]

    def union(self, i, j):
        i = self.root(i)
        j = self.root(j)
        if i == j:
            return
        if self.rank[i] < self.rank[j]:
            self.parent[i] = j
        else:
            if self.rank[i] == self.rank[j]:
                self.rank[j] += 1
            self.parent[j] = i

    def same(self, i, j):
        return self.root(i) == self.root(j)

    def root(self, i):
        if self.parent[i] != i:
            self.parent[i] = self.root(self.parent[i])
        return self.parent[i]


uf = UnionFind(N)

for _ in range(M):
    X, Y, _ = list(map(int, input().split()))
    uf.union(X-1, Y-1)

ans = 0

for i in range(N):
    if uf.parent[i] == i:
        ans += 1

print(ans)

Buggy submission (verdict: Runtime Error):
N, M = list(map(int, input().split()))


class UnionFind():
    def __init__(self, n):
        self.rank = [1 for _ in range(n)]
        self.parent = [i for i in range(n)]

    def union(self, i, j):
        i = self.root(i)
        j = self.root(j)
        if i == j:
            return
        if self.rank[i] < self.rank[j]:
            self.parent[i] = j
        else:
            if self.rank[i] == self.rank[j]:
                self.rank[j] += 1
            self.parent[j] = i

    def same(self, i, j):
        return self.root(i) == self.root(j)

    def root(self, i):
        if self.parent[i] != i:
            self.parent[i] = self.root(self.parent[i])
        return self.parent[i]


uf = UnionFind(N)

for _ in range(M):
    X, Y, _ = list(map(int, input().split()))
    uf.union(X-1, Y-1)

ans = 0

for i in range(N):
    if uf.root(i) == i:
        ans += 1

print(ans)

Buggy submission (verdict: Runtime Error):
N, M = list(map(int, input().split()))
XYZ = []
for _ in range(M):
    XYZ.append(list(map(int, input().split())))


class UnionFind():
    def __init__(self, n):
        self.rank = [1 for _ in range(n)]
        self.parent = [i for i in range(n)]

    def union(self, i, j):
        i = self.root(i)
        j = self.root(j)
        if i == j:
            return
        if self.rank[i] < self.rank[j]:
            self.parent[i] = j
        else:
            if self.rank[i] == self.rank[j]:
                self.rank[j] += 1
            self.parent[j] = i

    def same(self, i, j):
        return self.root(i) == self.root(j)

    def root(self, i):
        if self.parent[i] != i:
            self.parent[i] = self.root(self.parent[i])
        return self.parent[i]


uf = UnionFind(N)

for xyz in XYZ:
    X, Y, Z = xyz
    uf.union(X-1, Y-1)

ans = 0

for i in range(N):
    if uf.root(i) == i:
        ans += 1

print(ans)