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

Fixed submission:
a,b=map(int,input().split())
lista=[]
import fractions
import math
gcd=fractions.gcd(a,b)

for i in range(1,int(gcd**0.5)+1): 
    if gcd% i == 0: 
        lista.append(i)
        if i!=int(gcd/i):
            lista.append(int(gcd/i))

#print(lista)
lista=lista[1:]
lista.sort()
listb=[]
for i in range(len(lista)):
    flag = True
    for j in range(len(listb)):
        if lista[i]%listb[j]==0:
            flag = False    
    if flag==True:
        listb.append(lista[i])

print(len(listb)+1)

Buggy submission (verdict: Runtime Error):
a,b=map(int,input().split())
lista=[]
import fractions
gcd=fractions.gcd(a,b)

for i in range(2,gcd/2+1): 
    if gcd% i == 0: 
        lista.append(i)

#print(lista)
listb=[]
for i in range(len(lista)):
    flag = True
    for j in range(len(listb)):
        if lista[i]%listb[j]==0:
            flag = False    
    if flag==True:
        listb.append(lista[i])

print(len(listb)+1)

Buggy submission (verdict: Runtime Error):
a,b=map(int,input().split())
lista=[]
import fractions
gcd=fractions.gcd(a,b)

for i in range(2,(gcd+1)/2): 
    if gcd% i == 0: 
        lista.append(i)

#print(lista)
listb=[]
for i in range(len(lista)):
    flag = True
    for j in range(len(listb)):
        if lista[i]%listb[j]==0:
            flag = False    
    if flag==True:
        listb.append(lista[i])

print(len(listb)+1)

Buggy submission (verdict: Runtime Error):
a,b=map(int,input().split())
lista=[]
import fractions
gcd=fractions.gcd(a,b)

for i in range(2,gcd+1):
    if a% i == 0 and b % i == 0: 
        lista.append(i)
        
listb=[]
for i in range(len(lista)):   
    if pow(2, lista[i]-1, lista[i]) == 1:
            listb.append(lista[i])
#print(listb)   

if lista[0]==2:   
    print(len(listb)+2)

else:
    print(len(listb)+1)

Buggy submission (verdict: Runtime Error):
a,b=map(int,input().split())
lista=[]
import fractions
gcd=fractions.gcd(a,b)

for i in range(2,gcd+1):
    if a% i == 0 and b % i == 0: 
        lista.append(i)
        
listb=[]
for i in range(len(lista)):   
    if pow(2, lista[i]-1, lista[i]) == 1:
            listb.append(lista[i])
#print(listb)   

if lista[1]==2:   
print(len(listb)+2)

else:
    print(len(listb)+1)

Buggy submission (verdict: Runtime Error):
a,b=map(int,input().split())
lista=[]
import fractions
gcd=fractions.gcd(a,b)

for i in range(2,gcd+1):
    if a% i == 0 and b % i == 0: 
        lista.append(i)
        
listb=[]
for i in range(len(lista)):   
    if pow(2, lista[i]-1, lista[i]) == 1:
            listb.append(lista[i])
print(listb)   

if lista[1]=2:   
print(len(listb)+2)

else:
    print(len(listb)+1)
Problem p02995 (python)

Fixed submission:
a,b,c,d=map(int,input().split())
ans1=b//c-(a-1)//c
ans2=b//d-(a-1)//d

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y) 
    
e=(c*d)//gcd(c,d)
ans3=b//e-(a-1)//e

ans=b-a+1-ans1-ans2+ans3

print(ans)

Buggy submission (verdict: Runtime Error):
a,b,c,d=map(int,input().split())
ans1=b//c-(a-1)//c
ans2=b//d-(a-1)//d

import math
e=(c*d)//math.gcd(c,d)
ans3=b//e-(a-1)//e

ans=b-a+1-ans1-ans2+ans3

print(ans)
Problem p02999 (python)

Fixed submission:
X,A=map(int,input().split())
if X<A :
    print(0)
else:
    print(10)

Buggy submission (verdict: Runtime Error):
X,A=map(int,input().split())
if x<A :
    print(0)
else:
    print(10)
Problem p03000 (python)

Fixed submission:
n,x=map(int,input().split())
List = [int(i) for i in input().split()]
d=0
j=1
for i in range(n):
    d=d+List[i]
    if d<=x :
        j+=1
print(j)

Buggy submission (verdict: Runtime Error):
n,x=map(int,input().split())
List = [int(i) for i in input().split()]
d=0
i=0
for i in range(n)
if d<x :
    d=d+List[i]
else :
    print(i)
Problem p03061 (python)

Fixed submission:
n=int(input())
lista = [int(i) for i in input().split()]

import fractions
import copy

listb=[]
listc=[]
ansb= lista[0]

for i in range(1,n-1):
	ansb=fractions.gcd(ansb,lista[i])
#	print(ansb)
	listb.append(ansb)

#print(int(max(list_ans)))
ansc= lista[n-1]

for i in range(n-2,0,-1):
	ansc=fractions.gcd(ansc,lista[i])
#	print(ansc)
	listc.append(ansc)


list_b=[lista[0]]
listb=[1]+list_b+listb
list_c=[lista[n-1]]
listc=list(reversed(listc))+list_c+[1]
#print(listb)
#print(listc)

ans=0
list_ans=[listc[0],listb[n-1]]
for i in range(1,n-1):
	ans=fractions.gcd(listb[i],listc[i])
	list_ans.append(ans)
	
ansans=max(list_ans)

if n==2:
	ansans=max(lista[0],lista[1])
	
print(ansans)

Buggy submission (verdict: Runtime Error):
n=int(input())
lista = [int(i) for i in input().split()]

import fractions

list_ans=[]

for i in range(n):
	listb=lista.copy()
	listb.pop(i)
#	print(listb)

	ans= listb[0]

	for i in range(1,n-1):
		ans=fractions.gcd(ans,listb[i])
#	print(ans)
	list_ans.append(ans)

print(int(max(list_ans)))

Buggy submission (verdict: Runtime Error):
n=int(input())
lista = [int(i) for i in input().split()]

import fractions

list_ans=[]

for i in range(n):
	listb=lista.copy()
	listb.pop(i)
#	print(listb)

	ans= listb[0]

	for i in range(1,n-1):
		ans=fractions.gcd(ans,listb[i])
#	print(ans)
	list_ans.append(ans)

print(max(list_ans))

Buggy submission (verdict: Runtime Error):
n=int(input())
lista = [int(i) for i in input().split()]

import fractions

list_ans=[]

for i in range(n):
	listb=lista.copy()
	listb.pop(i)
#	print(listb)

	ans= listb[0]

	for i in range(1,n-1):
		ans=fractions.gcd(ans,listb[i])
#	print(ans)
	list_ans.append(ans)
	print(max(list_ans))
Problem p03086 (python)

Fixed submission:
s=str(input())

lens=len(s)
ans=0
list=[]

for i in range(lens):
	if (s[i]=='A')|(s[i]=='T')|(s[i]=='C')|(s[i]=='G'):
		ans=ans+1
	else:
		list.append(ans)
		ans=0
list.append(ans)
print(max(list))

Buggy submission (verdict: Runtime Error):
s=str(input())

lens=len(s)
ans=0
list=[]

for i in range(lens):
	if (s[i]=='A')|(s[i]=='T')|(s[i]=='C')|(s[i]=='G'):
		ans=ans+1
	else:
		list.append(ans)
		ans=0

#print(list)
print(max(list))
Problem p03651 (python)

Fixed submission:
n,k=map(int,input().split())
lista = [int(i) for i in input().split()]
import functools
#from functools import reduce
import fractions
#from fractions import gcd

gcda=functools.reduce(fractions.gcd, lista)

if k>max(lista):
    print("IMPOSSIBLE")
else:
    if k%gcda==0:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")

Buggy submission (verdict: Runtime Error):
n,k=map(int,input().split())
lista = [int(i) for i in input().split()]
import functools
#from functools import reduce
import math
#from math import gcd

gcda=functools.reduce(math.gcd, lista)

if k>max(lista):
    print("IMPOSSIBLE")
else:
    if k%gcda==0:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")

Buggy submission (verdict: Runtime Error):
n,k=map(int,input().split())
lista = [int(i) for i in input().split()]
from functools import reduce
from math import gcd

gcda=functools.reduce(gcd, lista)

if k>max(lista):
    print("IMPOSSIBLE")
else:
    if k%gcda==0:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")
Problem p03994 (python)

Fixed submission:
s=str(input())
k=int(input())

lista=[]
for i in range(26):
	lista.append(chr(ord('a') + i))
	
#print(lista)

s_list=list(s)
len_s=len(list(s))
temp1=k
temp2=0
for i in range(len_s):
	if (123-ord(s_list[i])<=temp1)and (s_list[i] != 'a'):
		temp1=temp1-(123-ord(s_list[i]))
		s_list[i]="a"
if temp1!=0:
#	print(temp1)
	temp2=temp1%26+ord(s_list[-1])
	if temp2>122:
		temp2=temp2-122+96
	s_list[-1]=chr(temp2)
#print(temp2)
#print(str(s_list))

for i in range(len(s_list)):
	print(s_list[i],end="")
print()

Buggy submission (verdict: Runtime Error):
s=str(input())
k=int(input())

lista=[]
for i in range(26):
	lista.append(chr(ord('a') + i))
	
#print(lista)

s_list=list(s)
len_s=len(list(s))
temp1=k
temp2=0
for i in range(len_s):
	if (123-ord(s_list[i])<=temp1):
		temp1=temp1-(123-ord(s_list[i]))
		s_list[i]="a"
if temp1!=0:
#	print(temp1)
	temp2=temp1%26+ord(s_list[-1])
	if temp2>122:
		temp2=temp2-122+96
	s_list[-1]=chr(temp2)
#print(temp2)
#print(str(s_list))

for i in range(len(s_list)):
	print(s_list[i],end="")
print(\n)
Problem p02993 (python)

Fixed submission:
S = input()

flg = False
for i in range(3):
    if S[i] == S[i+1]:
        flg =True

print('Bad' if flg else 'Good')

Buggy submission (verdict: Runtime Error):
import fractions
a, b, c, d = map(int, input().split())
 
def wareruzu(x):
    start_a = a if a % x == 0 else a - (a % x) + x
    end_b = b - (b % x)
    m = end_b - start_a
    return int(m / x) + 1
 
all_n = b - a + 1
print(all_n - wareruzu(c) - wareruzu(d) + wareruzu((c*d) / fractions.gcd(c,d)))
Problem p02995 (python)

Fixed submission:
import fractions
a, b, c, d = map(int, input().split())
 
def wareruzu(x):
    if b < x:
        return 0
    if b == x:
        return 1
    start_a = a if a % x == 0 else a - (a % x) + x
    end_b = b - (b % x) # bより小さい最大の値。
    m = end_b - start_a
    if m < 0:
        return 0
    return int(m // x) + 1
 
all_n = b - a + 1
print(all_n - wareruzu(c) - wareruzu(d) + wareruzu((c*d) // fractions.gcd(c,d)))

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

def wareruzu(x):
    if b < x:
        return 0
    start_a = a if a % x == 0 else a - (a % x) + x
    end_b = b - (b % x)
    m = end_b - start_a
    return int(m / x) + 1

all_n = b - a + 1
print(all_n - wareruzu(c) - wareruzu(d) + wareruzu((c*d) / math.gcd(c,d)))
Problem p02996 (python)

Fixed submission:
from operator import itemgetter
N = int(input())

lst =[]
for i in range(N):
    lst.append(list(map(int, input().split())))

lst.sort(key=itemgetter(1))

now = 0
flg = True
for item in lst:
    now += item[0]
    if now > item[1]:
        flg = False
        break

print('Yes' if flg else 'No')

Buggy submission (verdict: Runtime Error):
import fractions
a, b, c, d = map(int, input().split())
 
def wareruzu(x):
    if b < x:
        return 0
    if b == x:
        return 1
    start_a = a if a % x == 0 else a - (a % x) + x
    end_b = b - (b % x)
    m = end_b - start_a
    return int(m / x) + 1
 
all_n = b - a + 1
print(all_n - wareruzu(c) - wareruzu(d) + wareruzu((c*d) / fractions.gcd(c,d)))
Problem p02886 (python)

Fixed submission:
import itertools
import numpy as np

N = int(input())
lst = np.array(list(map(int,input().split())))
lst2 = np.array(list(itertools.combinations(lst,2)))
lst3 =[]

for i in range(len(lst2)):
               dot = np.dot(lst2[i][0],lst2[i][1])
               lst3.append(dot)

print(sum(lst3))

Buggy submission (verdict: Runtime Error):
import itertools
import numpy as np

N = int(input())
lst = np.array(list(map(int,input().split())))

lst2 = np.array(list(itertools.combinations(lst,2)))
lst3 =[]
for i in range(len(lst2):
               dot = np.dot(lst2[i][0],lst2[i][1])
               lst3.append(dot)

print(sum(lst3))
Problem p02957 (python)

Fixed submission:
A,B = map(int,input().split())
 
K=(A+B)/2
 
def is_integer_num(n):
    if isinstance(n, int):
        return True
    if isinstance(n, float):
        return n.is_integer()
    return False
 
if is_integer_num(K)==False:
  print("IMPOSSIBLE")
else:
  print(int(K))

Buggy submission (verdict: Runtime Error):
A,B = map(int,input().split())
 
K=(A+B)/2
 
def is_integer_num(n):
    if isinstance(n, int):
        return True
    if isinstance(n, float):
        return n.is_integer()
    return False
 
if is_integer_num(K)==False:
  print(IMPOSSIBLE)
else:
  print(K)

Buggy submission (verdict: Runtime Error):
A=int(input())
B=int(input())

K=(A+B)/2

def is_integer_num(n):
    if isinstance(n, int):
        return True
    if isinstance(n, float):
        return n.is_integer()
    return False

if is_integer_num(K)==False:
  print(IMPOSSIBLE)
else:
  print(K)
Problem p02993 (python)

Fixed submission:
w=input()

cnt=0
for i in w:
    if cnt+1 < len(w):
        if w[cnt] == w[cnt+1]:
            print("Bad")
            exit()
    cnt += 1

print("Good")

Buggy submission (verdict: Runtime Error):
w=input()

cnt=0
for i in w:
  if w[cnt] == w[cnt+1]:
    print("Bad")
  else:
    print("Good")
  cnt += 1
Problem p03238 (python)

Fixed submission:
N = int(input())
if N == 1:
  print("Hello World")
else:
  A = int(input())
  B = int(input())
  print(A+B)

Buggy submission (verdict: Runtime Error):
L = []
N = L.append(int(input))
if len(N) == 1:
  print("Hello world")
  
else:
  print(N[2]+N[3])
Problem p02922 (python)

Fixed submission:
a,b = map(int, input().split())
n = 1
if b == 1:
    print(0)
else:
    while a*n-(n-1) < b:
        n += 1
    print(n)

Buggy submission (verdict: Runtime Error):
n = 1
if b == 1:
    print(0)
else:
    while a*n-(n-1) < b:
        n += 1
    print(n)
Problem p02843 (python)

Fixed submission:
X = int(input())

num = X // 100

if num * 100 <= X <= num * 105:
  print(1)
else:
  print(0)

Buggy submission (verdict: Runtime Error):
import math
X = int(input())

def dfs(price):
  if price > X:
    return 0
  ret = 1 if price == X else 0
  for pri in range(100, 106):
    ret += dfs(price+pri)
  return ret

if dfs(0) > 0:
  print(1)
else:
  print(0)
Problem p02909 (python)

Fixed submission:
S = input()
ans_list = ["Sunny", "Cloudy", "Rainy", "Sunny"]
for i in range(3):
  if S == ans_list[i]:
    ans = ans_list[i+1]

print(ans)

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

while M != 0:
  ind = A.index(max(A))
  A[ind] = A[ind] // 2
  M -= 1
  
print(sum(A))

Buggy submission (verdict: Runtime Error):
S = input()
ans_list = ["Sunny", "Cloudy", "Rainy", "Sunny"]
for i in range(2):
  if S == ans_list[i]:
    ans = ans_list[i+1]

print(ans)
Problem p03212 (python)

Fixed submission:
N = int(input())
 
def dfs(s):
  if int(s) > N: 
    return 0
  ret = 1 if all(s.count(c) > 0 for c in '753') else 0
  for c in '753':
    ret += dfs(s+c)
  return ret
 
print(dfs('0'))

Buggy submission (verdict: Runtime Error):
N = int(input())

def dfs(s):
  if int(s) > N: #sがNより大きくなったら再帰終了
    return 0
  ret = 1 if all(s.count(c) > 0 for c in '753') else 0　#sが七五三数ならretに1を入れる
  for c in '753':
    ret += dfs(s+c)
  return ret

print(dfs('0'))　#s='0'からスタート

Buggy submission (verdict: Runtime Error):
N = input()
N_ = len(N)
A = N_ * N_ - 1 * N_ - 2

if int(N) < 357:
  print(0)
elif int(N[0]) < 2:
  A = N_ - 1 * N_ - 2 * N_ - 3
elif int(N[0]) == 3 or int(N[0]) == 4:
  A = N_ - 1 * N_ - 2
elif int(N[0]) == 5 int(N[0]) == 6:
  A = 2 * N_ -1 * N_ -2
elif int(N[0]) >= 7:
  A = N_ * N_ - 1 * N_ - 2
  

print(A)
Problem p03861 (python)

Fixed submission:
a, b, x = map(int, input().split())

#aの商と余り、bの商を求める
qa = a // x
qb = b // x
ra = a % x
#bの商からaの商を引く
ans = qb - qa

#ここまでの操作で、a以外の値の内、xで割り切れる値の数がansに入っているため、
#aが割り切れるかどうかで条件分岐させる
if ra == 0:
  print(ans+1)
else:
  print(ans)

Buggy submission (verdict: Runtime Error):
a, b, x = map(int, input().split())
#aからbまでをliに格納
li = list(range(a, b+1))
ans = 0

#liの要素数だけfor文を回す
for i in range(len(li)):
  #li[i]がxで割り切れる時
  if li[i] % x == 0:
    #ansに1を追加
    ans += 1
    
print(ans)
Problem p02789 (python)

Fixed submission:
n, m = list(map(int, input().split()))
if n==m:
    print("Yes")
else:
    print("No")

Buggy submission (verdict: Runtime Error):
    n, m = list(map(int, input().split()))
    if n==m:
        print("Yes")
    else:
        print("No")
Problem p02789 (python)

Fixed submission:

n, m = input().split()
n = int(n)
m = int(m)

if m == n:
    print('Yes')
else:
    print('No')

Buggy submission (verdict: Runtime Error):

n, m = int(input()).split()

if m == n:
    print('Yes')
else:
    print('No')
Problem p02802 (python)

Fixed submission:
N, M = map(int,input().split())
AC_Set = set()
WA_Dict = {}
WA_SUM = 0
for i in range(M):
    num,result = list(input().split())
    if num in AC_Set:
        continue
    else:
        if result == "AC":
            AC_Set.add(num)
            WA_SUM += WA_Dict.get(num,0)
        else:
            WA_Dict[num] = WA_Dict.get(num,0) + 1

print("{} {}".format(len(AC_Set),WA_SUM))

Buggy submission (verdict: Runtime Error):
N, M = map(int,input().split())
AC_Set = set()
WA_Dict = {}
WA_SUM = 0
for i in range(M):
    num,result = list(input().split())
    if num in AC_Set:
        continue
    else:
        if result == "AC":
            AC_Set.add(num)
            WA_SUM += WA_Dict.get(num)
        else:
            WA_Dict[num] = WA_Dict.get(num,0) + 1

print("{} {}".format(len(AC_Set),WA_SUM))
Problem p02812 (python)

Fixed submission:
n = input()
s = input()
print(s.count("ABC"))

Buggy submission (verdict: Runtime Error):
n = input()
s = input()
print(s.count("ABC")
Problem p02789 (python)

Fixed submission:
n,m = input().split()
N = int(n)
M = int(m)
if N == M:
  print('Yes')
else:
  print('No')

Buggy submission (verdict: Runtime Error):
N,M = int(input().split())
if N == M:
  print('Yes')
else:
  print('No')
Problem p02789 (python)

Fixed submission:
ls = [int(i) for i in input().split()]

if ls[0] == ls[1]:
  print('Yes')
else :
  print('No')

Buggy submission (verdict: Runtime Error):
    l = input().split()
     
    if l[0] == l[1]:
      print('Yes')
    else:
      print('No')

Buggy submission (verdict: Runtime Error):
n = input()
m = input()

if n == m:
  print('YES')
else:
  print('NO')
Problem p03160 (python)

Fixed submission:
def frog(H):
    n = len(H)
    cost = 0
    n_2 = 0
    n_1 = 0
    for i in range(n):
        if i >= 1:
            cost = abs(H[i] - H[i - 1]) + n_1
            if i >= 2:
                cost = min(cost, abs(H[i] - H[i - 2]) + n_2)
        n_2 = n_1
        n_1 = cost
    return cost

assert frog([10, 10, 10]) == 0
assert frog([10, 10]) == 0
assert frog([10, 30, 40, 20]) == 30
assert frog([30, 10, 60, 10, 60, 50]) == 40

n = int(input())
H = list(map(int, input().split()))
ans = frog(H)
print(ans)

Buggy submission (verdict: Runtime Error):
import functools

n = int(input())
A = list(map(int, input().split()))

@functools.lru_cache(None)
def rec(i):
  if i == 0: return 0
  i1 = rec(i - 1) + abs(A[i - 1] - A[i])
  i2 = float("inf")
  if i >= 2:
      i2 = rec(i - 2) + abs(A[i - 2] - A[i])
  return min(i1, i2)

ans = rec(n - 1)
print(ans)
Problem p03164 (python)

Fixed submission:
def knapsack_rec(target, W, V): # target=knapsack weight
    P = {}
    P[0] = target
    max_ = 0

    for vi in range(len(V)):
        we, va = W[vi], V[vi]
        for i in range(max_, -1, -1):
            if i in P:
                piva = P.get(i + va, -1)
                if piva < P[i] - we:
                    P[i + va] = P[i] - we
                    if max_ < i + va:
                        max_ = i + va
    return max_

assert knapsack_rec(15, [6, 5, 6, 6, 3, 7], [5, 6, 4, 6, 5, 2]) == 17

if __name__ == "__main__":
    import sys
    n, w, *r = map(int, sys.stdin.read().split())
    W, V = r[::2], r[1::2]
    ans = knapsack_rec(w, W, V)
    print(ans)

Buggy submission (verdict: Runtime Error):
def knapsack_rec(target, W, V): # target=knapsack weight
    P = {}
    P[target] = 0 # default + max
    max_ = 0

    for vi in range(len(V)):
        we = W[vi]
        va = V[vi]
        for i in P:
            if i >= we:
                prev = P[i-we] if (i-we) in P else -1
                piva = P[i] + va
                if prev < piva:
                    P[i - we] = piva
                    if piva > max_:
                        max_ = piva

    return max_

assert knapsack_rec(15, [6, 5, 6, 6, 3, 7], [5, 6, 4, 6, 5, 2]) == 17

if __name__ == "__main__":
    import sys
    n, w, *r = map(int, sys.stdin.read().split())
    W, V = r[::2], r[1::2]
    ans = knapsack_rec(w, W, V)
    print(ans)
Problem p03165 (python)

Fixed submission:
# AtCoder DP Task F - LCS
def backtrack(C, A, B, i, j):
    out = ""
    while i != 0 and j != 0:
        if A[i - 1] == B[j - 1]:
            out = A[i - 1] + out
            i -= 1
            j -= 1
        elif C[i][j - 1] > C[i - 1][j]:
            j -= 1
        else:
            i -= 1
    return out

def lcs(A, B):
    a, b = len(A), len(B)
    C = [ [0] * (b + 1) for _ in range(a + 1) ]
    for i in range(1, a + 1):
        for j in range(1, b + 1):
            if A[i - 1] == B[j - 1]:
                C[i][j] = C[i-1][j-1] + 1
            else:
                C[i][j] = max(C[i][j - 1], C[i - 1][j])
#    return C[a][b]
    ret = backtrack(C, A, B, a, b)
    return ret

assert lcs("XMJYAUZ", "MZJAWXU") == "MJAU"
assert lcs("MZJAWXU", "XMJYAUZ") == "MJAU"
assert lcs("AGCAT", "GAC") == "AC"
assert lcs("AAAA", "AAAA") == "AAAA"
assert lcs("a", "z") == ""

if False:
    import random
    for _ in range(1000):
        q = [chr(random.randint(ord('a'), ord('z'))) for _ in range(random.randint(1, 1000))]
        p = [chr(random.randint(ord('a'), ord('z'))) for _ in range(random.randint(1, 1000))]
        lcs("".join(q), "".join(p))

x = input().strip()
y = input().strip()
ans = lcs(x, y)
print(ans)

Buggy submission (verdict: Runtime Error):
# AtCoder DP Task F - LCS
def backtrack(C, A, B, i, j):
    if i == 0 or j == 0:
        return ""
    if A[i - 1] == B[j - 1]:
        return backtrack(C, A, B, i - 1, j - 1) + A[i - 1]
    if C[i][j - 1] > C[i - 1][j]:
        return backtrack(C, A, B, i, j - 1)
    return backtrack(C, A, B, i - 1, j)

def lcs(A, B):
    a, b = len(A), len(B)
    C = [ [0] * (b + 1) for _ in range(a + 1) ]
    for i in range(1, a + 1):
        for j in range(1, b + 1):
            if A[i - 1] == B[j - 1]:
                C[i][j] = C[i-1][j-1] + 1
            else:
                C[i][j] = max(C[i][j - 1], C[i - 1][j])
#    return C[a][b]
    ret = backtrack(C, A, B, a, b)
    return ret

assert lcs("XMJYAUZ", "MZJAWXU") == "MJAU"
assert lcs("AGCAT", "GAC") == "AC"
assert lcs("AAAA", "AAAA") == "AAAA"

x = input().strip()
y = input().strip()
ans = lcs(x, y)
print(ans)
Problem p03166 (python)

Fixed submission:
from collections import deque

def main(n, edges):
    deg = [0] * (n + 1)
    adj = {}

    for j in range(1, n + 1):
        adj[j] = []

    for u, v in edges:
        adj[u].append(v)
        deg[v] += 1

    S = deque()

    dp = [-1] * (n + 1)

    for u in range(1, n + 1):
        if deg[u] == 0:
            S.append(u)
            dp[u] = 0

    L = []

    while S:
        v = S.popleft()
        L.append(v)
        for u in adj[v]:
            deg[u] -= 1
            if deg[u] == 0:
                S.append(u)
                dp[u] = max(dp[u], dp[v] + 1)

    return max(dp)

assert main(6, [ (2, 3), (4, 5), (5, 6) ]) == 2
assert main(4, [ (1, 2), (1, 3), (3, 2), (3, 4), (2, 4) ]) == 3

n, m = map(int, input().split())
edges = []
for _ in range(m):
    u, v = map(int, input().split())
    edges.append((u, v))
ans = main(n, edges)
print(ans)

Buggy submission (verdict: Runtime Error):
def dfs(node, edges, dp, visited):
    visited.add(node)
    for child in edges.get(node, []):
        if not child in visited:
            dfs(child, edges, dp, visited)
        dp[node] = max(dp[node], 1 + dp[child])

def main(n, edges):
    dp = [0] * (n + 1)
    visited = set()
    for i in range(1, n + 1):
        if not i in visited:
            dfs(i, edges, dp, visited)
    return max(dp)

assert main(6, { 2: [3], 4: [5], 5: [6] }) == 2
assert main(4, { 1: [2, 3], 3: [2, 4], 2: [4] }) == 3

n, m = map(int, input().split())
edges = {}
for _ in range(m):
    u, v = map(int, input().split())
    if u not in edges:
        edges[u] = set([v])
    else:
        edges[u].add(v)
ans = main(n, edges)
print(ans)
Problem p03206 (python)

Fixed submission:
x = input()
l = { 25: "Christmas", 24: "Christmas Eve", 23: "Christmas Eve Eve", 22: "Christmas Eve Eve Eve" }
print(l[int(x)])

Buggy submission (verdict: Runtime Error):
x = input()
l = { 25: "Christmas", 24: "Christmas Eve", 23: "Christmas Eve Eve", 22: "Christmas Eve Eve Eve" }
return l[int(x)]