Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
#区間ごとの面積を計算する
def calc_area(v_end, v_start, v_max, dt):
    kouten_v = (v_end + v_start + dt) / 2
    kouten_t = kouten_v - v_start
    if 0 < kouten_t < dt:
        area = (v_start + kouten_v) * kouten_t / 2 #左側
        area +=  (v_end + kouten_v) * (dt - kouten_t) / 2 #右側
        area -=  max(0, (kouten_v - v_max))** 2 #上の三角形
    else:
        area = (v_start + v_end) *  dt / 2
    return area

def main():
    #与えられた入力を受け取る
    n=int(input())
    t=[int(i) for i in input().split()]
    v=[int(i) for i in input().split()]

    #各区間の許容最大速度を計算する
    #（この段階では傾きが-1未満になる可能性がある）
    max_velocity = [0]
    for i in range(1, n):
        max_velocity_ = min(v[i-1], v[i], max_velocity[i-1] + t[i-1])
        max_velocity.append(max_velocity_)
    max_velocity.append(0)

    #後ろから走査して、傾きが-1以上を満たすように許容速度をfittingする
    for i in range(n-1):
        if  max_velocity[-(i+1)] - max_velocity[-(i+2)] < -t[-(i+1)]:
            max_velocity[-(i+2)] = max_velocity[-(i+1)] + t[-(i+1)]

    #各区間の面積を計算して足し合わせる
    ans = 0
    for i in range(n):
        ans += calc_area(max_velocity[i+1], max_velocity[i], v[i], t[i])
    print(ans)

main()

Fixed submission:
a=int(input())
b=int(input())

print(a+2*(b-a))
Buggy python submission (verdict: Time Limit Exceeded):
def calc_area(v_end, v_start, v_max, dt):
    kouten_v = (v_end + v_start + dt) / 2
    kouten_t = kouten_v - v_start
    kouten_t_limit1 = max(v_max - v_start, 0)
    kouten_t_limit2 = min(v_end + dt - v_max, dt)
    if 0 < kouten_t < dt:
        area = (v_start + kouten_v) * kouten_t / 2
        area +=  (v_end + kouten_v) * (dt - kouten_t) / 2
        area -=  (kouten_t_limit2  - kouten_t_limit1) * max(0, (kouten_v - v_max)) / 2
    else:
        area = (v_start + v_end) *  dt / 2
    return area

n=int(input())
t=[int(i) for i in input().split()]
v=[int(i) for i in input().split()]

max_velocity = [0]
for i in range(1, n):
    max_velocity_ = min(v[i-1], v[i], max_velocity[i-1] + t[i-1], sum(t) - sum(t[:i]))
    max_velocity.append(max_velocity_)
max_velocity.append(0)

ok = 0
while ok==0:
    for i in range(n-1):
        if  abs((max_velocity[i+1]-max_velocity[i])/t[i]) >1:
                max_velocity[i]=max_velocity[i]-1
                max_velocity[i+1]=max_velocity[i+1]-1
                break
    else:
        ok=1



ans = 0
for i in range(n):
    ans += calc_area(max_velocity[i+1], max_velocity[i], v[i], t[i])
print(ans)

Fixed submission:
n=int(input())
t=[int(i) for i in input().split()]
v=[int(i) for i in input().split()]
S=[0 for i in range(n)]
S1=[0 for i in range(n)]
S2=[0 for i in range(n)]
vel=[0 for i in range(n)]

dt=[0 for i in range(n)]
v0=[0 for i in range(n)]
ve=[0 for i in range(n)]
ok=0



for i in range(n):
    if n ==1:
        dt[0]=t[0]
    elif i==n-1:
        v0[i]=ve[i-1]
        ve[i]=0
        dt[i]=t[i]
    else:
        v0[i]=ve[i-1]
        dt[i]=t[i]
        ve[i]=min(v[i+1],v[i],v0[i]+dt[i])

#print(dt)
#print(v0)
#print(ve)

while ok==0:
    for i in range(n-1):
#        if  abs((ve[i]-ve[i+1])/dt[i+1]) >1:
        if  abs((ve[i+1]-v0[i+1])/dt[i+1]) >1:
                ve[i]=ve[i]-1
                v0[i+1]=v0[i+1]-1
#                v0[i]=v0[i]-1
#                print("dt",dt)
#                print("v0",v0)
#                print("ve",ve)
                break
    else:
        ok=1


#print(dt)
#print(v0)
#print(ve)


for i in range(n):

    ttt=0.5*(ve[i]+dt[i]-v0[i])
    vvv=ttt+v0[i]
    if vvv-v[i]>=0:
        S[i]=0.5*(v0[i]+vvv)*ttt + 0.5*(ve[i]+vvv)*(dt[i]-ttt) - (ttt-v[i]+v0[i])*(vvv-v[i]) 
        S1[i]=0.5*(v0[i]+vvv)*ttt + 0.5*(ve[i]+vvv)*(dt[i]-ttt)
        S2[i]=(ttt-v[i]+v0[i])*(vvv-v[i]) 
    else:
        S[i]=0.5*(v0[i]+vvv)*ttt + 0.5*(ve[i]+vvv)*(dt[i]-ttt)
        S1[i]=0.5*(v0[i]+vvv)*ttt + 0.5*(ve[i]+vvv)*(dt[i]-ttt)
        S2[i]=0

print(sum(S))
Buggy python submission (verdict: Runtime Error):
a,b,c,d,e,f= map(int, input().split())
youeki=0
yousitu=0
noudo=0
n_a=int(f/(100*a))


for i in range(2+n_a):
 for j in range(2+int((f-100*i*a)/(100*b))):
  for k in range(2+int((f-100*i*a-100*j*b)/c)):
   for l in range(2+int((f-100*i*a-100*j*b-k*c)/d)):
    S=100.0*a*i+100.0*b*j+c*k+d*l
    T=c*k+d*l
    if S!=0:
     L=100.0*T/S
     if S<=f and L<=100*e/(100+e) and L>noudo:
      noudo=L
      youeki=S
      yousitu=T
print(int(youeki),int(yousitu))


Fixed submission:
N=int(input())
a=int(input())

print(N**2-a)

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

print(N**2-A)

Fixed submission:
N=int(input())
a=int(input())

print(N**2-a)
Buggy python submission (verdict: Runtime Error):
a,b,c,d,e,f= map(int, input().split())
2.youeki=0
3.yousitu=0
4.noudo=0
5.n_a=int(f/(100*a))
6. 
7. 
8.for i in range(1+n_a):
9. for j in range(1+int((f-100*i*a)/(100*b))):
10.  for k in range(1+int((f-100*i*a-100*j*b)/c)):
11.   for l in range(1+int((f-100*i*a-100*j*b-k*c)/d)):
12.    S=100.0*a*i+100.0*b*j+c*k+d*l
13.    T=c*k+d*l
14.    if S!=0:
15.     L=100.0*T/S
16.     if S<=f and L<=100*e/(100+e) and L>=noudo:
17.      noudo=L
18.      youeki=S
19.      yousitu=T
20.print(int(youeki),int(yousitu))


Fixed submission:
a,b,c,d,e,f= map(int, input().split())
youeki=0
yousitu=0
noudo=0
n_a=int(f/(100*a))


for i in range(2+n_a):
 for j in range(2+int((f-100*i*a)/(100*b))):
  for k in range(2+int((f-100*i*a-100*j*b)/c)):
   for l in range(2+int((f-100*i*a-100*j*b-k*c)/d)):
    S=100.0*a*i+100.0*b*j+c*k+d*l
    T=c*k+d*l
    if S!=0:
     L=100.0*T/S
     if S<=f and L<=100*e/(100+e) and L>=noudo:
      noudo=L
      youeki=S
      yousitu=T
print(int(youeki),int(yousitu))
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=[int(input()) for i in range(n)]
b=[]
count=0

for i in a: 
    if i not in b:
        b.append(i)

for i in b:
    if a.count(i)%2==1:
        count=count+1

print(count)


Fixed submission:
n=int(input())
a=[int(input()) for i in range(n)]
b=[]

m=0
count=[0 for i in range(n)]
count[m]=1

ans_count=0
a.sort()

for i in range(n-1):
    if a[m]==a[i+1]:
        count[m]=count[m]+1
    else:
        m=i+1
        count[m]=1

for i in range(n):
     ans_count=ans_count+count[i]%2

print(ans_count)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=[int(input()) for i in range(n)]
b=[]
count=0

for i in a: 
    if i not in b:
        b.append(i)

for i in b:
    if a.count(i)%2==1:
        count=count+1

print(count)


Fixed submission:
n=int(input())
a=[int(input()) for i in range(n)]
b=[]

m=0
count=[0 for i in range(n)]
count[m]=1

ans_count=0
a.sort()

for i in range(n-1):
    if a[m]==a[i+1]:
        count[m]=count[m]+1
    else:
        m=i+1
        count[m]=1

for i in range(n):
     ans_count=ans_count+count[i]%2

print(ans_count)
Buggy python submission (verdict: Runtime Error):
n,m=[int(i) for i in input().split()]
p=[[0 for i in range(2)] for j in range(n)]
a=[0 for i in range(n+1)]

for i in range(m):
  p[i]=[int(i) for i in input().split()]

for i in range(m):  
  
  if p[i][0]==1:
    a[p[i][1]]+=1
    
  elif p[i][1]==n:
    a[p[i][0]]+=1
   
    
if max(a)>=2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Fixed submission:
n,m=[int(i) for i in input().split()]
p=[[0 for i in range(2)] for j in range(m)]

a=[0 for i in range(n+1)]
b=[0 for i in range(n+1)]

for i in range(m):
  p[i]=[int(i) for i in input().split()]

for i in range(m):  
  
  if p[i][0]==1:
    a[p[i][1]]+=1
    
  elif p[i][1]==n:
    a[p[i][0]]+=1
   
    
if max(a)>=2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Buggy python submission (verdict: Runtime Error):
n,m=[int(i) for i in input().split()]
p=[[0 for i in range(2)] for j in range(n)]

for i in range(m):
  p[i]=[int(i) for i in input().split()]
  
  
#隣接リスト  
l = [[] for i in range(n+1)]
for pi in p:  #0-originedに注意、l[0]は空
        l[pi[0]].append(pi[1])
        l[pi[1]].append(pi[0])  

count=0
for i in l[1]:
  if i in l[n]:
    count=1
    
if count==1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
      

Fixed submission:
n,m=[int(i) for i in input().split()]
p=[[0 for i in range(2)] for j in range(m)]

a=[0 for i in range(n+1)]
b=[0 for i in range(n+1)]

for i in range(m):
  p[i]=[int(i) for i in input().split()]

for i in range(m):  
  
  if p[i][0]==1:
    a[p[i][1]]+=1
    
  elif p[i][1]==n:
    a[p[i][0]]+=1
   
    
if max(a)>=2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Buggy python submission (verdict: Runtime Error):
n,m=[int(i) for i in input().split()]
p=[[0 for i in range(2)] for j in range(n)]

for i in range(m):
  p[i]=[int(i) for i in input().split()]
  
  
#隣接リスト  
l = [[] for i in range(n+1)]
for pi in p:  #0-originedに注意、l[0]は空
        l[pi[0]].append(pi[1])
        l[pi[1]].append(pi[0])  

count=0
for i in l[1]:
  if i in l[n]:
    count=1
    
if count==1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
      

Fixed submission:
n,m=[int(i) for i in input().split()]
p=[[0 for i in range(2)] for j in range(m)]

a=[0 for i in range(n+1)]
b=[0 for i in range(n+1)]

for i in range(m):
  p[i]=[int(i) for i in input().split()]

for i in range(m):  
  
  if p[i][0]==1:
    a[p[i][1]]+=1
    
  elif p[i][1]==n:
    a[p[i][0]]+=1
   
    
if max(a)>=2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
Buggy python submission (verdict: Runtime Error):
N=int(input())
a=[int(i) for i in input().split()]
X=0
Y=0
min=10**11
for i in range(N):
  X=X+a[i]

for j in range(N-1):
  Y=Y+a[j]
  if abs(X-2*Y) <= min:
   min=abs(X-2*Y)
print(min)


Fixed submission:
m,d = [ int(i) for i in input().split()]

if m%3==0 or d%3==0 or (m+d)%3==0 :
    print("Possible")
else:
    print("Impossible")
Buggy python submission (verdict: Runtime Error):
#import sys
#import numpy as np
from scipy.sparse import csr_matrix, coo_matrix
from scipy.sparse.csgraph import dijkstra, bellman_ford

#sys.setrecursionlimit(10000)

N, M = [int(i) for i in input().split()]

rows = []
cols = []
weights = []

for _ in range(M):
    # u v 間のコスト
    u, v, a = [int(i) for i in input().split()]
    rows.append(u-1)
    cols.append(v-1)
    weights.append(-a)

#graph = coo_matrix((weights, (rows, cols)), shape=(N, N)).tocsr()
graph = coo_matrix((weights, (cols, rows)), shape=(N, N)).tocsr() #N→1

d1 = bellman_ford(graph, indices = [N-1], directed=True, unweighted=False)
#print(d1)
print(-int(d1[0][0]))



Fixed submission:
#import sys
#import numpy as np
from scipy.sparse import csr_matrix, coo_matrix
from scipy.sparse.csgraph import dijkstra, bellman_ford

#sys.setrecursionlimit(10000)

N, M = [int(i) for i in input().split()]

rows = []
cols = []
weights = []

for _ in range(M):
    # u v 間のコスト
    u, v, a = [int(i) for i in input().split()]
    rows.append(u-1)
    cols.append(v-1)
    weights.append(-a)

#graph = coo_matrix((weights, (rows, cols)), shape=(N, N)).tocsr()
graph = coo_matrix((weights, (cols, rows)), shape=(N, N)).tocsr() #N→1
try:
    d1 = bellman_ford(graph, indices = [N-1], directed=True, unweighted=False)
    print(-int(d1[0][0]))
except:
    print("inf")
Buggy python submission (verdict: Time Limit Exceeded):
k,s=[int(i) for i in input().split()]
count=0
for y in range(k+1):
 for x in range(k+1):
   if x + y <= s + k and s>=x+y and s<=k+x+y:
      count=count+1
print(count)


Fixed submission:
k,s=[int(i) for i in input().split()]
count=0
for y in range(k+1):
 for x in range(k+1):
   if x + y <= s + k and s>=x+y and s<=k+x+y:
      count=count+1
print(count)

Buggy python submission (verdict: Time Limit Exceeded):
k,s=[int(i) for i in input().split()]
count=0
#print(k,s)
for y in range(k+1):
 for x in range(k+1):
   if x + y <= s + k and s-x-y>=0 and s-x-y<=k:
#      print(x,y,s-x-y)
      count=count+1
print(count)


Fixed submission:
k,s=[int(i) for i in input().split()]
count=0
for y in range(k+1):
 for x in range(k+1):
   if x + y <= s + k and s>=x+y and s<=k+x+y:
      count=count+1
print(count)
Buggy python submission (verdict: Time Limit Exceeded):
import itertools
h, w = [int(i) for i in input().split()]
a = [input() for i in range(h)]

for way in itertools.permutations([1 for i in range(h - 1)] + [-1 for i in range(w - 1)]):
    k = 0
    l = 0
    ij_list =[[k, l]]
    for way_route in way:
        k += (way_route == 1)
        l += (way_route == -1)
        ij_list.append([k, l])

    for i, j in itertools.product(range(h), range(w)):
            if [i, j] not in ij_list:
                if a[i][j] != ".":
                    break
            else:
                if a[i][j] != "#":
                    break
    else:
        print("Possible")
        break

else:
    print("Impossible")

Fixed submission:
h, w = [int(i) for i in input().split()]
a = [input().count("#") for i in range(h)]
print(["Impossible", "Possible"][sum(a) == h + w - 1])

Buggy python submission (verdict: Time Limit Exceeded):
import itertools
h, w = [int(i) for i in input().split()]
a = [input() for i in range(h)]

for way in itertools.permutations([1 for i in range(h - 1)] + [-1 for i in range(w - 1)]):
    k = 0
    l = 0
    ij_list =[[k, l]]
    for way_route in way:
        k += (way_route == 1)
        l += (way_route == -1)
        ij_list.append([k, l])

    for i, j in itertools.product(range(h), range(w)):
            if [i, j] not in ij_list:
                if a[i][j] != ".":
                    break
            else:
                if a[i][j] != "#":
                    break
    else:
        print("Possible")
        break

else:
    print("Impossible")

Fixed submission:
h, w = [int(i) for i in input().split()]
a = [input().count("#") for i in range(h)]
print(["Impossible", "Possible"][sum(a) == h + w - 1])
Buggy python submission (verdict: Runtime Error):
S=input()
a=0
for i in range(len(S)-1):
  if S[i]==S[i+1] or S[i]==S[i+2] :
    a=1
    print(i+1,i+3)
    break
if a==0:
    print(-1,-1)

Fixed submission:
S=input()
a=0
for i in range(len(S)-2):
  if S[i]==S[i+1] or S[i]==S[i+2] or S[i+1]==S[i+2]:
    a=1
    print(i+1,i+3)
    break

if a==0:
 if len(S)>1 and S[-1]==S[-2]:
  print(len(S)-1,len(S))
 else:
  print(-1,-1)
Buggy python submission (verdict: Runtime Error):
h,w,m,*t = map(int,open(0).read().split())
a = [[0]*w for _ in range(h)]
ht = [0]*h
wt = [0]*w
for i in range(m):
  y,x = t[i*2]-1,t[i*2+1]-1
  a[y][x] += 1
  ht[y] += 1
  wt[x] += 1
htm = max(ht)
wtm = max(wt)
htt = [i for i in range(h) if ht[i]==htm]
wtt = [i for i in range(w) if wt[i]==wtm]
ans = htm+wtm-1
for i in htt:
  for j in wtt:
    if a[i][j] == 0:
      print(ans + 1)
      exit()
print(ans)

Fixed submission:
h,w,m = map(int,input().split())
t = [tuple(map(lambda x:int(x)-1,input().split())) for _ in range(m)] 
ht = [0]*h
wt = [0]*w
for y,x in t:
  ht[y] += 1
  wt[x] += 1
htm = max(ht)
wtm = max(wt)
htt = [i for i in range(h) if ht[i]==htm]
wtt = [i for i in range(w) if wt[i]==wtm]
ans = htm+wtm-1
t = set(t)
for i in htt:
  for j in wtt:
    if (i,j) not in t:
      print(htm+wtm)
      exit()
print(htm+wtm-1)

Buggy python submission (verdict: Runtime Error):
h,w,m,*t = map(int,open(0).read().split())
a = [[0]*w for _ in range(h)]
ht = [0]*h
wt = [0]*w
for i in range(m):
  y,x = t[i*2]-1,t[i*2+1]-1
  a[y][x] += 1
  ht[y] += 1
  wt[x] += 1
htm = max(ht)
wtm = max(wt)
htt = [i for i in range(h) if ht[i]==htm]
wtt = [i for i in range(w) if wt[i]==wtm]
ans = 0
for i in htt:
  for j in wtt:
    ans = max(ans,ht[i]+wt[j]-a[i][j])
print(ans)

Fixed submission:
h,w,m = map(int,input().split())
t = [tuple(map(lambda x:int(x)-1,input().split())) for _ in range(m)] 
ht = [0]*h
wt = [0]*w
for y,x in t:
  ht[y] += 1
  wt[x] += 1
htm = max(ht)
wtm = max(wt)
htt = [i for i in range(h) if ht[i]==htm]
wtt = [i for i in range(w) if wt[i]==wtm]
ans = htm+wtm-1
t = set(t)
for i in htt:
  for j in wtt:
    if (i,j) not in t:
      print(htm+wtm)
      exit()
print(htm+wtm-1)

Buggy python submission (verdict: Runtime Error):
h,w,m,*t = map(int,open(0).read().split())
a = [[0]*w for _ in range(h)]
ht = [0]*h
wt = [0]*w
for i in range(m):
  y,x = t[i*2]-1,t[i*2+1]-1
  a[y][x] += 1
  ht[y] += 1
  wt[x] += 1
htm = max(ht)-1
wtm = max(wt)-1
htt = [i for i in range(h) if ht[i]>=htm]
wtt = [i for i in range(w) if wt[i]>=wtm]
ans = 0
for i in htt:
  for j in wtt:
    ans = max(ans,ht[i]+wt[j]-a[i][j])
print(ans)

Fixed submission:
h,w,m = map(int,input().split())
t = [tuple(map(lambda x:int(x)-1,input().split())) for _ in range(m)] 
ht = [0]*h
wt = [0]*w
for y,x in t:
  ht[y] += 1
  wt[x] += 1
htm = max(ht)
wtm = max(wt)
htt = [i for i in range(h) if ht[i]==htm]
wtt = [i for i in range(w) if wt[i]==wtm]
ans = htm+wtm-1
t = set(t)
for i in htt:
  for j in wtt:
    if (i,j) not in t:
      print(htm+wtm)
      exit()
print(htm+wtm-1)
Buggy python submission (verdict: Runtime Error):
n,k,*a = map(int,open(0).read().split())
def func(b):
  c = k
  for i in a:
    c -= i//b
    if c < 0:
      return False
  return True
l = 0
r = max(a)
while(r>l):
  lr = (l+r)//2
  if func(lr):
    r = lr
  else:
    l = lr + 1
print(r)

Fixed submission:
n,k,*a = map(int,open(0).read().split())
def func(b):
  c = k
  for i in a:
    c -= (i-1)//b
    if c < 0:
      return False
  return True
l = 1
r = max(a)
while(r>l):
  lr = (l+r)//2
  if func(lr):
    r = lr
  else:
    l = lr + 1
print(r)
Buggy python submission (verdict: Time Limit Exceeded):
n,*a = map(int,open(0).read().split())
s = sorted(list(set(a)),reverse=True)
m = len(s)
ans = 0
for i in range(m):
  if a.count(s[i]) != 1:
    continue
  for j in range(i+1,m):
    if s[i]%s[j]==0:
      break
  else:
    ans+=1
print(ans)

Fixed submission:
from collections import Counter
n,*a = map(int,open(0).read().split())
s = set(a)
c = Counter(a)
m = max(s)
l = [True]*(m+1)
ans = 0
for i in range(1,m+1):
  if i in s and l[i]:
    if c[i] == 1:
      ans += 1
    for j in range(1,m//i+1):
      l[i*j] = False
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
n,*a = map(int,open(0).read().split())
c = Counter(a)
d = sorted(c.keys(),reverse=True)
m = len(d)
ans = 0
for i in range(m):
  if c[d[i]] != 1:
    continue
  for j in range(i+1,m):
    if d[i]%d[j]==0:
      break
  else:
    ans+=1
print(ans)

Fixed submission:
from collections import Counter
n,*a = map(int,open(0).read().split())
s = set(a)
c = Counter(a)
m = max(s)
l = [True]*(m+1)
ans = 0
for i in range(1,m+1):
  if i in s and l[i]:
    if c[i] == 1:
      ans += 1
    for j in range(1,m//i+1):
      l[i*j] = False
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int,input().split()))
ans = a[0]
for i in a[1:]:
  ans *= i
if ans > 10**18:
  print(-1)
else:
  print(ans)

Fixed submission:
n = int(input())
a = list(map(int,input().split()))
if 0 in a:
  print(0)
  exit()
ans = a[0]
for i in a[1:]:
  ans *= i
  if ans > 10**18:
    ans = -1
    break
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
t = int(input())
  
def solve(n,a,b,c,d):
  sol = [n*d]
  if n>=2:
    if n%2 == 0:
      sol.append(a+solve(n//2,a,b,c,d))
    else:
      sol.append(a+d+solve((n+1)//2,a,b,c,d))
      sol.append(a+d+solve((n-1)//2,a,b,c,d))
  if n>=3:
    if n%3 == 0:
      sol.append(b+solve(n//3,a,b,c,d))
    else:
      bd = n%3
      sol.append(b+bd*d+solve((n-bd)//3,a,b,c,d))
      sol.append(b+(3-bd)*d+solve((n-bd+3)//3,a,b,c,d))
  if n>=5:
    if n%5 == 0:
      sol.append(c+solve(n//5,a,b,c,d))
    else:
      cd = n%5
      sol.append(c+cd*d+solve((n-cd)//5,a,b,c,d))
      sol.append(c+(5-cd)*d+solve((n-cd+5)//5,a,b,c,d))
  return min(sol)

for _ in range(t):
  n,a,b,c,d = map(int,input().split())
  print(solve(n,a,b,c,d))

Fixed submission:
t = int(input())

def solve(n,a,b,c,d):
  mem = {0:0,1:d}
  def f(n):
    if n in mem:
      return mem[n]
    ret = n*d
    if n%2 == 0:
      ret = min(ret,a+f(n//2))
    else:
      ret = min(ret,a+d+f(n//2+1),a+d+f(n//2))
    
    if n%3 == 0:
      ret = min(ret,b+f(n//3))
    elif n%3 == 1:
      ret = min(ret,b+d+f(n//3))
    else:
      ret = min(ret,b+d+f(n//3+1))
    
    if n%5 == 0:
      ret = min(ret,c+f(n//5))
    elif n%5 == 1:
      ret = min(ret,c+d+f(n//5))
    elif n%5 == 2:
      ret = min(ret,c+d+d+f(n//5))
    elif n%5 == 3:
      ret = min(ret,c+d+d+f(n//5+1))
    else:
      ret = min(ret,c+d+f(n//5+1))
    mem[n] = ret
    return ret
  return f(n)
 
for _ in range(t):
  n,a,b,c,d = map(int,input().split())
  print(solve(n,a,b,c,d))
Buggy python submission (verdict: Time Limit Exceeded):
n,*x = map(int,open(0).read().split())
ans = 0
for i in range(n-1):
  for j in range(i+x[i]+1,n):
    if x[i] + x[j] == j - i :
      ans += 1
print(ans)

Fixed submission:
n,*x = map(int,open(0).read().split())
ans = 0
xr = {}
xl = {}
for i in range(n):
  xrt = i+x[i]
  if xrt < n:
    if xrt in xr:
      xr[xrt] += 1
    else:
      xr[xrt] = 1
  xlt = i-x[i]
  if xlt >= 0:
    if xlt in xl:
      xl[xlt] += 1
    else:
      xl[xlt] = 1
for i in xr.keys():
  if i in xl:
    ans += xr[i]*xl[i]
print(ans)
Buggy python submission (verdict: Runtime Error):
def main():
  s = input()
  n = len(s)
  num = 2019
  ans = 0
  for i in range(n-4):
    for j in range(i+5,n+1):
      a = int(s[i:j])
      if a%num == 0:
        ans += 1
  print(ans)
main()

Fixed submission:
s,w = map(int,input().split())
if w >= s:
  print("unsafe")
else:
  print("safe")
Buggy python submission (verdict: Time Limit Exceeded):
def main():
  s = input()
  n = len(s)
  num = 2019
  ans = 0
  for i in range(n-4):
    for j in range(i+5,n+1):
      a = int(s[i:j])
      if a%num == 0:
        ans += 1
  print(ans)
main()

Fixed submission:
def main():
  s = input()[::-1]
  l = len(s)
  n = 2019
  dp = [0]*n
  wk = 0
  r = 1
  for i in range(l):
    wk += int(s[i])*r
    wk %= n
    dp[wk] += 1
    r*= 10
    r %= n
  print(dp[0]+sum([i*(i-1)//2 for i in dp]))
main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
  s = input()
  n = len(s)
  num = 2019
  ans = 0
  for i in range(n-4):
    for j in range(i+5,n+1):
      a = int(s[i:j])
      if a%num == 0:
        ans += 1
  print(ans)
main()

Fixed submission:
def main():
  s = input()[::-1]
  l = len(s)
  n = 2019
  dp = [0]*n
  wk = 0
  r = 1
  for i in range(l):
    wk += int(s[i])*r
    wk %= n
    dp[wk] += 1
    r*= 10
    r %= n
  print(dp[0]+sum([i*(i-1)//2 for i in dp]))
main()

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
n = len(s)
num = 2019
ans = 0
for i in range(n-3):
  for j in range(i+4,n+1):
    a = int(s[i:j])
    if a%num == 0:
      ans += 1
print(ans)

Fixed submission:
def main():
  s = input()[::-1]
  l = len(s)
  n = 2019
  dp = [0]*n
  wk = 0
  r = 1
  for i in range(l):
    wk += int(s[i])*r
    wk %= n
    dp[wk] += 1
    r*= 10
    r %= n
  print(dp[0]+sum([i*(i-1)//2 for i in dp]))
main()
Buggy python submission (verdict: Time Limit Exceeded):
x,y,a,b,c = map(int,input().split())
p = sorted(list(map(int,input().split())),reverse=True)
q = sorted(list(map(int,input().split())),reverse=True)
r = sorted(list(map(int,input().split())),reverse=True)
ans = 0
for i in range(x,max(-1,x-c-1),-1):
  z = c-(x-i)
  for j in range(y,max(-1,y-1-z),-1):
    ans = max(ans,sum(p[:i])+sum(q[:j])+sum(r[:(x+y-i-j)]))
print(ans)

Fixed submission:
x,y,a,b,c = map(int,input().split())
p = sorted(list(map(int,input().split())),reverse=True)[:x]
q = sorted(list(map(int,input().split())),reverse=True)[:y]
r = list(map(int,input().split()))
print(sum(sorted(p+q+r,reverse=True)[:(x+y)]))
Buggy python submission (verdict: Time Limit Exceeded):
h,w = map(int,input().split())
s = [list(input()) for _ in range(h)]
def f(dh,dw):
  if s[dh][dw] == "#":
    a = 1
  else:
    a = 0
  if dh == h-1 and dw == w-1:
    return a
  elif dh == h-1:
    return a + f(dh,dw+1)
  elif dw == w-1:
    return a + f(dh+1,dw)
  else:
    return a + min(f(dh,dw+1),f(dh+1,dw))
print(f(0,0))

Fixed submission:
h,w = map(int,input().split())
s = [list(input()) for _ in range(h)]
dp = [[h*w]*w for _ in range(h)]
if s[0][0] == "#":
  dp[0][0] = 1
else:
  dp[0][0] = 0
for i in range(h):
  for j in range(w):
    if i < h-1:
      if s[i][j]=="." and s[i+1][j]=="#":
        dp[i+1][j] = min(dp[i+1][j],dp[i][j]+1)
      else:
        dp[i+1][j] = min(dp[i+1][j],dp[i][j])
    if j < w-1:
      if s[i][j]=="." and s[i][j+1]=="#":
        dp[i][j+1] = min(dp[i][j+1],dp[i][j]+1)
      else:
        dp[i][j+1] = min(dp[i][j+1],dp[i][j])
print(dp[h-1][w-1])