Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
n = int(input())

if n %2 ==1:
  print(0)
else:
  mod = 10
  ans = 0
  x = 0
  while(x>0):
    x = n//mod
    ans+=x
    mod *= 5
print(ans)

Fixed submission:
n = int(input())

if n %2 ==1:
  print(0)
else:
  mod = 10
  ans = 0
  x = 0
  while True:
    x = n//mod
    if x==0: break
    ans+=x
    mod *= 5
  print(ans)

Buggy python submission (verdict: Runtime Error):
try:
  n = int(input())

  if n %2 ==1:
    print(0)
  else:
    mod = 10
    ans = n//mod
    x = n//mod
    while(x>0):
      mod *= 5
      x = n//mod
      ans+=x
print(ans)
except Exception as e:
  print(e)


Fixed submission:
n = int(input())

if n %2 ==1:
  print(0)
else:
  mod = 10
  ans = 0
  x = 0
  while True:
    x = n//mod
    if x==0: break
    ans+=x
    mod *= 5
  print(ans)

Buggy python submission (verdict: Runtime Error):
n = int(input())

if n %2 ==1:
  print(0)
else:
  mod = 10
  ans = n//mod
  x = n//mod
  loop = 0
  while(x>0 and loop<10**7):
    loop += 1
    mod *= 5
    x = n//mod
    ans+=x
print(ans)

Fixed submission:
n = int(input())

if n %2 ==1:
  print(0)
else:
  mod = 10
  ans = 0
  x = 0
  while True:
    x = n//mod
    if x==0: break
    ans+=x
    mod *= 5
  print(ans)

Buggy python submission (verdict: Runtime Error):
n = int(input())

if n %2 ==1:
  print(0)
else:
  mod = 10
  ans = n//mod
  x = n//mod
  while(x>0):
    mod *= 5
    x = n//mod
    ans+=x
print(ans)

Fixed submission:
n = int(input())

if n %2 ==1:
  print(0)
else:
  mod = 10
  ans = 0
  x = 0
  while True:
    x = n//mod
    if x==0: break
    ans+=x
    mod *= 5
  print(ans)

Buggy python submission (verdict: Runtime Error):
n = int(input())

if n %2 ==1:
  print(0)
else:
  mod = 10
  ans = x = n//mod
  
  while(x>=0):
    mod *= 5
    x = n//mod
    ans+=x
print(ans)

Fixed submission:
n = int(input())

if n %2 ==1:
  print(0)
else:
  mod = 10
  ans = 0
  x = 0
  while True:
    x = n//mod
    if x==0: break
    ans+=x
    mod *= 5
  print(ans)

Buggy python submission (verdict: Runtime Error):
n = int(input())

if n %2 ==1:
  print(0)
else:
  mod = 10
  ans = x = n//mod
  
  while(x>0):
    mod *= 5
    x = n//mod
    ans+=x
print(ans)

Fixed submission:
n = int(input())

if n %2 ==1:
  print(0)
else:
  mod = 10
  ans = 0
  x = 0
  while True:
    x = n//mod
    if x==0: break
    ans+=x
    mod *= 5
  print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())

ls = [map(int(input().split())) for _ in range(n)]

sum = 0
for i in range(n-1):
  for j in range(1,n):
    sum += ((ls[i][0]-ls[j][0])**2+(ls[i][1]-ls[j][1])**2)**0.5
    
print(sum*2/n)

Fixed submission:
n = int(input())

ls = [list(map(int,input().split())) for _ in range(n)]

sum = 0
for i in range(n-1):
  for j in range(i+1,n):
    sum += ((ls[i][0]-ls[j][0])**2+(ls[i][1]-ls[j][1])**2)**0.5
    
print(sum*2/n)
Buggy python submission (verdict: Runtime Error):
t = input()
s = list(t)
k = int(input())

ans = 0

s = s+s
for i in range(1,len(s)):
  if s[i-1] == s[i]:
    s[i] = "0"
    if i>=len(s)//2:
      ans += k-1
    else:
      ans += 1
      
if len(set(list(t))) == 1 and len(t)%2 == 1:
  ans = len(t) * (k//2) + (k%2==1)*(t//2)
print(ans)

Fixed submission:
t = input()
s = list(t)
k = int(input())

ans = 0

s = s+s
for i in range(1,len(s)):
  if s[i-1] == s[i]:
    s[i] = "0"
    if i>=len(s)//2:
      ans += k-1
    else:
      ans += 1
      
if len(set(list(t))) == 1 and len(t)%2 == 1:
  ans = len(t) * (k//2) + (k%2==1)*(len(t)//2)
print(ans)

Buggy python submission (verdict: Runtime Error):
t = input()
s = list(t)
k = int(input())

ans = 0

s = s+s
for i in range(1,len(s)):
  if s[i-1] == s[i]:
    s[i] = "0"
    if i>=len(s)//2:
      ans += k-1
    else:
      ans += 1
      
if len(set(list(t))) == 1 and len(t)%2 == 1:
  ans = len(t) * (k//2) + (k%2==1)*(k//2)
  ans = 1/0
print(ans)

Fixed submission:
t = input()
s = list(t)
k = int(input())

ans = 0

s = s+s
for i in range(1,len(s)):
  if s[i-1] == s[i]:
    s[i] = "0"
    if i>=len(s)//2:
      ans += k-1
    else:
      ans += 1
      
if len(set(list(t))) == 1 and len(t)%2 == 1:
  ans = len(t) * (k//2) + (k%2==1)*(len(t)//2)
print(ans)
Buggy python submission (verdict: Runtime Error):
def main():
  import fractions
  import math

  a,b = map(int,input().split())

  if a>b:
    a,b = b,a
  
  d = [1]
  num = 2

  while num <= min(a,b):
    if a%num == 0 and b%num == 0:
      d.append(num)
      while a%num == 0 and a>1:
        a = a//num
      while b%num == 0 and b>1:
        b = b//num
    num+=1
  
  print(len(d))

if __name__ == "__main__":
  main()


Fixed submission:
n = int(input())

print(0.5 if n%2==0 else (n//2+1)/n)
Buggy python submission (verdict: Runtime Error):
n = int(input())

ls = list(map(int,input().split()))

ans = [None]*n

for i in range(n):
  ans[ls[i]-1] = i+1
  
print(" ".join(ans))

Fixed submission:
n = int(input())
 
ls = list(map(int,input().split()))
 
ans = [None]*n
 
for i in range(n):
  ans[ls[i]-1] = i+1
  
print(" ".join(map(str,ans)))
Buggy python submission (verdict: Time Limit Exceeded):
n,k = map(int,input().split())
s = input()
ls = []

tmp = s[0]
count = 1
for i in range(1,n):
  if s[i] == tmp:
    count += 1
  else:
    tmp = s[i]
    ls.append(count)
    count = 1
ls.append(count)


while k>0 and len(ls)>1:
  tmp = 0
  k-=1
  if len(ls) == 2:
    ls = [ls[0]+ls[1]]
  else:
    tmp += ls.pop(0)
    tmp += ls.pop(0)
    tmp += ls.pop(0)
    ls = [tmp]+ls
  
print(n-len(ls))

Fixed submission:
n,k = map(int,input().split())
s = input()
ls = []

tmp = s[0]
count = 1
for i in range(1,n):
  if s[i] == tmp:
    count += 1
  else:
    tmp = s[i]
    ls.append(count)
    count = 1
ls.append(count)

length = len(ls)
for i in range(k):
  if length==1: break
  tmp = 0
  if length == 2:
    ls = [ls[0]+ls[1]]
    break
  else:
    tmp += ls.pop(0)
    tmp += ls.pop(0)
    ls[0] += tmp
    length -= 2
  
print(n-len(ls))
Buggy python submission (verdict: Runtime Error):
import numpy as np
n,q= map(int,input().split())

edges = {i+1:[] for i in range(n+1)}
for i in range(n-1):
  a,b = map(int,input().split())
  edges[a].append(b)

ans = np.zeros(n)
dp = {i:np.zeros(n) for i in range(1,n+1)}
for i in range(1,n+1):
  dp[i][i-1] = 1
for i in range(n,0,-1):
  for j in edges[i]:
    dp[i] += dp[j]

queries = [0]*(n+1)
for _ in range(q):
  p,x = map(int,input().split())
  queries[p] += x
for i in range(1,n+1):
  ans += queries[i]*dp[i]
    
st = ""
for i in range(n):
  if i != 0:
    st+=" "
  st+= str(int(ans[i]))
print(st)

Fixed submission:
n = int(input())
s = input()
if n< 3200:
  print("red")
else:
  print(s)

Buggy python submission (verdict: Runtime Error):
n = int(input())

if n>= 3200:
  print(red)
else:
  print(input())

Fixed submission:
n = int(input())
s = input()
if n< 3200:
  print("red")
else:
  print(s)
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
st = 0
ans = 0

finished = [b[i] == a[i] for i in range(n)]
fcount = sum(finished)
while fcount<n and ans>=0:
  for i in range(st,n):
    if not finished[i] and (b[i-1] <= b[i] >= b[(i+1) % n]):
      ans += (b[i]-a[i])//(b[i-1] + b[(i+1) % n])
      b[i] =a[i]+(b[i]-a[i]) % (b[i-1] + b[(i+1) % n])
      
      #print(b)
      if b[i] == a[i]:
        finished[i] = True
        fcount += 1
      elif b[i] < a[i]:
        ans = -1
        break
      st =(i-1)%n
      break
    elif i == n-1:
      st = 0
      
print(ans)
      



Fixed submission:
s = input()
n = len(s)

i = 0
tmp = ''
ans = 0
while i<n:
  
  if s[i] == tmp:
    if i == n-1:
      break
    tmp = s[i]+s[i+1]
    i+=2
  else:
    tmp = s[i]
    i+=1
  ans +=1
    
print(ans)
Buggy python submission (verdict: Runtime Error):
import heapq

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

ls = [list(map(int,input().split())) for i in range(n)]

ls = sorted(ls,key=lambda x:(x[0],-x[1]))

ans = 0
a = []
j = 0
for i in range(m-1,-1,-1):
  while j<len(ls) and ls[j][0] == m-i:
    heapq.heappush(a,ls[j][1]*(-1))
    j += 1
  g = -1*heapq.heappop(a)
  ans += g

print(ans)

Fixed submission:
import heapq

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

ls = [list(map(int,input().split())) for i in range(n)]

ls = sorted(ls,key=lambda x:(x[0],-x[1]))

ans = 0
a = []
j = 0
for i in range(m-1,-1,-1):
  while j<len(ls) and ls[j][0] == m-i:
    heapq.heappush(a,ls[j][1]*(-1))
    j += 1
  
  if a:
    ans += -1*heapq.heappop(a)

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

print(max(0,c-a+b))

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

print(max(0,c-a+b))
Buggy python submission (verdict: Runtime Error):
mod = 2019
l,r = map(int,input().split())

if l==0 or r//mod - (l-1)//mod >= 1:
  print(0)
else:
  print(l*(l+1)%mod)

Fixed submission:
n = int(input())

lsA = list(map(int,input().split()))
tot = sum(lsA)

an = tot
for i in range(0,n-2,2):
  an -= 2*lsA[i]

ans = [2*lsA[i] for i in range(n)]
ans[n-1] = an
for i in range(n-2,-1,-1):
  ans[i] -= ans[i+1]

print(" ".join(list(map(str,ans))))
Buggy python submission (verdict: Runtime Error):
import math
a,b,c,d = map(int,input().split())

tot = b - a + 1
e = c*d//math.gcd(c,d)
ans = tot - (b//c-(a-1)//c) - (b//d-(a-1)//d) + (b//e-(a-1)//e)
print(int(ans)  )

Fixed submission:
def gcd(a, b):
  while b:
    a, b = b, a % b
  return a


a,b,c,d = map(int,input().split())

tot = b - a + 1
e = c*d//gcd(c,d)
ans = tot - (b//c-(a-1)//c) - (b//d-(a-1)//d) + (b//e-(a-1)//e)
print(int(ans))
Buggy python submission (verdict: Runtime Error):
w,h,x,y = map(int,input().split())


num = 0

if w%2 is 0 and h%2 is 0:
  if w//2 is x and h//2 is y:
  	num = 1
    num = 2/0
print(w*h/2,num)


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

if x>=a:
  print(10)
else:
  print(0)
Buggy python submission (verdict: Runtime Error):
w,h,x,y = map(int,input().split())


num = 0

if w%2 is 0 and h%2 is 0:
  if w//2 is x and h//2 is y:
  	num = 1;a = 2/0
print(w*h/2,num)


Fixed submission:
w,h,x,y = map(int,input().split())


num = 0

if w/2 == x and h/2 == y:
  num = 1
print(w*h/2,num)

Buggy python submission (verdict: Runtime Error):
w,h,x,y = map(int,input().split())


num = 0

if w%2 is 0 and h%2 is 0:
  if w//2 is x and h//2 is y:
  	num = 1;num = 2/0
print(w*h/2,num)


Fixed submission:
w,h,x,y = map(int,input().split())


num = 0

if w/2 == x and h/2 == y:
  num = 1
print(w*h/2,num)
Buggy python submission (verdict: Runtime Error):
N,A,B,C,D = map(int,input().split())
S = input()

def obs(st,end):
  for i in range(st,end):
  	if S[i] is "#" and S[i+1] is "#": return True
  return False

if obs(B,D) or obs(A,C):
  print("No")
elif C > D:
  b = False
  for i in range(B-1,max(D,N-2)):
    if S[i] is "." and S[i+1] is "." and S[i+2] is ".":
      b = True
      break
  if b:
    print("Yes")
  else:
    print("No")
else:
  print("Yes")


    
  

Fixed submission:
N,A,B,C,D = map(lambda x: int(x)-1,input().split())
S = input()

def obs(st,end):
  for i in range(st,end):
  	if S[i] is "#" and S[i+1] is "#": return True
  return False

if obs(B,D) or obs(A,C):
  print("No")
elif C > D:
  b = False
  for i in range(B-1,min(D,N-2)):
    if S[i] is "." and S[i+1] is "." and S[i+2] is ".":
      b = True
      break
  if b:
    print("Yes")
  else:
    print("No")
else:
  print("Yes")

Buggy python submission (verdict: Runtime Error):
N,A,B,C,D = map(int,input().split())
S = input()

def obs(st,end):
  for i in range(st,end):
  	if S[i] is "#" and S[i+1] is "#": return True
  return False

if obs(B,D) or obs(A,C):
  print("No")
elif C > D:
  b = False
  for i in range(B-1,D):
    if S[i] is "." and S[i+1] is "." and S[i+2] is ".":
      b = True
      break
  if b:
    print("Yes")
  else:
    print("No")
else:
  print("Yes")


    
  

Fixed submission:
N,A,B,C,D = map(lambda x: int(x)-1,input().split())
S = input()

def obs(st,end):
  for i in range(st,end):
  	if S[i] is "#" and S[i+1] is "#": return True
  return False

if obs(B,D) or obs(A,C):
  print("No")
elif C > D:
  b = False
  for i in range(B-1,min(D,N-2)):
    if S[i] is "." and S[i+1] is "." and S[i+2] is ".":
      b = True
      break
  if b:
    print("Yes")
  else:
    print("No")
else:
  print("Yes")
Buggy python submission (verdict: Runtime Error):
from collections import deque

N,M = map(int,input().split())

xy = {i:[] for i in range(1,N+1)}
visited = {i:False for i in range(1,N+1)}

for _ in range(M):
  x,y,z = map(int,input().split())
  xy[x].append(y)
  xy[y].append(x)

def dfs(p):
  visited[p] = True
  for q in xy[p]:
    if visited[q]:
      pass
    else:
      dfs(q)
      
count = 0
for i in range(1,N+1):
  if visited[i]:
    continue
  else:
    count += 1
    dfs(i)
print(count)
  

Fixed submission:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
      
      
def main():
  n,m = map(int,input().split())
  u = UnionFind(n)
  
  for _ in range(m):
    x,y,_ = map(int,input().split())
    u.union(x-1,y-1)
  print(u.group_count())
  
if __name__ == "__main__":
  main()
Buggy python submission (verdict: Runtime Error):
R,G,B,N = map(int,input().split())
a = sorted([R,G,B],reverse=True) 
R,G,B = a[0],a[1],a[2]

count = 0
for r in range(N//R+1):
  if r*R>N:break
  for g in range(N//G+1):
    if r*R+g*G>N: break
    for b in range(N//B+1):
      if  (r)*R+(g)*G+(b)*B == N:
        count += 1
print(count)
        


Fixed submission:
n,k = map(int,input().split())

print(n-k+1)
Buggy python submission (verdict: Runtime Error):
n = int(input())
arr = list(map(int,input().split(" ")))

count = 0
s = 1000000000
add = 0
for num in arr:
  if num < 0:
    count += 1
  s = min(s, abs(num))
  add += abs(num)

print(add-(count%2)*abs(s)*2)

Fixed submission:
l = list(map(int,input().split(" ")))
A = l[0]
B = l[1]
T = l[2]

print((T//A)*B)

Buggy python submission (verdict: Runtime Error):
def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)
  
n = int(input())
arr = list(map(int,input().split(" ")))
list.sort(arr)

memoa = [None for i in range(n)]
memoa[0] = arr[0]
memob = [None for i in range(n)]
memob[0] = arr[-1]
for i in range(1,n):
  memoa[i] = gcd(memoa[i-1],arr[i])
  memob[i] = gcd(memob[i-1],arr[i])

m = 0
for i in range(len(arr)):
  if i is 0:
    ans = memob[n-2]
  elif i is n-1:
    ans = memoa[n-2]
  else:
    ans = gcd(memoa[i-1],memob[n-i-2])
      
  m = max(m, ans)
print(m)

Fixed submission:
l = list(map(int,input().split(" ")))
A = l[0]
B = l[1]
T = l[2]

print((T//A)*B)
Buggy python submission (verdict: Runtime Error):
k = int(input().split(" ")[1])
s = input()

arr = []
if s[0] is "0": 
  arr.append(0)
arr.append(1)
for i in range(1,len(s)):
  if s[i-1] is s[i]:
    arr[-1] += 1
  else:
    arr.append(1)
if s[-1] is "0": 
  arr.append(0)

t = 2*k+1
if t>len(s):
  print(len(s))
else:
  temp = sum(arr[0:t])
  m = temp
  for i in range(2,len(arr)-t+1,2):
    m = max(m,temp-arr[i-2]-arr[i-1]+arr[i+t-2]+arr[i+t-1])
  print(m)
#print(arr)

Fixed submission:
arr = list(map(int,input().split(" ")))
a = arr[0]
b = arr[1]

if a==b:
  print(2*a)
else:
  print(2*max(a,b)-1)
Buggy python submission (verdict: Time Limit Exceeded):
x,y,z,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

r = []

for i in range(x):
  for j in range(y):
    for h in range(z):
      r.append(a[i]+b[j]+c[h])
list.sort(r,reverse=True)
for i in range(k):
  print(r[i])

Fixed submission:
x,y,z,k = map(int,input().split())
a = sorted(list(map(int,input().split())),reverse=True)
b = sorted(list(map(int,input().split())),reverse=True)
c = sorted(list(map(int,input().split())),reverse=True)

r = []
for i in range(x):
  for j in range(y):
    for h in range(z):
      if (i+1)*(j+1)*(h+1) > k:
                break
      r.append(a[i]+b[j]+c[h])
list.sort(r,reverse=True)
for i in range(k):
  print(r[i])
Buggy python submission (verdict: Runtime Error):
n = input()
a  list(map(int,input().split()))

a = sorted(a)

if sum(a[0:-1]) > a[-1]:
  print("No")
else:
  print("Yes")


Fixed submission:
n = input()
a = list(map(int,input().split()))

a = sorted(a)

if sum(a[0:-1]) <= a[-1]:
  print("No")
else:
  print("Yes")

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

a = sorted(a)

if sum(a[0:-2]) > a[-1]:
  print("No")
else:
  print("Yes")

Fixed submission:
n = input()
a = list(map(int,input().split()))

a = sorted(a)

if sum(a[0:-1]) <= a[-1]:
  print("No")
else:
  print("Yes")
Buggy python submission (verdict: Runtime Error):
N = int(input())
dp = [[0 for _ in range(N+1)] for i in range(3)]

for i in range(1,N+1):
  ai,bi,ci = map(int,input().split())
  
  dp[i][0] = ai + max(dp[i-1][1],dp[i-1][2])
  dp[i][1] = bi + max(dp[i-1][0],dp[i-1][2])
  dp[i][2] = ci + max(dp[i-1][1],dp[i-1][0])
  
print(max(dp[N]))
  

Fixed submission:
N = int(input())
dp = [[0 for i in range(3)] for _ in range(N+1)] 

for i in range(1,N+1):
  ai,bi,ci = map(int,input().split())
  
  dp[i][0] = ai + max(dp[i-1][1],dp[i-1][2])
  dp[i][1] = bi + max(dp[i-1][0],dp[i-1][2])
  dp[i][2] = ci + max(dp[i-1][1],dp[i-1][0])
  
print(max(dp[N]))
Buggy python submission (verdict: Time Limit Exceeded):
N,W = map(int,input().split())

dp = [[None for _ in range(N+1)] for _ in range(W+1)]

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

def f(dp,wleft,index):
  if index > N:
    return 0
  if dp[wleft][index] is not None:
    return dp[wleft][index]
  
  if wleft < items[index-1][0]:
    return f(dp,wleft,index+1)
  dp[wleft][index] = max(f(dp,wleft,index+1),items[index-1][1]+f(dp,wleft-items[index-1][0],index+1))
  return dp[wleft][index]
  
print(f(dp,W,1))


Fixed submission:
import numpy as np
N,W = map(int, input().split())
# np.maximum https://www.sejuku.net/blog/69175
# 第一引数と第二引数の大小関係を要素ごとに比較して、大きい方を格納した配列を返す
dp = np.zeros(W+1, dtype=np.int64)
# その重さでの最大valueが保存されている
for _ in range(N):
    w,v = map(int,input().split())
    # w以下ならvを足したもの、w以上ならそのままの値で、最大値を求める
    # 出力はw以上の配列として返す(それ以下は重さwなので関与しない)
    # 足す場合が前者、足さない場合が後者
    np.maximum(dp[:W-w+1]+v,dp[w:],out=dp[w:]) 

print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
N,W = map(int,input().split())

dp = [[None for _ in range(N+1)] for _ in range(W+1)]

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

def f(dp,wleft,index):
  if index > N:
    return 0
  if dp[wleft][index] is not None:
    return dp[wleft][index]
  
  if wleft < items[index-1][0]:
    return f(dp,wleft,index+1)
  
  return max(f(dp,wleft,index+1),items[index-1][1]+f(dp,wleft-items[index-1][0],index+1))
  
print(f(dp,W,1))


Fixed submission:
import numpy as np
N,W = map(int, input().split())
# np.maximum https://www.sejuku.net/blog/69175
# 第一引数と第二引数の大小関係を要素ごとに比較して、大きい方を格納した配列を返す
dp = np.zeros(W+1, dtype=np.int64)
# その重さでの最大valueが保存されている
for _ in range(N):
    w,v = map(int,input().split())
    # w以下ならvを足したもの、w以上ならそのままの値で、最大値を求める
    # 出力はw以上の配列として返す(それ以下は重さwなので関与しない)
    # 足す場合が前者、足さない場合が後者
    np.maximum(dp[:W-w+1]+v,dp[w:],out=dp[w:]) 

print(dp[-1])
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
import math


def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


def main():
    N, M, K = map(int, input().split())
    const = 998244353

    def hoge(k):
        return comb(N - 1, k) * M * ((M - 1) ** (N - k - 1))

    ans = sum([hoge(k) for k in range(K + 1)])

    print(ans % const)


if __name__ == '__main__':
    main()


Fixed submission:
import math
from collections import defaultdict


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    visited = [-1 for _ in range(N)]
    visited[0] = 0

    current = 0
    th = -1
    per_loop = -1
    for i in range(1, N+1):
        current = A[current] - 1

        if visited[current] >= 0:
            # print(i, current, visited[current])
            per_loop = i - visited[current]
            th = visited[current]
            break
        else:
            visited[current] = i

    current = 0
    # print(th, per_loop)

    if K < th:
        num_rep = K
    else:
        num_rep = th + (K - th) % per_loop

    for i in range(num_rep):
        current = A[current] - 1

    print(current + 1)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import math
from collections import defaultdict


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    #
    # visited = [-1 for _ in range(N)]
    # visited[0] = 0
    #
    # current = 0
    # th = -1
    # per_loop = -1
    # for i in range(1, N):
    #     current = A[current] - 1
    #
    #     if visited[current] >= 0:
    #         # print(i, current, visited[current])
    #         per_loop = i - visited[current]
    #         th = visited[current]
    #         break
    #     else:
    #         visited[current] = i
    #
    # current = 0
    # # print(th, per_loop)
    # # print(th + (K - th) % per_loop)
    #
    # if th < 0:
    #     num_rep = K
    # else:
    #     num_rep = th + (K - th) % per_loop
    #
    # for i in range(num_rep):
    #     current = A[current] - 1
    #
    # print(current + 1)

    current = 0
    for i in range(K):
        current = A[current] - 1

    print(current + 1)


if __name__ == '__main__':
    main()


Fixed submission:
import math
from collections import defaultdict


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    visited = [-1 for _ in range(N)]
    visited[0] = 0

    current = 0
    th = -1
    per_loop = -1
    for i in range(1, N+1):
        current = A[current] - 1

        if visited[current] >= 0:
            # print(i, current, visited[current])
            per_loop = i - visited[current]
            th = visited[current]
            break
        else:
            visited[current] = i

    current = 0
    # print(th, per_loop)

    if K < th:
        num_rep = K
    else:
        num_rep = th + (K - th) % per_loop

    for i in range(num_rep):
        current = A[current] - 1

    print(current + 1)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import math


def main():
    N = int(input())
    A = list(map(int, input().split()))
    minus_A_plus_i = tuple([- A[i] + (i+1) for i in range(N)])
    A_plus_i = tuple([A[i] + (i+1) for i in range(N)])

    c = 0

    for item in minus_A_plus_i:
        c += A_plus_i.count(item)

    print(c)


if __name__ == '__main__':
    main()


Fixed submission:
import math
from collections import defaultdict


def main():
    N = int(input())
    A = list(map(int, input().split()))
    minus_A_plus_i = tuple([- A[i] + (i+1) for i in range(N)])
    A_plus_i = tuple([A[i] + (i+1) for i in range(N)])

    cnt = defaultdict(int)
    for e in minus_A_plus_i:
        cnt[e] += 1

    c = 0

    for item in A_plus_i:
        c += cnt[item]

    print(c)


if __name__ == '__main__':
    main()