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

Fixed submission:
import math
n,k= map(int,input().split())
m=min(n,k)
a=[0]*n
for i in range(1,m+1):
    a[i-1]=math.ceil(math.log2(k/i))
for i in range(m):
    a[i]=0.5**a[i]
print((sum(a)+max(n-k,0))/n)

Buggy submission (verdict: Runtime Error):
import math
n,k= map(int,input().split())
m=min(n,k)
a=[0]*n
for i in range(1,m+1):
    a[i-1]=math.ceil(math.log2(k/i))
for i in range(m):
    a[i]=0.5**a[i]
print((sum(a)+max(n-k,0))/n)
Problem p03160 (python)

Fixed submission:
n=int(input())
h=list(map(int,input().split()))
dp=[0]*n
dp[1]=abs(h[1]-h[0])
for i in range(2,n,1):
    dp[i]=min(dp[i-2]+abs(h[i-2]-h[i]),dp[i-1]+abs(h[i-1]-h[i]))
print(dp[n-1])

Buggy submission (verdict: Runtime Error):
n=int(input())
h=list(map(int,input(),split()))
dp=[0]*n
dp[1]=abs(h[1]-h[0])
for i in range(2,n,1):
  dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]))
print(dp[n-1])
Problem p03163 (python)

Fixed submission:
N,W=map(int,input().split())
w=[0]*N
v=[0]*N
for i in range(N):
    w[i],v[i]=map(int,input().split())
dp=[0]*(W+1)
for i in range(N):
    j=W
    while j>=w[i]:
        dp[j]=max(dp[j],dp[j-w[i]]+v[i])
        j-=1
print(dp[W])

Buggy submission (verdict: Runtime Error):
N,W=map(int,input().split())
for i in range(N):
    w[i],v[i]=map(int,input().split())
dp=[[0 for i in range(W+1)] for j in range(N+1)]
for i in range(N):
    for j in range(W+1):
        if j<w[i]:
            dp[i+1][j]=dp[i][j]
        else:
            dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i])
print(dp[N][W])

Buggy submission (verdict: Runtime Error):
N,W=map(int,input().split())
for i in range(n):
    w[i],v[i]=map(int,input().split())
dp=[[0 for i in range(W+1)] for j in range(N+1)]
for i in range(N):
    for j in range(W+1):
        if j<w[i]:
            dp[i+1][j]=dp[i][j]
        else:
            dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i])
print(dp[N][W])

Buggy submission (verdict: Runtime Error):

#入力,準備
N,W=map(int,input().split())
w=[0]*n
v=[0]*n
for i in range(n):
    w[i],v[i]=map(int,input().split())
dp=[0]*(W+1)

#メイン
#dp[j] : 重さの総和がjを超えないように選んだ時の価値の総和の最大値
for i in range(n):
    j=W
    while j>=w[i]:
        dp[j]=max(dp[j],dp[j-w[i]]+v[i])
        j-=1

print(dp[W])

Buggy submission (verdict: Runtime Error):

#入力,準備
n=int(input())
w=[0]*n
v=[0]*n
for i in range(n):
    w[i],v[i]=map(int,input().split())
W=int(input())
dp=[0]*(W+1)

#メイン
#dp[j] : 重さの総和がjを超えないように選んだ時の価値の総和の最大値
for i in range(n):
    j=W
    while j>=w[i]:
        dp[j]=max(dp[j],dp[j-w[i]]+v[i])
        j-=1

print(dp[W])
Problem p03164 (python)

Fixed submission:
INF = 2000000000
"""
メモ : Pythonでは無限大を表す float('inf') があるが, 処理がかなり重たいので
       代わりにsum(v)より真に大きい 2*10^9 を INFとする.
       (https://atcoder.jp/contests/dp/tasks/dp_e において,PyPyを使用して,
        前者だと1060ms, 後者だと570msで2倍近く差が出ている.)
"""
n,W = map(int,input().split())
w = [0]*n
v = [0]*n
for i in range(n):
    w[i], v[i] = map(int, input().split())
sum_v = sum(v)
dp = [[INF for i in range(sum_v + 1)] for j in range(n + 1)]
# dp[i][j]には重さが入る.
# dp[i][j]=(i番目までの品物から価値がちょうどｊになるための重さの最小値)

# ここからメイン
dp[0][0] = 0
for i in range(n):
    for j in range(sum_v + 1):
        if j < v[i]:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = min(dp[i][j], dp[i][j - v[i]] + w[i])

# n個まで使って,重さがlimit_wを超えないで価値が最大のものを求める.
max_value = 0
for i in range(sum_v + 1):
    if dp[n][i] <= W:
        max_value = i
print(max_value)

Buggy submission (verdict: Runtime Error):
INF = 2000000000
n,W = map(int,input().split())
w = [0]*n
v = [0]*n
for i in range(n):
    w[i], v[i] = map(int, input().split())
sum_v = sum(v)
dp = [INF for i in range(sum_v + 1)]

# ここからメイン
dp[0] = 0
for i in range(n):
    for j in range(sum_v ,-1 ,-1):
        if j >= v[i]:
            dp[j] = min(dp[j], dp[j - v[i]] + w[i])

# n個まで使って,重さがlimit_wを超えないで価値が最大のものを求める.
for i in range(sum_v, -1, -1):
    if dp[i] <= W:
		print(i)
		break

Buggy submission (verdict: Runtime Error):
N,W=map(int,input().split())
w=[0]*N
v=[0]*N
for i in range(N):
    w[i],v[i]=map(int,input().split())
dp=[0]*(W+1)
for i in range(N):
    j=W
    while j>=w[i]:
        dp[j]=max(dp[j],dp[j-w[i]]+v[i])
        j-=1
print(dp[W])

Buggy submission (verdict: Runtime Error):
N,W=map(int,input().split())
w=[0]*N
v=[0]*N
for i in range(N):
    w[i],v[i]=map(int,input().split())
dp=[0]*(W+1)
for i in range(N):
    j=W
    while j>=w[i]:
        dp[j]=max(dp[j],dp[j-w[i]]+v[i])
        j-=1
print(dp[W])
Problem p03219 (python)

Fixed submission:
a,b=map(int,input().split())
print(a+(b//2))

Buggy submission (verdict: Runtime Error):
a,b=int(input())
print(a+(b//2))
Problem p03469 (python)

Fixed submission:
s=list(input())
s[3]="8"
ans=""
for i in range(len(s)):
  ans+=s[i]
print(ans)

Buggy submission (verdict: Runtime Error):
s=input()
s[3]=str(8)
print(s)

Buggy submission (verdict: Runtime Error):
s=input()
s[3]=8
print(s)

Buggy submission (verdict: Runtime Error):
s=input()
s[3]="8"
print(s)
Problem p03493 (python)

Fixed submission:
s=input()
ans=0
for i in range(3):
  if s[i]=="1":
    ans+=1
print(ans)

Buggy submission (verdict: Runtime Error):
s=map(int,input().split())
print(s.count("1"))
Problem p03777 (python)

Fixed submission:
a,b=map(str,input().split())
if a=="H":
  print(b)
else:
  if b=="H":
    print("D")
  else:
    print("H")

Buggy submission (verdict: Runtime Error):
H*H=H
H*D=D
D*H=D
D*D=H
a,b=map(str,input().split())
print(a*b)
Problem p02584 (python)

Fixed submission:
[X,K,D]=[int(_) for _ in input().split()]
X=abs(X)
Y=X//D
if Y <= K:
  X-=Y*D
  if (K-Y)%2 != 0:
    X = abs(X-D) if abs(X-D) < abs(X+D) else abs(X+D)
else:
  X-=K*D
print(X)

Buggy submission (verdict: Runtime Error):
[X,K,D]=[int(_) for _ in input().split()]
X/=D
X=abs(X)
k1 = K//2
k2 = K%2
#print(k1,k2)
for _ in [0]*k1:
  X = min([abs(X-2), abs(X), abs(X+2)])
  #print(X)
if k2 == 1:
  X = X-1 if abs(X-1) < abs(X+1) else X+1
  #print(X)
print(abs(int(X*D)))

Buggy submission (verdict: Runtime Error):
[X,K,D]=[int(_) for _ in input().split()]
X/=D
for _ in [0]*K:
  X = X-1 if abs(X-1) < abs(X+1) else X+1
print(abs(int(X*D)))

Buggy submission (verdict: Runtime Error):
[X,K,D]=[int(_) for _ in input().split()]
for _ in [0]*K:
  X = X-D if abs(X-D) < abs(X+D) else X+D
print(abs(X))
Problem p02621 (python)

Fixed submission:
a=int(input())
b=int(a*a*a+a*a+a)
print(b)

Buggy submission (verdict: Runtime Error):
a=input()
b=a*a*a+a*a+a
print(b)
Problem p02730 (python)

Fixed submission:
S=list(map(str,input()))
if S[0]==S[int((len(S)-1)/2-1)] and S[:int((len(S)-1)/2)]==S[int((len(S)+1)/2):]:
    print("Yes")
else:
    print("No")

Buggy submission (verdict: Runtime Error):
N=list(str(input()))
a=len(N)
if N[0]==N[(a-1)/2] and N[a]==N[(a+3)/2]:
  print("yes")
else:
  print("No")
Problem p02921 (python)

Fixed submission:
S=list(map(str,input()))
T=list(map(str,input()))
cnt=0
for i in range(len(S)):
    if S[i]==T[i]:
        cnt +=1
print(cnt)

Buggy submission (verdict: Runtime Error):
A,B = map(int, input().split())
cnt = 1
ans = 0
while cnt < B:
    cnt += A-1
    ans += 1
print(ans)
Problem p02957 (python)

Fixed submission:
A,B=map(int,input().split())
if (A+B)%2 !=0:
    print("IMPOSSIBLE")
else:
    print(int((A+B)/2))

Buggy submission (verdict: Runtime Error):
A,B=map(int,input().split())
if (A+B)%2 !=0:
	print("IMPOSSIBLE")
else:
	print((A+B)2)

Buggy submission (verdict: Runtime Error):
A,B=map(int,input().split())
if (A+B)%2 !=0:
	print("IMPOSSIBLE")
else:
  print((A+B)2)
Problem p03238 (python)

Fixed submission:
N=int(input())
if N==1:
    print("Hello World")
elif N==2:
    a=int(input())
    b=int(input())
    print(a+b)

Buggy submission (verdict: Runtime Error):
N=int(input())
a=int(input())
b=int(input())
if N==1:
    print("Hello World")
elif N==2:
    print(a+b)
Problem p03433 (python)

Fixed submission:
N=int(input())
A=int(input())
if (N%500)==0:
  print("Yes")
elif ((N%500)-A)<=0:
  print("Yes")
elif ((N%500)-A) >0:
  print("No")

Buggy submission (verdict: Runtime Error):
N=int(input())
A=int(input())
if (N%500)==0:
  print("Yes")
elif (N%500)%A==0:
  print("Yes")
else:
  print("No")
Problem p02843 (python)

Fixed submission:
N = int(input())

import sys
sys.setrecursionlimit(10 ** 9)

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

def dfs(x):
    if x >= 0 and memo[x] != -1:
        return memo[x]
    ans = False
    if x == 0:
        memo[x] = 1
        return True
    elif x < 0:
        return False
    else:
        ans |= dfs(x - 100)
        ans |= dfs(x - 101)
        ans |= dfs(x - 102)
        ans |= dfs(x - 103)
        ans |= dfs(x - 104)
        ans |= dfs(x - 105)
    memo[x] = 1 if ans else 0
    return ans
if dfs(N):
    print(1)
else:
    print(0)

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

import sys
sys.setrecursionlimit(10 ** 9)

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

def dfs(x):
    if x >= 0 and memo[x] != -1:
        return memo[x]
    ans = False
    if x == 0:
        memo[x] = 1
        return True
    elif x < 0:
        memo[x] = 0
        return False
    else:
        ans |= dfs(x - 100)
        ans |= dfs(x - 101)
        ans |= dfs(x - 102)
        ans |= dfs(x - 103)
        ans |= dfs(x - 104)
        ans |= dfs(x - 105)
    memo[x] = 1 if ans else 0
    return ans
if dfs(N):
    print(1)
else:
    print(0)

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

import sys
sys.setrecursionlimit(10 ** 9)

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

def dfs(x):
    if memo[x] != -1:
        return memo[x]
    ans = False
    if x == 0:
        memo[x] = 1
        return True
    elif x < 0:
        memo[x] = 0
        return False
    else:
        ans |= dfs(x - 100)
        ans |= dfs(x - 101)
        ans |= dfs(x - 102)
        ans |= dfs(x - 103)
        ans |= dfs(x - 104)
        ans |= dfs(x - 105)
    memo[x] = 1 if ans else 0
    return ans
if dfs(N):
    print(1)
else:
    print(0)
Problem p02999 (python)

Fixed submission:
X,A = map(int, input().split())

if X < A:
    print(0)
else:
    print(10)

Buggy submission (verdict: Runtime Error):
W, H, x, y = map(int, input().split())
 
print((H * W) / 2, end=" ")
 
if W / 2 == x and H /2 == y:
    print(1)
else:
    print(0)
Problem p03063 (python)

Fixed submission:
N = int(input())
S = list(input())

acc = [0]
acc2 = [0]
for s in S:
    if s == ".":
        acc.append(acc[-1] + 1)
        acc2.append(acc2[-1])
    else:
        acc.append(acc[-1])
        acc2.append(acc2[-1] + 1)
acc.pop(0)

ans = float("inf")

for i in range(N):
    s = S[i]
    tmp = acc[-1] - acc[i]
    tmp2 = acc2[i]
    ans = min(ans , tmp + tmp2)
print(ans)

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

ans = 0
T1 = S.copy()
f = False
for i in range(N):
    s = T1[i]
    if s == ".":
        continue
    else:
        if i < N - 1 and T1[i+1] == ".":
            if not f and i + 1 < N - 1 and T1[i+2] == ".":
                ans += 1
            else:
                f = True
                T1[i+1] = "#"
                ans += 1
        else:
            f = True
ans2 = 0

for i in range(N):
    s = S[i]
    if s == ".":
        continue
    else:
        ans2 += 1

ans3 = 0

for i in range(N):
    s = S[i]
    if s == ".":
        ans3 += 1
    else:
        continue

while S[-1] != ".":
    S.pop()
N = len(S)
ans4 = 0
for i in range(N):
    s = S[i]
    if s == ".":
        continue
    else:
        ans4 += 1

# print(ans, ans2, ans3)
print(min(ans2, ans, ans3, ans4))

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

while S[-1] != ".":
    S.pop()
N = len(S)

if N == 0:
    print(0)

ans = 0
T1 = S.copy()
f = False
for i in range(N):
    s = T1[i]
    if s == ".":
        continue
    else:
        if i < N - 1 and T1[i+1] == ".":
            if not f and i + 1 < N - 1 and T1[i+2] == ".":
                ans += 1
            else:
                f = True
                T1[i+1] = "#"
                ans += 1
        else:
            f = True
ans2 = 0

for i in range(N):
    s = S[i]
    if s == ".":
        continue
    else:
        ans2 += 1

ans3 = 0

for i in range(N):
    s = S[i]
    if s == ".":
        ans3 += 1
    else:
        continue
print(min(ans2, ans, ans3))
Problem p03085 (python)

Fixed submission:
b = input()

if b == "A":
    print("T")
elif b == "T":
    print("A")
elif b == "G":
    print("C")
else:
    print("G")

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

mod = 10 ** 9 + 7

dp = [[[[0] * 4 for _ in range(4)] for _ in range(4)] for _ in range(N + 1)]

dp[0][3][3][3] = 1

print(dp)
for i in range(N):
    for j in range(4):
        for k in range(4):
            for m in range(4):
                if dp[i][j][k][m] == 0:
                    continue
                for l in range(4):
                    if l == 2 and j == 1 and k == 0:
                        continue
                    if l == 2 and j == 0 and k == 1:
                        continue
                    if l == 1 and j == 2 and k == 0:
                        continue
                    if l == 2 and j == 1 and m == 0:
                        continue
                    if l == 2 and k == 1 and m == 0:
                        continue
                    dp[i + 1][l][j][k] += dp[i][j][k][m]
                    dp[i + 1][l][j][k] %= mod

ans = 0
print(dp)
for i in range(4):
    for j in range(4):
        for k in range(4):
            ans += dp[N][i][j][k]
            ans %= mod
print(ans)
Problem p03112 (python)

Fixed submission:
A, B, Q = map(int, input().split())
s_list = [int(input()) for i in range(A)]
t_list = [int(input()) for i in range(B)]
x_list = [int(input()) for _ in range(Q)]

s_list.sort()
t_list.sort()
s_list = [-float("inf")] + s_list + [float("inf")]
t_list = [-float("inf")] + t_list + [float("inf")]
import bisect

ans = []
for x in x_list:
    tmp = float("inf")
    s_i = bisect.bisect_left(s_list, x)
    t_i = bisect.bisect_left(t_list, x)

    for s in (s_list[s_i - 1], s_list[s_i]):
        for t in (t_list[t_i - 1], t_list[t_i]):
            d1 = abs(s - x) + abs(t - s)
            d2 = abs(t - x) + abs(s - t)
            tmp = min(tmp, d1, d2)
    ans.append(tmp)
for a in ans:
    print(a)

Buggy submission (verdict: Runtime Error):
A, B, Q = map(int, input().split())
s_list = [int(input()) for i in range(A)]
t_list = [int(input()) for i in range(B)]
x_list = [int(input()) for _ in range(Q)]

s_list.sort()
t_list.sort()
import bisect

ans = []
for x in x_list:
    tmp = float("inf")
    s_i = bisect.bisect_left(s_list, x)
    t_i = bisect.bisect_left(t_list, x)

    if s_i == A and t_i == B:
        tmp = abs(x - min(s_list[-1], t_list[-1]))
        ans.append(tmp)
        continue
    if s_i == A:
        if t_i != 0:
            tmp = abs(s_list[-1] - x)
            if s_list[-1] <= t_list[t_i] <= x:
                ans.append(tmp)
                continue
            else:
                tmp += min(abs(t_list[t_i] - x) * 2, abs(t_list[t_i - 1] - s_list[-1]))
        else:
            tmp = abs(min(abs(s_list[s_i - 1] - x), abs(t_list[0] - x)) * 2 + max(abs(s_list[s_i - 1] - x), abs(t_list[0] - x)))
        ans.append(tmp)
        continue
    if t_i == B:
        if s_i != 0:
            tmp = abs(t_list[-1] - x)
            if t_list[-1] <= s_list[t_i] <= x:
                ans.append(tmp)
                continue
            else:
                tmp += min(abs(s_list[s_i] - x) * 2, abs(s_list[s_i - 1] - t_list[-1]))
        else:
            tmp = abs(min(abs(t_list[t_i - 1] - x), abs(s_list[0] - x)) * 2 + max(abs(t_list[t_i - 1] - x), abs(s_list[0] - x)))
        ans.append(tmp)
        continue
    tmp = min(tmp, max(s_list[s_i], t_list[t_i]) - x)
    if s_i != 0:
        tmp = min(tmp, s_list[s_i - 1] + t_list[t_i] - x)
    if t_i != 0:
        tmp = min(tmp, s_list[s_i] + t_list[t_i - 1] - x)
    ans.append(tmp)

for a in ans:
    print(a)
Problem p03125 (python)

Fixed submission:
A, B = map(int, input().split())

if B % A == 0:
    print(A+B)
else:
    print(B-A)

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

items = {
    1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6
}
dp = [0] * (N + 1)

b_list = []
for a in a_list:
    need = items[a]
    if need <= N:
        dp[need] = a
        b_list.append(a)

M = len(b_list)
b_list.sort()
for i in range(N + 1):
    for b in b_list:
        if i - items[b] >= 0:
            if dp[i - items[b]] != 0:
                cnt = 0
                num = dp[i - items[b]]
                while num >= 1:
                    cnt += 1
                    num //= 10
                tmp = max(b * (10 ** cnt) + dp[i - items[b]], dp[i - items[b]] * 10 + b)
                dp[i] = max(tmp, dp[i])
print(dp[N])
Problem p03138 (python)

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

b = [0] * 41
for a in A:
    for k in range(41):
        if a & (1 << k):
            b[k] += 1

x = 0
for k in range(40, -1, -1):
    if x + (1 << k) > K:
        continue
    if b[k] < (N + 1) // 2:
        x += (1 << k)

ans = 0
for a in A:
    ans += x ^ a
print(ans)

Buggy submission (verdict: Runtime Error):
N, K = map(int, input().split())
a_list = list(map(int, input().split()))
cnt = [0] * K
for a in a_list:
    bi = bin(a)[2:].zfill(K)
    if a >= K:
        continue
    for j in range(len(bi)):
        if bi[j] == "1":
            cnt[j] += 1
xor_str = ""
first = float("inf")
k_bin = bin(K)[2:]
for i, c in enumerate(cnt):
    if c % 2 == 0:
        xor_str += "0"
        if c >= 2 and i < first:
            first = i
    else:
        xor_str += "1"
if xor_str.count("0") == K:
    xor_str = xor_str[1:first] + "1" + xor_str[first:K]
xor = int(xor_str, 2)
ans = 0
for a in a_list:
    ans += xor ^ a
print(ans)
Problem p03160 (python)

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

dp = [float("inf") for _ in range(N + 1)]
dp[1] = 0
for i in range(2, N + 1):
    if i == 2:
        dp[2] = abs(h_list[1] - h_list[0])
    else:
        dp[i] = min(dp[i - 1] + abs(h_list[i-1] - h_list[i - 2]), dp[i - 2] + abs(h_list[i-1] - h_list[i - 3]))
print(dp[N])

Buggy submission (verdict: Runtime Error):
H, W = map(int, input().split())
s_list = []
for i in range(H):
    s = list(input())
    s_list.append(s)

dp = [[0 for _ in range(W)] for _ in range(H)]
dp[0][0] = 1
mod = 10 ** 9 + 7
for i in range(H):
    for j in range(W):
        if s_list[i][j] == "#":
            continue
        if i + 1 < H and s_list[i + 1][j] == ".":
            dp[i + 1][j] += dp[i][j] % mod
        if j + 1 < W and s_list[i][j + 1] == ".":
            dp[i][j + 1] += dp[i][j] % mod
print(dp[H - 1][W - 1] % mod)
Problem p03164 (python)

Fixed submission:
N, W = map(int, input().split())
goods = [list(map(int, input().split())) for i in range(N)]
v_sum = sum([i[1] for i in goods])
dp = [float("inf") for i in range(v_sum + 1)]
dp[0] = 0
for i in range(N):
    for j in range(v_sum, -1, -1):
        dp[j] = min(dp[j - goods[i][1]] + goods[i][0], dp[j])

for i in range(v_sum, -1, -1):
    if dp[i] <= W:
        print(i)
        break

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

items = [list(map(int, input().split())) for _ in range(N)]
v_sum = sum([item[1] for item in items])

inf = float("inf")
dp = [inf for _ in range(v_sum + 1)]

dp[0] = 0
for i in range(N):
    for j in range(v_sum, -1, -1):
        if dp[j] >= dp[j - items[i][1] + items[i][0]]:
            dp[j] = dp[j - items[i][1]] + items[i][0]

for i in range(v_sum, -1, -1):
    if dp[i] <= W:
        print(i)
        exit()

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

items = [list(map(int, input().split())) for i in range(N)]
v_sum = sum([i[1] for i in items])

inf = float("inf")
dp = [inf for i in range(v_sum + 1)]

dp[0] = 0
for i in range(N):
    for j in range(v_sum, -1, -1):
        if dp[j] > dp[j - items[i][1] + items[i][0]]:
            dp[j] = dp[j - items[i][1]] + items[i][0]

for i in range(v_sum, -1, -1):
    if dp[i] <= W:
        print(i)
        exit()
Problem p03165 (python)

Fixed submission:
def lcs(x, y):
    m = len(x)
    n = len(y)

    c = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if x[i - 1] == y[j - 1]:
                c[i][j] = c[i - 1][j - 1] + 1
            else:
                c[i][j] = max(c[i - 1][j], c[i][j - 1])

    lcs_str = ''
    i, j = m, n
    while i > 0 and j > 0:
        if x[i-1] == y[j-1]:
            lcs_str += x[i-1]
            i -= 1
            j -= 1
        else:
            if c[i][j] == c[i-1][j]:
                i -= 1
            else:
                j -= 1

    return lcs_str[::-1]


s = input()
t = input()
print(lcs(s, t))

Buggy submission (verdict: Runtime Error):
def maxBy(f, x, y):
    if f(x) > f(y):
        return x
    else:
        return y


table = {("", ""): ""}


def lcs(xs, ys):
    if (xs, ys) in table:
        return table[(xs, ys)]

    ret = ""
    if xs == "" or ys == "":
        ret = ""
    elif xs[-1] == ys[-1]:
        ret = lcs(xs[:-1], ys[:-1]) + xs[-1]
    else:
        ret = maxBy(len,
                    lcs(xs[:-1], ys),
                    lcs(xs, ys[:-1]))
    table[(xs, ys)] = ret
    return ret


s = input()
t = input()

c = lcs(s, t)
print(c)
Problem p03166 (python)

Fixed submission:
import sys

sys.setrecursionlimit(10 ** 8)

N, M = map(int, input().split())
graph = [dict() for _ in range(N)]

for i in range(M):
    x, y = map(int, input().split())
    graph[y - 1][x - 1] = 1

dp = [0 for _ in range(N)]


def dfs(u):
    if dp[u] != 0:
        return dp[u]
    max_dis = 0
    for f in graph[u].keys():
        if max_dis < dfs(f) + 1:
            max_dis = dfs(f) + 1

    dp[u] = max_dis
    return dp[u]


for i in range(N):
    dfs(i)
print(max(dp))

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

for i in range(M):
    x, y = map(int, input().split())
    graph[y - 1][x - 1] = 1

dp = [0 for _ in range(N)]


def dfs(u):
    if dp[u] != 0:
        return dp[u]
    max_dis = 0
    for f in graph[u].keys():
        if max_dis < dfs(f) + 1:
            max_dis = dfs(f) + 1

    dp[u] = max_dis
    return dp[u]


for i in range(N):
    dfs(i)
print(max(dp))

Buggy submission (verdict: Runtime Error):
H, W = map(int, input().split())
s_list = []
for i in range(H):
    s = list(input())
    s_list.append(s)

dp = [[0 for _ in range(W)] for _ in range(H)]
dp[0][0] = 1
mod = 10 ** 9 + 7
for i in range(H):
    for j in range(W):
        if s_list[i][j] == "#":
            continue
        if i + 1 < H and s_list[i + 1][j] == ".":
            dp[i + 1][j] += dp[i][j] % mod
        if j + 1 < W and s_list[i][j + 1] == ".":
            dp[i][j + 1] += dp[i][j] % mod
print(dp[H - 1][W - 1] % mod)

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

graph = [dict() for _ in range(N)]
for i in range(M):
    x, y = map(int, input().split())
    graph[x-1][y-1] = 1

dp = [0 for _ in range(N)]

def dfs(num_v):
    if len(graph[num_v]) == 0:
        return
    for to in graph[num_v].keys():
        dp[to] = max(dp[to], dp[num_v] + 1)
        dfs(to)

ans = 0
for i in range(N):
    dfs(i)
    ans = max(ans, max(dp))
print(ans)