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

Fixed submission:
import numpy as np
n,w=map(int,input().split())
wv=[]
for _ in range(n):
      wv.append(list(map(int,input().split())))
# dp[i]:価値の総和をちょうどiにできる最小の重さ総和
# dp[i]=w+1となる価値総和iにはできない。
# 求めるのはdp[i]<=wとなる最大のi
dp=np.full(10**5+1,w+1) # ndarray(1000,1000,...,1000])
dp[0]=0
# 10**5:viの総和の最大
for i in range(n):
      w_=wv[i][0]
      v_=wv[i][1]
      # i番目までの商品を取るか取らないかの全ての組み合わせをためすことができる。
      dp[v_:]=np.minimum(dp[v_:], dp[:-v_]+w_)
print(np.where(dp<=w)[0][-1])

Buggy submission (verdict: Runtime Error):
import numpy as np
n,w=map(int,input().split())
wv=[]
for _ in range(n):
      wv.append(list(map(int,input().split())))

# dp[j]:重さの総和がj以下となるように選択した時の最大
dp=np.zeros(w+1)
for i in range(n):
      # i+1個目までの商品の中から選ぶときのdpを計算する
      # i+1個目の計算をするときはdpはi個目までの商品の中から選んだ時のdpとなっている
      # i=0 ->dp=zeros
      w_=wv[i][0]
      v_=wv[i][1]
      # dp[w_:]:i+1個目の商品を加えられるのはこの部分のみ。
      # dp[w_:]:i+1個目の商品を加えないパターン
      # dp[:-w_]+v_:i+1個目の商品を加えたパターン。商品の重さだけwを減らした時の最大価値に商品の価値をプラスしている。
      dp[w_:] = np.maximum(dp[w_:], dp[:-w_] + v_)
print(int(dp[-1]))

Buggy submission (verdict: Runtime Error):
import numpy as np
n,w=map(int,input().split())
wv=[]
for _ in range(n):
      wv.append(list(map(int,input().split())))

# dp[j]:重さの総和がj以下となるように選択した時の最大
dp=np.zeros(w+1,np.int64)
for i in range(n):
      # i+1個目までの商品の中から選ぶときのdpを計算する
      # i+1個目の計算をするときはdpはi個目までの商品の中から選んだ時のdpとなっている
      # i=0 ->dp=zeros
      w_=wv[i][0]
      v_=wv[i][1]
      # dp[w_:]:i+1個目の商品を加えられるのはこの部分のみ。
      # dp[w_:]:i+1個目の商品を加えないパターン
      # dp[:-w_]+v_:i+1個目の商品を加えたパターン。商品の重さだけwを減らした時の最大価値に商品の価値をプラスしている。
      dp[w_:] = np.maximum(dp[w_:], dp[:-w_] + v_)
print(dp[-1])
Problem p03165 (python)

Fixed submission:
import numpy as np
s=np.array(list(input()))
t=np.array(list(input()))
is_eq=np.array(s[:,None]==t[None,])
# is_eq[i][j]:sのi文字目とtのj文字目が等しいかどうか
# print(is_eq)
ns=len(s)
nt=len(t)
dp=np.zeros((ns+1,nt+1),np.int64)

# dp[i+1][j+1]:sのi文字目までとtのj文字目までで最長の部分列
# dp[0][j]=0,dp[i][0]=0,dp[n+1][w+1]の値がsとtで最長の部分列の長さ
for i in range(ns): #sのi文字目までの文字列で調査
    dp[i+1][1:]=np.maximum(dp[i][:-1]+is_eq[i],dp[i][1:])#左上からの更新、真上からの更新
    dp[i+1]=np.maximum.accumulate(dp[i+1])#左からの更新
i=ns
j=nt
ans=['']
while i>0 and j>0:
      if dp[i][j]==dp[i-1][j]:
            i-=1
      elif dp[i][j]==dp[i][j-1]:
            j-=1
      else:
            ans.append(s[i-1])
            i-=1
            j-=1
a=''
for _ in range(len(ans)):
      a+=ans.pop()
print(a)

Buggy submission (verdict: Runtime Error):
import numpy as np
s=np.array(list(input()))
t=np.array(list(input()))
is_eq=np.array(s[:,None]==t[None,])
# is_eq[i][j]:sのi文字目とtのj文字目が等しいかどうか
# print(is_eq)
ns=len(s)
nt=len(t)
dp=np.zeros((ns+1,nt+1),np.int64)
print(dp.shape)
print(is_eq.shape)

# dp[i+1][j+1]:sのi文字目までとtのj文字目までで最長の部分裂の長さ
# dp[0][j]=0,dp[i][0]=0,
for i in range(ns): #sのi文字目までの文字列で調査
    dp[i+1][1:]=np.maximum(dp[i][:-2]+is_eq[i],dp[i+1][:-1],dp[i][1:])
print(dp)
print(is_eq)

Buggy submission (verdict: Runtime Error):
import numpy as np
s=input()
t=input()

ns=len(s)
nt=len(t)
dp=np.zeros((ns+1,nt+1),np.int64)
pp=np.full((ns+1,nt+1),'')
ppd={0:'c',1:'l',2:'u'}
for i in range(ns):
  for j in range(nt):
    a=np.array([dp[i][j]+1 if s[i]==t[j] else -1,dp[i+1][j],dp[i][j+1]])
    dp[i+1][j+1]=np.max(a)
    pp[i+1][j+1]=ppd[np.argmax(a)]

i=ns
j=nt
ans=[]
while i>0 and j>0:
  sw=pp[i][j]
  if sw=='c':
        i-=1
        j-=1
        ans.append(s[i])
  elif sw=='l':
        j-=1
  elif sw=='u':
        i-=1
ans1=''
for _ in range(len(ans)):
      ans1+=ans.pop()
print(ans1)

Buggy submission (verdict: Runtime Error):
import numpy as np
s=input()
t=input()

"""
dp[i+1][j+1]:sのi文字目までとtのj文字目まででの LCS の長さ
dp[i+1][j+1]をdp[i][j],dp[i][j+1],dp[i][j+1]を使って表現する。
dp[i+1][j+1]=max(dp[i][j]+1 if s[i]==t[j] else 0,dp[i+1][j],dp[i][j+1])
"""
ns=len(s)
nt=len(t)
dp=np.zeros((ns+1,nt+1),np.int64)
pp=np.full((ns+1,nt+1),'')
ppd={0:'c',1:'l',2:'u'}
for i in range(ns):
  for j in range(nt):
    a=np.array([dp[i][j]+1 if s[i]==t[j] else -1,dp[i+1][j],dp[i][j+1]])
    dp[i+1][j+1]=np.max(a)
    pp[i+1][j+1]=ppd[np.argmax(a)]

i=ns
j=nt
ans=[]
while i>0 and j>0:
  sw=pp[i][j]
  if sw=='c':
        i-=1
        j-=1
        ans.append(s[i])
  elif sw=='l':
        j-=1
  elif sw=='u':
        i-=1
ans1=''
for _ in range(len(ans)):
      ans1+=ans.pop()
print(ans1)
Problem p03166 (python)

Fixed submission:
import numpy as np
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
n,m = map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
      x,y=map(int,input().split())
      g[x-1].append(y-1)
memo = [0]*n
visited = [False]*n
# dp(i):i=0,1,..,n-1:頂点iを始点とした最長のパスを返す
def dp(v):
      if visited[v]:
            return memo[v]
      else:
            res=0
            for u in g[v]:
                  res=max(res,dp(u)+1)
            memo[v]=res
            visited[v]=True
            return res
for i in range(n):
      dp(i)
print(max(memo))

Buggy submission (verdict: Runtime Error):
import numpy as np
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
      x,y=map(int,input().split())
      g[x-1].append(y-1)
memo = [0]*n
visited = [False]*n
# dp(i):i=0,1,..,n-1:頂点iを始点とした最長のパスを返す
def dp(v):
      if visited[v]:
            return memo[v]
      else:
            res=0
            for u in g[v]:
                  res=max(res,dp(u)+1)
            memo[v]=res
            visited[v]=True
            return res
for i in range(n):
      dp(i)
print(max(memo))

Buggy submission (verdict: Runtime Error):
import numpy as np
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
xy = [list(map(int,input().split())) for _ in range(m)]
# dp[j][k]:頂点iからはじまり頂点jで終わる最長のもの
dp=np.full((n,n),-1,np.int64)
for i in range(n):
      dp[i][i]=0
for _ in xy:
      x_=_[0]-1
      y_=_[1]-1
      dp[x_,y_]=1
      x0=np.where(dp[:,x_] >= 0)[0]
      y0=np.where(dp[y_,:] >= 0)[0]
      for j in x0:
            for k in y0:
                  dp[j,k]=max(dp[j,k],dp[j,x_]+dp[y_,k]+1)
print(np.max(dp))
Problem p03167 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
h,w = map(int,input().split())
a=[input() for _ in range(h)]
mod=10**9+7
dp=[[0]*w for _ in range(h)]
dp[0][0]=1
for i in range(h):
      for j in range(w):
            if i+1<h and a[i+1][j]=='.':
                  dp[i+1][j]+=dp[i][j]%mod
            if j+1<w and a[i][j+1]=='.':
                  dp[i][j+1]+=dp[i][j]%mod
print(dp[-1][-1]%mod)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
h,w = map(int,input().split())
a=[input() for _ in range(h)]
mod=10**9+7
dp=[[0]*w for _ in range(w)]
dp[0][0]=1
for i in range(h):
      for j in range(w):
            if i+1<h and a[i+1][j]=='.':
                  dp[i+1][j]+=dp[i][j]%mod
            if j+1<w and a[i][j+1]=='.':
                  dp[i][j+1]+=dp[i][j]%mod
print(dp[-1][-1]%mod)
Problem p03170 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
n,k=map(int,input().split())
a=list(map(int,input().split()))
#n,k=100,100000
#a=range(1,101)

dp=[False for _ in range(k+1)]
calted=[False for _ in range(k+1)]
# dp[i]:残り石i個で自分のターンになった時、勝てるならTrue
# dp[0]=False,dp[a]=True,求めるのはdp[k]
mi=min(a)
ma=max(a)
for ai in a:
	dp[ai]=True
	calted[ai]=True
# dp[i]={dp[i-a]の中にFalseがあればTrue、すべてTrueならFalse}
for i in range(mi+1,k+1):
      if calted[i]:
            continue
      il=[i-ai for ai in a if i-ai>=0]
      f=1
      for l in il:
        f*=dp[l]
      if f == 0:
            dp[i]=True
      else:
            dp[i]=False
print('First' if dp[k] else 'Second')
#print(dp)
#print(datetime.datetime.now())

Buggy submission (verdict: Runtime Error):
n,k=map(int,input().split())
a=np.array(list(map(int,input().split())))
dp=[False]*(k+1)
# dp[i]:残り石i個で自分のターンになった時、勝てるならTrue
# dp[0]=False,dp[a]=True,求めるのはdp[k]
# dp[i]={dp[i-a]の中にひとつでもFalseがあればTrue、other->False}
# <=> すべてのai(in a)についてdp[i]=False->dp[i+ai]=True
for i in range(k+1):
      for ai in a:
            if i+ai<=k and not dp[i]:
                  dp[i+ai]=True
print('First' if dp[k] else 'Second')
Problem p03171 (python)

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
dp=[[0]*n for _ in range(n)]
# dp[i][j]:i<=j,i番目からj番目までの数列(j-i+1個)を前にした時、ゲーム終了までに自分が取れる最大得点。i,j=0,..,n-1
sa=[0]
s=0
for ai in a:
      s+=ai
      sa.append(s)
for len in range(1,n+1):
      for l in range(n-len+1):
            r=l+len-1
            s=sa[r+1]-sa[l]
            dp[l][r]=max(s-dp[l][r-1],s-dp[l+1][r] if l+1<n else 0)
print(2*dp[0][-1]-sa[-1])

Buggy submission (verdict: Runtime Error):
n=int(input())
a=list(map(int,input().split()))
d={}
def k(a):
      return ','.join(map(str,a))
def dp(a):
      ka=k(a)
      if ka in d:
            return [d[ka][0],d[ka][1]]
      if len(a)==1:
            d[ka]=[a[0],[]]
            return a[0],[]
      elif len(a)==2:
            d[ka]=[max(a),[min(a)]]
            return max(a),[min(a)]
      else:
            if a[0]-dp(a[1:])[0]>a[-1]-dp(a[:-1])[0]:
                  d[ka]=[a[0],a[1:]]
                  return a[0],a[1:]
            else:
                  d[ka]=[a[-1],a[:-1]]
                  return a[-1],a[:-1]
x,y=0,0
while a!=[]:
      x_,a=dp(a)
      x+=x_
      if a==[]:
            break
      y_,a=dp(a)
      y+=y_
print(x-y)
Problem p03248 (python)

Fixed submission:
s=list(input())
n=len(s)
if s[0]=='0' or s[-1]=='1':
  print(-1)
else:
  s.pop()
  sr=s.copy()
  sr.reverse()
  if s!=sr:
    print(-1)
  else:
    ans=[]
    now=1
    cnt=1
    for x in s:
      if x=='1':
        ans.append([now,now+cnt])
        now+=cnt
        cnt=1
      else:
        ans.append([now,now+cnt])
        cnt+=1
    for x in ans:
      print(x[0],x[1])

Buggy submission (verdict: Runtime Error):
s=list(map(int,list(input())))
# s[0]=1,s[-1]=0,s[k]=s[n-k-1]は必要
def main(s):
  n=len(s)
  if s[0]!=1 or s[-1]!=0:return [-1]
  for k in range(n//2-1):
    if s[k]!=s[n-k-2]:return [-1]
  uv=[(1,2)]
  t=2
  i=3
  for x in s[1:-1]:
    uv.append((t,i))
    if x==1:
      t=i
    i+=1
  return uv
for x in main(s):
  print(*x,sep=' ')
Problem p03311 (python)

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
for i in range(n):
    a[i] -= i + 1
a.sort()
b1 = a[n // 2]
b2 = a[(n // 2 ) - 1]
r1=0
r2=0
for i in range(n):
    r1+=abs(a[i]-b1)
    r2+=abs(a[i]-b2)
print(min(r1,r2))

Buggy submission (verdict: Runtime Error):
n=int(input())
a=list(map(int,input().split()))
a.sort()
s=0
for i in range(n):
    a[i] -= i + 1
    s += a[i]
b1 = a[n // 2]
b2 = a[(n // 2 )+ 1]
r1=0
r2=0
for i in range(n):
    r1+=abs(a[i]-b1)
    r2+=abs(a[i]-b2)
print(min(r1,r2))
Problem p03330 (python)

Fixed submission:
n,nc=map(int,input().split())
d=[list(map(int,input().split())) for _ in range(nc)]
c=[list(map(int,input().split())) for _ in range(n)]
from collections import defaultdict
dct=defaultdict(int)
for x in range(n):
  for y in range(n):
    for ci in range(nc):
      if (ci,(x+y)%3) in dct:
        dct[(ci,(x+y)%3)]+=d[c[x][y]-1][ci]
      else:
        dct[(ci,(x+y)%3)]=d[c[x][y]-1][ci]

def func(c1,c2,c3): #(i+j)%=0をc1に、=1をc2に、=2をc3に塗るときの違和感
  ret=dct[(c1,0)]+dct[(c2,1)]+dct[(c3,2)]
  return ret
ans=float('inf')
for c1 in range(nc):
  for c2 in range(nc):
    if c1==c2:continue
    for c3 in range(nc):
      if c1==c3 or c2==c3:continue
      ans=min(ans,func(c1,c2,c3))
print(ans)
#print(dct)

Buggy submission (verdict: Runtime Error):
n,nc=map(int,input().split())
d=[list(map(int,input().split())) for _ in range(nc)]
c=[list(map(int,input().split())) for _ in range(n)]

dct={}
for x in range(n):
  for y in range(n):
    for ci in range(nc):
      if (ci,(x+y)%3) in dct:
        dct[(ci,(x+y)%3)]+=d[c[x][y]-1][ci]
      else:
        dct[(ci,(x+y)%3)]=d[c[x][y]-1][ci]

def func(x,y,z): #(i+j)%=0をxに、=1をyに、=2をzに塗るときの違和感
  ret=dct[(x,0)]+dct[(y,1)]+dct[(z,2)]
  return ret
ans=float('inf')
for x in range(nc):
  for y in range(nc):
    if x==y:continue
    for z in range(nc):
      if x==z or z==y:continue
      ans=min(ans,func(x,y,z))
print(ans)
#print(dct)
Problem p03364 (python)

Fixed submission:
n=int(input())
s=[list(input()) for _ in range(n)]
import numpy as np
ss=[si+si for si in s]
ss=np.array(ss+ss)
ans=0
for i in range(n):
    a=ss[i:i+n,:n]
    if np.array_equal(a,a.T):
      ans+=1
print(ans*n)

Buggy submission (verdict: Runtime Error):
n=int(input())
s=[list(input()) for _ in range(n)]
import numpy as np
ss=[si+si for si in s]
ss=np.array(ss+ss)
ans=0
for i in range(n):
  for j in range(n):
    a=ss[i:i+n,j:j+n]
    if np.array_equal(a,a.T):
      ans+=1
print(ans)
Problem p03388 (python)

Fixed submission:
q=int(input())
ab=[list(map(int,input().split())) for _ in range(q)]
from math import floor
for a,b in ab:
  if a==b:
    print(2*a-2)
    continue
  t=floor((a*b)**0.5)
  # t,t+1 組み合わせの積がa*bで抑えられているかどうか
  if t*t>=a*b: # t*tもだめ
    print(2*t-3)
  elif t*(t+1)>=a*b: # t*(t+1)はだめ
    print(2*t-2)
  else: # t*tもt*(t+1)もOK
    print(2*t-1)

Buggy submission (verdict: Runtime Error):
q=int(input())
ab=[list(map(int,input().split())) for _ in range(q)]
for a,b in ab:
    if a>b:a,b=b,a
    if a==b:
        print(2*a-2)
    elif a+1==b:
        print(2*a-2)
    else:
        c=int((a*b)**0.5)
        if c*(c+1)>=a*b:
            print(2*c-2)
        elif c**2<a*b:
            print(2*c-1)


q=int(input())
ab=[list(map(int,input().split())) for _ in range(q)]
from math import floor
for a,b in ab:
    # a*bをぎりぎりまで攻めたい
    # (1,1)とかはもったいない。(1,a*b-1)は良い。片方は√a*b未満で、片方は√a*bより大きい組み合わせ。
    # a==bならa未満の整数yについて適切な数字xを選べばy*x<a*bとできる。xは他のxと被らないように選択できる。
    if a==b:
        print(2*a-2)
    else:
        # t,t+1 組み合わせの積がa*bで抑えられているかどうか。(t+1)*(t+1)は必ずa*bを超える。
        # t未満の自然数については適切な整数を選べばa*b以下にできる。
        t=floor((a*b)**0.5)
        # (1,2*t-1),(2,2*t-2),(3,(a*b-1)//3),...,(t-1,(a*b-1)//(t-1))
        if t*t>=a*b: 
            # t*tはだめ。t*t=a*b、a!=bのとき。t未満の数字と適切な数字を選べばよいが、t未満の数字の内一つはaなので、その分を引く。
            print(2*t-3)
        elif t*(t+1)>=a*b: 
            # t*tはOK。t*(t+1)はだめ。t未満の数字と適切な数字を選べばよいが、t未満の数字の内一つはaなので、その分を引く。
            # さらに一回目tの人は2回目もtで条件を満たす。この分を足す。t!=a,t!=bなので(t,t)は選択できる。
            print(2*t-2)
        else:
            # t*tもt*(t+1)もOK。(t,t+1),(t+1,t)をまず選ぶ。あとはt未満の数字と適切な数字を選べばよいが、t未満の数字の内一つはaなので、その分を引く。
            print(2*t-1)
Problem p03440 (python)

Fixed submission:
n,m=map(int,input().split())
a=list(map(int,input().split()))
f=[[] for _ in range(n)]
for _ in range(m):
  x,y=map(int,input().split())
  f[x].append(y)
  f[y].append(x)
if m==n-1:
  print(0)
  exit()
if (n-m-1)*2>n:
  print('Impossible')
  exit()
from heapq import heappop,heappush,heapify
mi=set(list(range(n)))
dg={}
dg1c=[]
while mi:
  gk=mi.pop()
  #if len(f[gk])==0:
  #  dg1c.append(a[gk])
  #  continue
  todo=[gk]
  dg[gk]=[]
  while todo:
    v=todo.pop()
    dg[gk].append(a[v])
    for nv in f[v]:
      if nv in mi:
        todo.append(nv)
        mi.discard(nv)
# 頂点が2以上ある連結成分の個数
ren=n-m-len(dg1c)
topheap=[]
ans=0
ary=[]
cnt=0
#print(dg)
#print(f)
#print(dg1c)

for k in dg.keys():
  t=min(dg[k])
  ans+=t
  cnt+=1
  dg[k].remove(t)
  ary+=dg[k]
ary.sort()
ans+=sum(ary[:(n-m-1)*2-cnt])
print(ans)

Buggy submission (verdict: Runtime Error):
n,m=map(int,input().split())
a=list(map(int,input().split()))
f=[[] for _ in range(n)]
for _ in range(m):
  x,y=map(int,input().split())
  f[x].append(y)
  f[y].append(x)
if m==n-1:
  print(0)
  exit()
if (n-m-1)*2>n:
  print('Impossible')
  exit()
from heapq import heappop,heappush,heapify
mi=set(list(range(n)))
dg={}
dg1c=[]
while mi:
  gk=mi.pop()
  if len(f[gk])==0:
    dg1c.append(a[gk])
    continue
  todo=[gk]
  dg[gk]=[]
  while todo:
    v=todo.pop()
    dg[gk].append(a[v])
    for nv in f[v]:
      if nv in mi:
        todo.append(nv)
        mi.discard(nv)
# 頂点が2以上ある連結成分の個数
ren=n-m-len(dg1c)
topheap=[]
ans=0
#print(dg)
#print(f)
#print(dg1c)
for k in dg.keys():
  dg[k].sort()
  heapify(dg[k])
  heappush(topheap,[dg[k][0],k])
for _ in range(ren-1):
  c1,k1=heappop(topheap)
  c2,k2=heappop(topheap)
  ans+=c1+c2
  heappop(dg[k1])
  heappop(dg[k2])
  while dg[k1]:
    heappush(dg[k2],dg[k1].pop())
  dg.pop(k1)
  if dg[k2]:
    heappush(topheap,[dg[k2][0],k2])
# 頂点2個以上の連結成分は一個だけになっている
# そのコストはtopheapに一個、のこりはdg[k]にある
for i in range(len(dg1c)):
  c=heappop(dg[k2])
  ans+=c
#print(dg1c)
print(ans+sum(dg1c))
Problem p03487 (python)

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
seta=set(a)
d=dict([[x,0] for x in seta])
for i in range(len(a)):
  d[a[i]]+=1
seta=set(a)
ans=0
for ai in seta:
  if d[ai]==ai:
    pass
  elif d[ai]<ai:
    ans+=d[ai]
  else:
    ans+=d[ai]-ai
print(ans)

Buggy submission (verdict: Runtime Error):
n=int(input())
a=list(map(int,input().split()))
c=[0]*(max(a)+1)
for i in range(len(a)):
  c[a[i]]+=1
seta=set(a)
ans=0
for ai in seta:
  if c[ai]==ai:
    pass
  elif c[ai]<ai:
    ans+=c[ai]
  else:
    ans+=c[ai]-ai
print(ans)
Problem p03575 (python)

Fixed submission:
from collections import deque
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(m)]
g=[[]for _ in range(n)]

for a,b in ab:
  g[a-1].append(b-1)
  g[b-1].append(a-1)

def bfs(i,j):# iからjへのルートの数が2本以上あるかどうか。
  seen=[[-1]for _ in range(n)]
  seen[i]=[]
  todo=deque([[i]])
  c=0
  while len(todo)>0:
    d=todo.pop()
    l=g[d[-1]]
    for li in l:
      if li in d:
        continue
      if li==j:
        c+=1
        if c>1:
          return True
        continue
      e=d.copy()
      e.append(li)
      todo.append(e)
  return False

ans=0
for a,b in ab:
  ans+= 0 if bfs(a-1,b-1) else 1
print(ans)

Buggy submission (verdict: Runtime Error):
from collections import deque
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(m)]
g=[[]for _ in range(n)]

for a,b in ab:
  g[a-1].append(b-1)
  g[b-1].append(a-1)

def bfs(i,j):# iからjへのルートの数が2本以上あるかどうか。
  seen=[[-1]for _ in range(n)]
  seen[i]=[]
  todo=deque([[i]])
  c=0
  while len(todo)>0:
    d=todo.pop()
    l=g[d[-1]]
    for li in l:
      if li in d:
        continue
      if li==j:
        c+=1
        if c>1:
          return True
        continue
      e=d.copy()
      e.append(li)
      todo.append(e)
  return False

ans=0
for a,b in ab:
  ans+= 0 if bfs(a-1,b-1) else 1
print(ans)
Problem p03599 (python)

Fixed submission:
a,b,c,d,e,f=map(int,input().split())
able_water=[]
for na in range(1+f//(a*100)):
  for nb in range(1+(f-na*a*100)//(b*100)):
    water=na*a*100+nb*b*100
    if water and water<=f:
      able_water.append(water)
able_water.sort()
import bisect
ans=[0,0,0]
max_s=(f*e+100-1)//100
for nd in range(1+max_s//d):
  for nc in range(1+(max_s-nd*d)//c):
    sugger=nc*c+nd*d
    min_water=(sugger*100+e-1)//e
    if min_water+sugger>f:continue
    idx=bisect.bisect_left(able_water,min_water)
    if idx <len(able_water) and able_water[idx]+sugger<=f:
      if ans[0]<=(100*sugger/(able_water[idx]+sugger)):
        ans=[100*sugger/(able_water[idx]+sugger),able_water[idx]+sugger,sugger]
print(ans[1],ans[2])

Buggy submission (verdict: Runtime Error):
a,b,c,d,e,f=map(int,input().split())
able_water=[]
for na in range(1+f//(a*100)):
  for nb in range(1+(f-na*a*100)//(b*100)):
    water=na*a*100+nb*b*100
    if water<=f:
      able_water.append(water)
able_water.sort()
import bisect
ans=[0,0,0]
max_s=f//100*e
for nd in range(1+max_s//d):
  for nc in range(1+(max_s-nd*d)//c):
    sugger=nc*c+nd*d
    min_water=sugger*100/e
    if min_water>f-sugger:continue
    idx=bisect.bisect_left(able_water,min_water)
    if idx and able_water[idx]+sugger<=f:
      if ans[0]<(100*sugger/(able_water[idx]+sugger)):
        ans=[100*sugger/(able_water[idx]+sugger),able_water[idx]+sugger,sugger]
print(ans[1],ans[2])
Problem p03695 (python)

Fixed submission:
n=int(input())
a=list(map(lambda x:min(int(x)//400,8),input().split()))
cat=[0]*8
f=0
for ai in a:
    if ai < 8:
        cat[ai]=1
    if ai == 8:
        f+=1
print(str(max(sum(cat),1))+' '+str(sum(cat)+f))

Buggy submission (verdict: Runtime Error):
n=int(input())
a=list(map(lambda x:int(x)//400,input().split()))
cat=[0]*12
"""
cat=[0]*9
for ai in a:
    if ai < 8:
        cat[ai]=1
    else:
        cat[8]+=1
print(str(max(sum(cat[:8]),1))+' '+str(min(sum(cat),8)))
"""
for ai in a:
    cat[ai]+=1
print(str(max(sum([x > 0 for x in cat[:8]]),1))+' '+str(min(sum([x > 0 for x in cat[:8]])+sum(cat[8:]),8)))
Problem p03730 (python)

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

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

ans = 'YES' if c % gcd(a,b) == 0 else 'NO'

print(ans)

Buggy submission (verdict: Runtime Error):
a,b,c=map(int,input().split())
import math
ans = 'Yes' if c % math.gcd(a,b) == 0 else 'No'
print(ans)
Problem p03732 (python)

Fixed submission:
n,W=map(int,input().split())
wv=[list(map(int,input().split()))]
w0=wv[0][0]-1
wv[0][0]=1
# すべてのwからw0を引く
for _ in range(n-1):
  w,v=list(map(int,input().split()))
  wv.append([w-w0,v])
import numpy as np
dp=np.full((n+1,401),0,int)
# dp[k][w]:k個で重さwでの最大価値
dp[0]=0
for w,v in wv:
  for i in range(n):
    dp[n-i][w:]=np.maximum(dp[n-i][w:],dp[n-i-1][:-w]+v)
ans=0
for i in range(1,n+1):
  if W-i*w0<=0:break
  ans=max(ans,dp[i][min(W-i*w0,400)])
print(ans)

Buggy submission (verdict: Runtime Error):
n,W=map(int,input().split())
wv=[list(map(int,input().split()))]
w0=wv[0][0]-1
wv[0][0]=1
# すべてのwからw0を引く
for _ in range(n-1):
  w,v=list(map(int,input().split()))
  wv.append([w-w0,v])
import numpy as np
dp=np.full((n+1,401),0,int)
# dp[k][w]:k個で重さwでの最大価値
dp[0]=0
for w,v in wv:
  for i in range(n):
    dp[n-i][w:]=np.maximum(dp[n-i][w:],dp[n-i-1][:-w]+v)
ans=0
for i in range(1,n+1):
  if W-i*w0<=0:break
  ans=max(ans,dp[i][W-i*w0])
print(ans)

Buggy submission (verdict: Runtime Error):
n,W=map(int,input().split())
wv=[list(map(int,input().split()))]
w0=wv[0][0]-1
wv[0][0]=1
# すべてのwからw0を引く
for _ in range(n-1):
  w,v=list(map(int,input().split()))
  wv.append([w-w0,v])
import numpy as np
dp=np.full((n+1,301),0,int)
# dp[k][w]:k個で重さwでの最大価値
dp[0]=0
for w,v in wv:
  for i in range(n):
    dp[n-i][w:]=np.maximum(dp[n-i][w:],dp[n-i-1][:-w]+v)
ans=0
for i in range(1,n+1):
  if W-i*w0<=0:break
  ans=max(ans,dp[i][W-i*w0])
print(ans)
Problem p03912 (python)

Fixed submission:
def main():
  n,m=map(int,input().split())
  x=list(map(int,input().split()))
  #xmod=[y%m for y in x]
  from collections import Counter
  cx=Counter(x)
  cxmod={}
  for k in cx:
    if k%m in cxmod:
      cxmod[k%m]+=cx[k]
    else:
      cxmod[k%m]=cx[k]
  keys=cxmod.keys()
  ans1,ans2=0,0 # ams1:m倍になるペア、ans2:同数のペア。ans1からもとめる
  for k in keys:
    if k==0:
      ans1+=cxmod[k]//2
      cxmod[k]-=2*(cxmod[k]//2)
    else:
      if k==m-k:
        ans1+=cxmod[k]//2
        cxmod[k]-=2*(cxmod[k]//2)
      elif m-k in keys:
        tmp=min(cxmod[k],cxmod[m-k])
        ans1+=tmp
        cxmod[k]-=tmp
        cxmod[m-k]-=tmp
  for k in cx:
    v=cx[k]
    if v>=2 and cxmod[k%m]>=2:
      tmp=min(v//2,cxmod[k%m]//2)
      ans2+=tmp
      cxmod[k%m]-=tmp*2

  print(ans1+ans2)
if __name__=='__main__':
  main()

Buggy submission (verdict: Runtime Error):
def main():
  n,m=map(int,input().split())
  x=list(map(int,input().split()))
  xmod=[y%m for y in x]
  from collections import Counter
  cx=dict(Counter(x))
  cxmod=dict(Counter(xmod))
  ans1,ans2=0,0 # ams1:m倍になるペア、ans2:同数のペア。ans1からもとめる
  for k in cxmod.keys():
    if k==0:
      ans1+=cxmod[k]//2
      cxmod[k]-=2*(cxmod[k]//2)
    else:
      if k==m-k:
        ans1+=cxmod[k]//2
        cxmod[k]-=2*(cxmod[k]//2)
      elif m-k in keys:
        tmp=min(cxmod[k],cxmod[m-k])
        ans1+=tmp
        cxmod[k]-=tmp
        cxmod[m-k]-=tmp
  for k in cx:
    v=cx[k]
    if v>=2 and cxmod[k%m]>=2:
      tmp=min(v//2,cxmod[k%m]//2)
      ans2+=tmp
      cxmod[k%m]-=tmp*2

  print(ans1+ans2)
if __name__=='__main__':
  main()