Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
from math import gcd
g=[201*[0]for _ in range(201)]
for i in range(1,201):
  for j in range(i,201):
    g[i][j]=gcd(i,j)
ans=0
for i in range(1,201):
  for j in range(1,201):
    for k in range(1,201):
      m=g[min(i,j)][max(i,j)]
      ans+=g[min(k,m)][max(k,m)]
print(ans)


Fixed submission:
def gcd(a,b):
  while b:a,b=b,a%b
  return a
k=int(input())
ans=0
for i in range(1,k+1):
  for j in range(1,k+1):
    for k in range(1,k+1):
      ans+=gcd(i,gcd(j,k))
print(ans)

Buggy python submission (verdict: Runtime Error):
from math import gcd
g=[201*[0]for _ in range(201)]
for i in range(1,201):
  for j in range(i,201):
    g[i][j]=gcd(i,j)
ans=0
for i in range(1,201):
  for j in range(1,201):
    for k in range(1,201):
    m=g[min(i,j)][max(i,j)]
    ans+=g[min(k,m)][max(k,m)]
print(ans)

Fixed submission:
def gcd(a,b):
  while b:a,b=b,a%b
  return a
k=int(input())
ans=0
for i in range(1,k+1):
  for j in range(1,k+1):
    for k in range(1,k+1):
      ans+=gcd(i,gcd(j,k))
print(ans)
Buggy python submission (verdict: Runtime Error):
n,*l=open(0);n=int(n);l=list(map(int,l.split()))
p=[0]*n;d=[0]*n
for i in range(n):p[i]=l[i]+p[i-2];d[i]=max(p[i-1]if(i&1)else d[i-1],l[i]+d[i-2])
print(d[-1])

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
if n<=3:print(max(a));exit()
if n&1:
  dp=[3*[-(10**20)]for _ in range(n)]
  dp[0][0]=a[0]
  for i in range(1,n):
    if i%2==0:
      dp[i][0]=dp[i-2][0]+a[i]
      if i>=3:dp[i][2]=max(dp[i-2][2]+a[i],dp[i-3][1]+a[i])
      else:dp[i][2]=a[i]
    else:
      if i>=3:dp[i][1]=max(dp[i-2][1]+a[i],dp[i-3][0]+a[i])
      else:dp[i][1]=a[i]
  print(max(dp[-1][2],dp[-2][1],dp[-3][0]))
else:
  b=[a[0]]
  c=[a[1]]
  for i in range(2,n):
    if i%2==0:b.append(b[-1]+a[i])
    else:c.append(c[-1]+a[i])
  ans=max(b[-1],c[-1])
  for i in range(n//2-1):
    ans=max(ans,b[i]+c[-1]-c[i])
  print(ans)

Buggy python submission (verdict: Runtime Error):
n,*l=open(0);n=int(n);l=list(map(int,l))
p=[0]*n;d=[0]*n
for i in range(n):p[i]=l[i]+p[i-2];d[i]=max(p[i-1]if(i&1)else d[i-1],l[i]+d[i-2])
print(d[-1])

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
if n<=3:print(max(a));exit()
if n&1:
  dp=[3*[-(10**20)]for _ in range(n)]
  dp[0][0]=a[0]
  for i in range(1,n):
    if i%2==0:
      dp[i][0]=dp[i-2][0]+a[i]
      if i>=3:dp[i][2]=max(dp[i-2][2]+a[i],dp[i-3][1]+a[i])
      else:dp[i][2]=a[i]
    else:
      if i>=3:dp[i][1]=max(dp[i-2][1]+a[i],dp[i-3][0]+a[i])
      else:dp[i][1]=a[i]
  print(max(dp[-1][2],dp[-2][1],dp[-3][0]))
else:
  b=[a[0]]
  c=[a[1]]
  for i in range(2,n):
    if i%2==0:b.append(b[-1]+a[i])
    else:c.append(c[-1]+a[i])
  ans=max(b[-1],c[-1])
  for i in range(n//2-1):
    ans=max(ans,b[i]+c[-1]-c[i])
  print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
class CumulativeSum2D:
  def __init__(self,a):
    self.h=len(a)
    self.w=len(a[0])
    self.s=[(self.w+1)*[0]for _ in range(self.h+1)]
    for i in range(self.h):
      for j in range(self.w):
        self.s[i+1][j+1]=self.s[i+1][j]+self.s[i][j+1]-self.s[i][j]+a[i][j]
  def su(self,i1,j1,i2,j2):
    return self.s[i2+1][j2+1]-self.s[i1][j2+1]-self.s[i2+1][j1]+self.s[i1][j1]
  def prin(self):
    for i in self.s:print(i)
h,w,kk=map(int,input().split())
b=[list(map(int,list(input())))for _ in range(h)]
h-=1
bs=CumulativeSum2D(b)
ans=h+w-1
for i in range(2**h):
  bi=[-1]+[j for j in range(h)if(1<<j)&i]+[h]
  anss=len(bi)-2
  flag=False
  cut=[0]
  for k in range(w):
    for j in range(len(bi)-1):
      up=bi[j]+1
      down=bi[j+1]
      s=bs.su(up,cut[-1],down,k)
      if s>kk:
        if k==cut[-1]:flag=True
        else:cut.append(k);anss+=1
        break
    if flag:break
  if flag:continue
  ans=min(ans,anss)
print(ans)

Fixed submission:
class CumulativeSum2D:
  def __init__(self,a):
    self.h=len(a)
    self.w=len(a[0])
    self.s=[(self.w+1)*[0]for _ in range(self.h+1)]
    for i in range(self.h):
      for j in range(self.w):
        self.s[i+1][j+1]=self.s[i+1][j]+self.s[i][j+1]-self.s[i][j]+a[i][j]
  def su(self,i1,j1,i2,j2):
    return self.s[i2+1][j2+1]-self.s[i1][j2+1]-self.s[i2+1][j1]+self.s[i1][j1]
  def prin(self):
    for i in self.s:print(i)
h,w,kk=map(int,input().split())
b=[list(map(int,list(input())))for _ in range(h)]
h-=1
bs=CumulativeSum2D(b)
ans=h+w-1
for i in range(2**h):
  bi=[-1]+[j for j in range(h)if(1<<j)&i]+[h]
  anss=len(bi)-2
  flag=False
  cut=[0]
  for k in range(w):
    for j in range(len(bi)-1):
      up=bi[j]+1
      down=bi[j+1]
      s=bs.su(up,cut[-1],down,k)
      if s>kk:
        if k==cut[-1]:flag=True
        else:cut.append(k);anss+=1
        break
    if flag:break
  if flag:continue
  ans=min(ans,anss)
print(ans)
Buggy python submission (verdict: Runtime Error):
n,s=map(int,input().split())
a=list(map(int,input().split()))
dp=[0]*6007
ans=0
for i in range(n):
  for j in range(s,0,-1):dp[a[i]+j]+=dp[j]
  d[a[i]]+=i
  ans+=d[s]
print(ans%998244353)

Fixed submission:
n,s=map(int,input().split())
a=list(map(int,input().split()))
dp=[0]*6007
ans=0
for i in range(n):
  for j in range(s,0,-1):dp[a[i]+j]+=dp[j]
  dp[a[i]]+=i+1
  ans+=dp[s]
print(ans%998244353)

Buggy python submission (verdict: Runtime Error):
n,s=map(int,input().split())
dp=[[0]*(s+1) for _ in range(n)]
a=list(map(int,input().split()))
if s>=a[0]:dp[0][a[0]]=1
for i in range(1,n):
  if s>=a[0]:dp[i][a[i]]=i+1
  for j in range(s+1):
    dp[i][j]+=dp[i-1][j]
    if j-a[i]>=0:dp[i][j]+=dp[i-1][j-a[i]]
print(sum(dp[i][s]for i in range(n)))

Fixed submission:
n,s=map(int,input().split())
a=list(map(int,input().split()))
dp=[0]*6007
ans=0
for i in range(n):
  for j in range(s,0,-1):dp[a[i]+j]+=dp[j]
  dp[a[i]]+=i+1
  ans+=dp[s]
print(ans%998244353)
Buggy python submission (verdict: Runtime Error):
import sys;input=sys.stdin.readline
n=int(input())
s=input()
num=2**(n-1).bit_length()
def segfunc(x,y):return x|y
seg=[0]*(2*num-1)
for i in range(n):seg[i+num-1]=2**(ord(s[i])-97)
for i in range(num-2,-1,-1):seg[i]=segfunc(seg[2*i+1],seg[2*i+2])
def update(i,x):
  i+=num-1;seg[i]=x
  while i:i=(i-1)//2;seg[i]=segfunc(seg[i*2+1],seg[i*2+2])
def query(l,r):
  l+=num-1;r+=num-1
  if l==r:return seg[l]
  s=seg[l];l+=1
  while r-l>1:
    if ~l%2:s=segfunc(seg[l],s)
    if r%2:s=segfunc(seg[r],s);r-=1
    l//=2;r=(r-1)//2
  if l==r:return segfunc(s,seg[l])
  return segfunc(s,segfunc(seg[l],seg[r]))
for _ in range(int(input())):
  quer=input().split()
  if quer[0]=="1":
    _,i,c=quer
    update(int(i)-1,2**(ord(c)-97))
  else:
    _,l,r=quer
    print(sum(map(int,bin(query(int(l)-1,int(r)-1))[2:])))

Fixed submission:
# じょえチャンネルおもしろいよ～～～
# https://www.youtube.com/channel/UCRXsI3FL_kvaVL9zoolBfbQ

Hitachi="Hitachi"
hitachi="hitachi"

s=input()
if "hi"*(len(s)//2)==s:print("Yes")
else:print("No")
Buggy python submission (verdict: Time Limit Exceeded):
n,p=map(int,input().split())
s=list(map(int,list(input()[::-1])))
if p in [2,5]:
  ans=0
  for i in range(n):
    if s[-i-1]%p==0:ans+=i+1
  print(ans)
  exit()
from collections import defaultdict
d=defaultdict(int)
t=0
d[t]+=1
for i in range(n):
  t+=(10**i)*s[i]
  t%=p
  d[t]+=1
print(sum(d[i]*(d[i]-1)//2 for i in range(p)))

Fixed submission:
n,p=map(int,input().split())
s=list(map(int,list(input()[::-1])))
if p in [2,5]:
  ans=0
  for i in range(n):
    if s[-i-1]%p==0:ans+=i+1
  print(ans)
  exit()
from collections import defaultdict
d=defaultdict(int)
t=0
d[t]+=1
m=1
for i in range(n):
  t+=m*s[i]
  t%=p
  d[t]+=1
  m*=10
  m%=p
print(sum(d[i]*(d[i]-1)//2 for i in range(p)))
Buggy python submission (verdict: Runtime Error):
a=[[int(input())for _ in range(3)]for _ in range(3)]
n=int(input())
b=[int(input())for _ in range(n)]
for i in b:
  for j in range(3):
    for k in range(3):
      if i==a[j][k]:a[j][k]=0
ans="No"
for i in range(3):
  if a[i][0]==a[i][1]==a[i][2]:ans="Yes"
  if a[0][i]==a[1][i]==a[2][i]:ans="Yes"
if a[0][0]==a[1][1]==a[2][2]:ans="Yes"
if a[0][2]==a[1][1]==a[2][0]:ans="Yes"
print(ans)

Fixed submission:
a=[list(map(int,input().split()))for _ in range(3)]
for i in range(int(input())):
  b=int(input())
  for j in range(3):
    for k in range(3):
      if a[j][k]==b:a[j][k]=0
ans="No"
for i in range(3):
  if a[i][0]==a[i][1]==a[i][2]==0:ans="Yes"
  if a[0][i]==a[1][i]==a[2][i]==0:ans="Yes"
if a[0][0]==a[1][1]==a[2][2]==0:ans="Yes"
if a[2][0]==a[1][1]==a[0][2]==0:ans="Yes"
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
for i in range(10**10**10**10**10):
  if k**i>n:
    print(i)
    exit()

Fixed submission:
n,k=map(int,input().split())
for i in range(100000000000):
  if k**i>n:print(i);exit()
Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
mod=10**9+7
f=[1]
for i in range(2*n):f+=[f[-1]*(i+1)%mod]
def comb(a,b):return f[a]*pow(f[b],mod-2,mod)*pow(f[a-b],mod-2,mod)%mod
ans=comb(2*n-1,n-1)
for i in range(n-1,k,-1):ans=(ans-comb(n,n-i)*comb(n-1,i))%mod
print(ans)

Fixed submission:
mod=10**9+7
f=[1]
for i in range(10**6):f+=[f[-1]*(i+1)%mod]
def comb(a,b):return f[a]*pow(f[b],mod-2,mod)*pow(f[a-b],mod-2,mod)%mod

n,k=map(int,input().split())
ans=comb(n*2-1,n-1)
if k>=n-1:print(ans);exit()
for i in range(n-1,k,-1):
  #ansからi回の操作では不可能な組み合わせを引く
  #0*i + any*(n-i)
  #つまり((n-i)個の部屋にn人が入る組み合わせ)*nC(n-i)
  #各部屋には必ず1人は入る
  #つまり(n-1)Ci
  anss=comb(n-1,i)*comb(n,n-i)%mod
  ans=ans+(mod-anss)
  ans%=mod
print(ans)
Buggy python submission (verdict: Runtime Error):
n=int(input())
ans="APPROVED"
for i in list(map(int,input().split())):
  if a%2==0:
    if a%3!=0 and a%5!=0:ans="DENIED"
print(ans)

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
ans="APPROVED"
for i in a:
  if i%2==0:
    if i%3!=0 and i%5!=0:ans="DENIED"
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
inf=float('inf')
s=input()[::-1]
n=len(s)
dp=[2*[inf]for _ in range(n)]
dp[0]=[int(s[0]),10-int(s[0])]
for i in range(1,n):
  if s[i]=="9":
    dp[i][1]=min(dp[i-1][1],dp[i-1][0]+1)
    dp[i][0]=dp[i-1][0]+9
  else:
    dp[i][0]=int(s[i])+min(dp[i-1][0],dp[i-1][1]+1)
    dp[i][1]=min(9-int(s[i])+dp[i-1][1],10-int(s[i])+dp[i-1][0])
print(min(dp[n-1][0],dp[n-1][1]+1))
#for i in dp:print(*i)

Fixed submission:
inf=float('inf')
s=input()[::-1]
n=len(s)
dp=[2*[inf]for _ in range(n)]
dp[0]=[int(s[0]),10-int(s[0])]
for i in range(1,n):
  if s[i]=="9":
    dp[i][1]=min(dp[i-1][1],dp[i-1][0]+1)
    dp[i][0]=dp[i-1][0]+9
  else:
    dp[i][0]=int(s[i])+min(dp[i-1][0],dp[i-1][1]+1)
    dp[i][1]=min(9-int(s[i])+dp[i-1][1],10-int(s[i])+dp[i-1][0])
print(min(dp[n-1][0],dp[n-1][1]+1))
#for i in dp:print(*i)
Buggy python submission (verdict: Runtime Error):
n=input()
l=len(n)
k=int(input())
def f(n,k):
  l=len(n)
  if n[0]=="0":return f(n[1:],k)
  if l<k:return 0
  if k==1:
    ans=((l-1)*9)+int(n[0])
  if k==2:
    ans=((l-1)*(l-2)//2)*81+(int(n[0])-1)*((l-1)*9)
    ans+=f(n[1:],k-1)
  if k==3:
    ans=(int(n[0])-1)*((l-1)*(l-2)//2)*81+((l-1)*(l-2)*(l-3)//6)*9*9*9
    ans+=f(n[1:],k-1)
  return ans
print(f(n,k))

Fixed submission:
n=input()
k=int(input())
dp=[[(k+1)*[0]for _ in range(2)]for _ in range(len(n))]
#dp[i][flag][j]...i文字目までみて0以外がj個あるパターン数
#flag...True(n[])
dp[0][0][0]=1
dp[0][1][1]=1
dp[0][0][1]=int(n[0])-1
for i in range(1,len(n)):
  for j in range(k+1):dp[i][1][j]=dp[i-1][1][j]
  if n[i]!="0":dp[i][1]=[0]+dp[i][1][:k]
  for j in range(k+1):dp[i][0][j]=dp[i-1][0][j]
  for j in range(k):
    dp[i][0][j+1]+=dp[i-1][0][j]*9
    if n[i]!="0":
      dp[i][0][j+1]+=dp[i-1][1][j]*(int(n[i])-1)
      dp[i][0][j+1]+=dp[i-1][1][j+1]
print(dp[-1][0][-1]+dp[-1][1][-1])
#for i in dp:print(*i)

Buggy python submission (verdict: Runtime Error):
n=input()
if n[0]=="0"ans=1/0
l=len(n)
k=int(input())
if l<6:
  n=int(n)
  ans=0
  for i in range(1,n+1):
    if len(str(i))-str(i).count("0")==k:ans+=1
  print(ans)
  exit()
if k==1:
  ans=((l-1)*9)+int(n[0])
  print(ans)
if k==2:
  ans=((l-1)*(l-2)//2)*81
  ans+=(int(n[0])-1)*((l-1)*9)
  ans+=int(n[1])
  ans+=(l-2)*9
  print(ans)
if k==3:
  ans=int(n[2])+(l-3)*9
  ans+=(int(n[1])-1)*((l-2)*9)
  ans+=((l-2)*(l-3)//2)*81
  ans+=(int(n[0])-1)*((l-1)*(l-2)//2)*81
  ans+=((l-1)*(l-2)*(l-3)//6)*9*9*9
  print(ans)

Fixed submission:
n=input()
k=int(input())
dp=[[(k+1)*[0]for _ in range(2)]for _ in range(len(n))]
#dp[i][flag][j]...i文字目までみて0以外がj個あるパターン数
#flag...True(n[])
dp[0][0][0]=1
dp[0][1][1]=1
dp[0][0][1]=int(n[0])-1
for i in range(1,len(n)):
  for j in range(k+1):dp[i][1][j]=dp[i-1][1][j]
  if n[i]!="0":dp[i][1]=[0]+dp[i][1][:k]
  for j in range(k+1):dp[i][0][j]=dp[i-1][0][j]
  for j in range(k):
    dp[i][0][j+1]+=dp[i-1][0][j]*9
    if n[i]!="0":
      dp[i][0][j+1]+=dp[i-1][1][j]*(int(n[i])-1)
      dp[i][0][j+1]+=dp[i-1][1][j+1]
print(dp[-1][0][-1]+dp[-1][1][-1])
#for i in dp:print(*i)
Buggy python submission (verdict: Time Limit Exceeded):
h,n=map(int,input().split())
a=[]
b=[]
for i in range(n):
  aa,bb=map(int,input().split())
  a.append(aa)
  b.append(bb)
inf=10**10
f=h+max(a)+1
dp=[f*[inf]for _ in range(n+1)]
dp[0][0]=0
for i in range(1,n+1):
  dp[i]=dp[i-1]
  for j in range(f):
    if j+a[i-1]<f:
      dp[i][j+a[i-1]]=min(dp[i][j+a[i-1]],dp[i][j]+b[i-1])
  for j in range(f-1,0,-1):
    dp[i][j-1]=min(dp[i][j-1],dp[i][j])
print(dp[-1][h])


Fixed submission:
h,n=map(int,input().split())
a=[]
b=[]
for i in range(n):
  aa,bb=map(int,input().split())
  a.append(aa)
  b.append(bb)
inf=10**10
f=h+max(a)+1
#dp[i][j]=i番目までの魔法を使えるとき、体力をj減らす最小魔力
dp=[f*[inf]for _ in range(n+1)]
dp[0][0]=0
for i in range(1,n+1):
  dp[i][0]=0
  for j in range(f):
    dp[i][j]=dp[i-1][j]
    if j-a[i-1]>=0:dp[i][j]=min(dp[i][j],dp[i][j-a[i-1]]+b[i-1])
print(min(dp[-1][h:]))

Buggy python submission (verdict: Time Limit Exceeded):
h,n=map(int,input().split())
a=[]
b=[]
for i in range(n):
  aa,bb=map(int,input().split())
  a.append(aa)
  b.append(bb)
inf=10**10
f=h+max(a)+1
#dp[i][j]=i番目までの魔法を使えるとき、体力をj減らす最小魔力
dp=[f*[inf]for _ in range(n+1)]
dp[0][0]=0
for i in range(1,n+1):
  dp[i][0]=0
  for j in range(f):
    dp[i][j]=dp[i-1][j]
    if j-a[i-1]>=0:dp[i][j]=min(dp[i][j],dp[i][j-a[i-1]]+b[i-1])
print(min(dp[-1][h:]))

Fixed submission:
h,n=map(int,input().split())
a=[]
b=[]
for i in range(n):
  aa,bb=map(int,input().split())
  a.append(aa)
  b.append(bb)
inf=10**10
f=h+max(a)+1
#dp[i][j]=i番目までの魔法を使えるとき、体力をj減らす最小魔力
dp=[f*[inf]for _ in range(n+1)]
dp[0][0]=0
for i in range(1,n+1):
  dp[i][0]=0
  for j in range(f):
    dp[i][j]=dp[i-1][j]
    if j-a[i-1]>=0:dp[i][j]=min(dp[i][j],dp[i][j-a[i-1]]+b[i-1])
print(min(dp[-1][h:]))
Buggy python submission (verdict: Runtime Error):
from bisect import bisect_right
n,d,a=map(int,input().split())
xh=[list(map(int,input().split()))for _ in range(n)]
xh.sort()
x=[]
h=[]
for xx,hh in xh:
  x.append(xx)
  h.append(hh)

not_imos=[0]*(n+1)
atk_n=0
ans=0
for i in range(n):
  atk_n-=imos[i]
  h[i]-=atk_n*a
  if h[i]<0:h[i]=0
  atk_i=0--h[i]//a
  ans+=atk_i
  atk_n+=atk_i
  imos[bisect_right(x,x[i]+d*2)]+=atk_i
print(ans)

Fixed submission:
from bisect import bisect_left,bisect_right
n,d,a=map(int,input().split())
xh=[list(map(int,input().split()))for _ in range(n)]
xh.sort()
x=[]
h=[]
for xx,hh in xh:
  x.append(xx)
  h.append(hh)
imos=[0]*(n+1)
mi=0
ans=0
for i in range(n):
  mi-=imos[i]
  h[i]=max(h[i]-mi*a,0)
  atk=0--h[i]//a
  ans+=atk
  mi+=atk
  point=x[i]+d*2
  index=bisect_right(x,point)
  imos[index]+=atk
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
mod=10**9+7
n=int(input())
a=list(map(int,input().split()))
def gcd(a,b):
  while b:a,b=b,a%b
  return a
def lcm(a,b):return a*b//gcd(a,b)
l=a[0]
for i in range(1,n):
  l=lcm(l,a[i])
ans=0
for i in range(n):
  ans+=l//a[i]
  ans%=mod
print(ans)

Fixed submission:
mod=10**9+7
n=int(input())
a=list(map(int,input().split()))
def gcd(a,b):
  while b:a,b=b,a%b
  return a
def lcm(a,b):return a*b//gcd(a,b)
l=a[0]
for i in range(1,n):
  l=lcm(l,a[i])
ans=0
l%=mod
for i in range(n):
  ans+=l*pow(a[i],mod-2,mod)
  ans%=mod
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappop as hpop
from heapq import heappush as hpush
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort(reverse=1)
a+=[-99999999999999]
h=[]
for i in range(n):hpush(h,[-a[i]*2,i])
count=m
ans=0
while count!=0:
  x,i=hpop(h)
  x=-x
  c=min(count,1+(x!=a[i]*2))
  count-=c
  ans+=c*x
  x-=a[i]
  x+=a[i+1]
  i+=1
  hpush(h,[-x,i])
print(ans)

Fixed submission:
n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n):a[i]*=-1
a.sort()
from bisect import bisect_left,bisect_right
def check(mid):
  mm=0
  for i in range(n):
    if -(a[i]+a[0])<mid:break
    mm+=bisect_right(a,-(mid+a[i]))
  return mm
ok=0
ng=10**10+7
while ng!=ok+1:
  mid=(ok+ng)//2
  if check(mid)>=m:ok=mid
  else:ng=mid
b=[0]
for i in a:b.append(b[-1]+i)
ans=0
for i in range(n):
  if -(a[i]+a[0])<ok:break
  ind=bisect_right(a,-(ok+a[i]))
  ans+=a[i]*ind
  ans+=b[ind]
print(-(ans+(check(ok)-m)*ok))
Buggy python submission (verdict: Runtime Error):
ans=""
n=input()
s=input()
t=input()
for i in range(len(s)):
  ans+=s[i]+t[i]
print(ans)


Fixed submission:
n=int(input())
s,t=input().split()
a=""
for i,j in zip(s,t):a+=i+j
print(a)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=[]
for i in range(n):
  m=int(input())
  a.append([])
  for i in range(m):
    a[-1].append(list(map(int,input().split())))
ans=0
for i in range(2**n):
  s=bin(i)[2:].zfill(n)
  f=True
  for j,k in enumerate(a):
    for x,y in k:
      if s[x-1]!=str(y) and s[j]=="1":f=False
  if f:ans=max(ans,s.count("1"))
print(ans)

Fixed submission:
n=int(input())
a=[]
for i in range(n):
  m=int(input())
  a.append([])
  for i in range(m):
    a[-1].append(list(map(int,input().split())))
ans=0
for i in range(2**n):
  s=bin(i)[2:].zfill(n)
  f=True
  for j,k in enumerate(a):
    for x,y in k:
      if s[x-1]!=str(y) and s[j]=="1":f=False
  if f:ans=max(ans,s.count("1"))
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
s=input()
st=[str(i).zfill(3)for i in range(1000)]
dp=[0]*1000
for i in s:
  for j in range(1000):
    if dp[j]<3:
      if st[j][dp[j]]==i:dp[j]+=1
print(dp.count(3))

Fixed submission:
n=int(input())
s=input()
st=[str(i).zfill(3)for i in range(1000)]
dp=[0]*1000
for i in s:
  for j in range(1000):
    if dp[j]<3:
      if st[j][dp[j]]==i:dp[j]+=1
print(dp.count(3))
Buggy python submission (verdict: Runtime Error):
t1,t2=map(int,input().split())
a1,a2=map(int,input().split())
b1,b2=map(int,input().split())
a=t1*(a1-b1)
b=t2*(a2-b2)
if a+b==0:print("infinity");exit()
if a*b>=0:print(0);exit()
x,y=abs(a-b),abs(a+b)
print(x,y)
print(int(0--(x)//y)-0.5)-1)

Fixed submission:
t1,t2=map(int,input().split())
a1,a2=map(int,input().split())
b1,b2=map(int,input().split())
x=(a1-b1)*t1
y=(a2-b2)*t2
if x>0:
  x*=-1
  y*=-1
if x+y<0:print(0)
elif x+y==0:print("infinity")
else:
  ans=(-x)//(x+y)
  if (-x)%(x+y):print(ans*2+1)
  else:print(ans*2)
Buggy python submission (verdict: Runtime Error):
t="ABCDEFGHIJKLMNOPQRSTUVWXYZ"*2
n=int(input())
print(t[t.index(input())+n])

Fixed submission:
n=int(input())
s=input()
t=list("ABCDEFGHIJKLMNOPQRSTUVWXYZ"*2)
a=""
for i in s:a+=t[t.index(i)+n]
print(a)
Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
s=input()
x=n
a=0
while x!=0:
  for i in range(m,0,-1):
    if s[x-i]=="0":
      x-=i
      a=a*10+i
      break
    if i==1:print(-1);exit()
print(*list(str(a))[::-1])

Fixed submission:
n,m=map(int,input().split())
s=input()
x=n
a=[]
while x!=0:
  for i in range(min(m,x),0,-1):
    if s[x-i]=="0":
      x-=i
      a.append(i)
      break
    if i==1:print(-1);exit()
print(*a[::-1])
Buggy python submission (verdict: Runtime Error):
x,y=map(int,input().split())
a=0
if x==y==1:a=40000
a+=10000*((4-x)+(4-y))x,y=map(int,input().split())
a=0
x=min(x,4)
y=min(y,4)
if x==y==1:a=400000
a+=100000*((4-x)+(4-y))
print(a)

Fixed submission:
x,y=map(int,input().split())
a=0
x=min(x,4)
y=min(y,4)
if x==y==1:a=400000
a+=100000*((4-x)+(4-y))
print(a)
Buggy python submission (verdict: Runtime Error):
h,w,k=map(int,input().split())
b=[input()for _ in range(h)]
ans=[w*[0]for _ in range(h)]
f=[1]*h
j=-1
bb=[]
for i in range(h):
  if "#"in b[i]:
    f[i]=0
    j=i
    if len(bb)==0:continue
    for k in bb:b[k]=b[j]
    bb=[]
  else:
    if j<0:s.append(i)
    else:b[i]=b[j]
a=1
for i in range(h):
  if f[i]:continue
  fl=False
  for j in range(w):
    if b[i][j]=="#":
      a+=1
      fl=True
    ans[i][j]=a
  if f:a+=1
for i in ans:print(*i)

Fixed submission:
h,w,k=map(int,input().split())
s=[list(input())for _ in range(h)]
b=[w*[0]for _ in range(h)]
c=[]
d=-1
bb=[]
for i in range(h):
  if "#" not in s[i]:
    c.append(0)
    if d>-1:
      b[i]=b[d]
    else:bb.append(i)
  else:
    c.append(1)
    d=i
    if len(bb)>0:
      for j in bb:b[j]=b[d]
      bb=[]
a=1
for i in range(h):
  f=False
  if c[i]==0:continue
  for j in range(w):
    if s[i][j]=="#":
      if f:a+=1
      f=True
    b[i][j]=a
  if f:
    a+=1
    m=i
for i in b:print(*i)
Buggy python submission (verdict: Time Limit Exceeded):
m=int(input())
d,c=[],[]
ans=-1
for i in range(m):
  dd,cc=map(int,input().split())
  d.append(dd)
  c.append(cc)
  ans+=cc
a=0
ds=lambda n:sum(list(map(int,list(str(n)))))
for i in range(m):
  if d[i]*c[i]+a<10:a+=d[i]*c[i]
  else:
    if c[i]*d[i]>9:
      ci,di=c[i],d[i]
      while ci*di>9:
        cd=(0--10//di)
        ci,di,cci,ddi=ci//cd,ds(cd*di),ci-(ci//cd*cd),di
        ans+=ci
        if ddi*cci+a>9:ans+=1
        a=ds(ddi*cci+a)
      if di*ci+a>9:ans+=1
      a=ds(di*ci+a)
    else:
      ans+=1
      a=ds(a+c[i]*d[i])
print(ans)

Fixed submission:
m=int(input())
d,c=[],[]
ans=-1
for i in range(m):
  dd,cc=map(int,input().split())
  d.append(dd)
  c.append(cc)
  ans+=cc
a=0
for i in range(m):
  a+=d[i]*c[i]
  dd=(a-1)//9
  ans+=dd
  a-=dd*9
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
m=int(input())
d,c=[],[]
ans=-1
for i in range(m):
  dd,cc=map(int,input().split())
  d.append(dd)
  c.append(cc)
  ans+=cc
a=0
ds=lambda n:sum(list(map(int,list(str(n)))))
for i in range(m):
  if d[i]*c[i]+a<10:a+=d[i]*c[i]
  else:
    if c[i]*d[i]>9:
      ci,di=c[i],d[i]
      while ci*di>9:
        cd=(0--10//di)
        ci,di,cci,ddi=ci//cd,ds(cd*di),ci-(ci//cd*cd),di
        ans+=ci
        if ddi*cci+a>9:ans+=1
        a=ds(ddi*cci+a)
      if di*ci+a>9:ans+=1
      a=ds(di*ci+a)
    else:
      ans+=1
      a=ds(a+c[i]*d[i])
print(ans)

Fixed submission:
m=int(input())
d,c=[],[]
ans=-1
for i in range(m):
  dd,cc=map(int,input().split())
  d.append(dd)
  c.append(cc)
  ans+=cc
a=0
for i in range(m):
  a+=d[i]*c[i]
  dd=(a-1)//9
  ans+=dd
  a-=dd*9
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
ans=n-1
for i in range(2,n):
  if n%i:continue
  j=n//i
  if j<i:break
  ans=j+i-2
print(ans)


Fixed submission:
n=int(input())
a=n-1
for i in range(1,int(n**0.5)+1):
  if n%i:continue
  j,k=i,n//i
  a=min(a,j+k-2)
print(a)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
ans=n-1
for i in range(2,n):
  if n%i:continue
  j=n//i
  if j<i:break
  ans=j+i-2
print(ans)

Fixed submission:
n=int(input())
a=n-1
for i in range(1,int(n**0.5)+1):
  if n%i:continue
  j,k=i,n//i
  a=min(a,j+k-2)
print(a)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
x=[0]*1010
for i in list(map(int,input().split())):x[i]+=1
ans=0
for a in range(1,1001):
  for b in range(a,1001):
    for c in range(b,1001):
      if a<b+c and b<c+a and c<a+b:
        if a==b==c:ans+=x[a]*(x[b]-1)*(x[c]-2)//6
        elif a==b:ans+=x[a]*(x[b]-1)*x[c]//2
        elif b==c:ans+=x[a]*x[b]*(x[c]-1)//2
        else:ans+=x[a]*x[b]*x[c]
print(ans)

Fixed submission:
n=int(input())
l=list(map(int,input().split()))
from bisect import bisect_left,bisect_right
l.sort()
a=0
for i in range(n-2):
  for j in range(i+1,n-1):
    a+=bisect_left(l,l[i]+l[j])-j-1
print(a)