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

Fixed submission:
import bisect

A, B, Q=map(int, input().split())
s=[int(input()) for _ in range(A)]
t=[int(input()) for _ in range(B)]
x=[int(input()) for _ in range(Q)]

st=[0]*A
ts=[0]*B

for i in range(A):
  tmp=bisect.bisect_left(t, s[i])
  if tmp==0:
    st[i]=t[0]-s[i]
  elif tmp==B:
    st[i]=s[i]-t[-1]
  else:
    st[i]=min(s[i]-t[tmp-1], t[tmp]-s[i])
    
for i in range(B):
  tmp=bisect.bisect_left(s, t[i])
  if tmp==0:
    ts[i]=s[0]-t[i]
  elif tmp==A:
    ts[i]=t[i]-s[-1]
  else:
    ts[i]=min(t[i]-s[tmp-1], s[tmp]-t[i])

for i in range(Q):
  cand=set()
  tmp=bisect.bisect_left(s, x[i])
  if tmp>0:
    cand.add(x[i]-s[tmp-1]+st[tmp-1])
  if tmp<A:
    cand.add(s[tmp]-x[i]+st[tmp])
    
  tmp=bisect.bisect_left(t, x[i])
  if tmp>0:
    cand.add(x[i]-t[tmp-1]+ts[tmp-1])
  if tmp<B:
    cand.add(t[tmp]-x[i]+ts[tmp])
    
  print(min(cand))

Buggy submission (verdict: Runtime Error):
import numpy as np
A, B, Q=map(int, input().split())
s=[int(input()) for _ in range(A)]
t=[int(input()) for _ in range(B)]
x=[int(input()) for _ in range(Q)]

def f(nums, a):
  if a<=nums[0]:
    return nums[0]-a
  if nums[-1]<=a:
    return a-nums[-1]
  tmp=np.searchsorted(nums, a, side='left')
  return min(a-nums[tmp-1], nums[tmp]-a)

for i in range(Q):
  out=2*10**10
  if x[i]<=s[0]:
    s2=s[0]
    out=min(out, s2-x[i]+f(t, s2))
  elif s[-1]<=x[i]:
    s1=s[-1]
    out=min(out, x[i]-s1+f(t, s1))
  else:
    tmp=np.searchsorted(s, x[i], side='left')
    s1=s[tmp-1]
    out=min(out, x[i]-s1+f(t, s1))
    s2=s[tmp]
    out=min(out, s2-x[i]+f(t, s2))
    
  if x[i]<=t[0]:
    t2=t[0]
    out=min(out, t2-x[i]+f(s, t2))
  elif t[-1]<=x[i]:
    t1=t[-1]
    out=min(out, x[i]-t1+f(s, t1))
  else:
    tmp=np.searchsorted(t, x[i], side='left')
    t1=t[tmp-1]
    out=min(out, x[i]-t1+f(s, t1))
    t2=t[tmp]
    out=min(out, t2-x[i]+f(s, t2))
    
  print(out)
Problem p03240 (python)

Fixed submission:
N=int(input())
xyh=[list(map(int, input().split())) for i in range(N)]
 
for i in range(101):
  for j in range(101):
    check=True
    k=0
    while xyh[k][2]==0:
      k+=1
      
    h=abs(xyh[k][0]-i)+abs(xyh[k][1]-j)+xyh[k][2]
    
    for k in range(N):
      temph=abs(xyh[k][0]-i)+abs(xyh[k][1]-j)+xyh[k][2]
      if xyh[k][2]==0:
        if temph<h:
          check=False
      else:
        if h!=temph:
          check=False
        
    if check==True and 0<h:
        print(' '.join([str(i), str(j), str(h)]))
        exit()
        
sonnnakannsuuhateigisiteinai()

Buggy submission (verdict: Runtime Error):
N=int(input())
xyh=[list(map(int, input().split())) for i in range(N)]
 
for i in range(101):
  for j in range(101):
    check=True
    k=0
    while xyh[k][2]==0:
      k+=1
      
    h=abs(xyh[k][0]-i)+abs(xyh[k][1]-j)+xyh[k][2]
    
    for k in range(N):
      temph=abs(xyh[k][0]-i)+abs(xyh[k][1]-j)+xyh[k][2]
      if xyh[k][2]==0:
        if temph<=h:
          check=False
      else:
        if h!=temph:
          check=False
        
    if check==True and 0<h:
        print(' '.join([str(i), str(j), str(h)]))
        exit()
        
sonnnakannsuuhateigisiteinai()

Buggy submission (verdict: Runtime Error):
N=int(input())
xyh=[list(map(int, input().split())) for i in range(N)]
 
for i in range(101):
  for j in range(101):
    check=True
    k=0
    while xyh[k][2]==0:
      k+=1
      
    h=abs(xyh[k][0]-i)+abs(xyh[k][1]-j)+xyh[k][2]
    
    for k in range(N):
      temph=abs(xyh[k][0]-i)+abs(xyh[k][1]-j)+xyh[k][2]
      if xyh[k][2]==0:
        if temph<=h:
          check=False
      else:
        if h!=temph:
          check=False
        
    if check==True and 0<h:
        print(' '.join([str(i), str(j), str(h)]))
        
sonnnakannsuuhateigisiteinai()

Buggy submission (verdict: Runtime Error):
N=int(input())
xyh=[list(map(int, input().split())) for i in range(N)]

for i in range(101):
  for j in range(101):
    check=True
    h=abs(xyh[0][0]-i)+abs(xyh[0][1]-j)+xyh[0][2]
    
    for k in range(1, N):
      temph=abs(xyh[k][0]-i)+abs(xyh[k][1]-j)+xyh[k][2]
      if h!=temph:
        check=False
        
    if check:
      if 0<=h and h<=pow(10, 9):
      print(' '.join([str(i), str(j), str(h)]))

Buggy submission (verdict: Runtime Error):
N=int(input())
xyh=[list(map(int, input().split())) for i in range(N)]

for i in range(101):
  for j in range(101):
    check=True
    h=abs(xyh[0][0]-i)+abs(xyh[0][1]-j)+xyh[0][2]
    
    for k in range(1, N):
      temph=abs(xyh[k][0]-i)+abs(xyh[k][1]-j)+xyh[k][2]
      if h!=temph:
        check=False
        
    if check:
      if 0<=h<=pow(10, 9):
      print(' '.join([str(i), str(j), str(h)]))
Problem p03263 (python)

Fixed submission:
H, W=map(int, input().split())
a=[list(map(int, input().split())) for i in range(H)]
out=[]
n=0
for i in range(H):
  for j in range(W-1):
    if a[i][j]%2==1:
      n+=1
      a[i][j]-=1
      a[i][j+1]+=1
      out.append([i+1, j+1, i+1, j+2])
      
      
for i in range(H-1):
  if a[i][-1]%2==1:
    n+=1
    a[i][-1]-=1
    a[i+1][-1]+=1
    out.append([i+1, W, i+2, W])
    
print(n)
for i in range(n):
  print(' '.join(map(str, out[i])))

Buggy submission (verdict: Runtime Error):
H, W=map(int, input().split())
a=[list(map(int, input().split())) for i in range(H)]
out=[]
n=0
for i in range(H):
  for j in range(W-1):
    if a[i][j]%2==1:
      n+=1
      a[i][j]-=1
      a[i][j+1]+=1
      out.append([i+1, j+1, i+1, j+2])
      
      
for i in range(H):
  if a[i][-1]%2==1:
    n+=1
    a[i][-1]-=1
    a[i+1][-1]+=1
    out.append([i+1, W, i+2, W])
    
print(n)
for i in range(n):
  print(' '.join(map(str, out[i])))
Problem p03424 (python)

Fixed submission:
N=int(input())
S=list(input().split())
X=set()
for s in S:
  X.add(s)
  
if len(X)==3:
  print('Three')
else:
  print('Four')

Buggy submission (verdict: Runtime Error):
N=int(input())
S=list(map(int, input().split()))
X=set()
for s in S:
  X.add(s)
  
if len(X)==3:
  print('Three')
else:
  print('Four')
Problem p03436 (python)

Fixed submission:
H, W=map(int, input().split())
m=[[-1 for i in range(W+2)]]
mm=[[-1]+[0 for j in range(W)]+[-1] for i in range(H)]
m=m+mm+m
m[1][1]=1

counter0=0
for i in range(1, H+1):
  c=input()
  for j in range(1, W+1):
    if c[j-1]=='#':
      m[i][j]=-1
    else:
      counter0+=1
      
def f(math, kazu, h, w):
  cha=0
  for i in range(1, h+1):
    for j in range(1, w+1):
      if math[i][j]==kazu:
        if math[i-1][j]==0:
          math[i-1][j]=kazu+1
          cha=1
        if math[i+1][j]==0:
          math[i+1][j]=kazu+1
          cha=1
        if math[i][j-1]==0:
          math[i][j-1]=kazu+1
          cha=1
        if math[i][j+1]==0:
          math[i][j+1]=kazu+1
          cha=1
  return math, cha

cha=1
i=1
while cha==1:
  m, cha=f(m, i, H, W)
  i+=1
  
if m[H][W]==0:
  out=-1
else:
  out=counter0-m[H][W]
  
print(out)

Buggy submission (verdict: Runtime Error):
H, W=map(int, input().split())
m=[[-1 for i in range(W+2)]]
mm=[[-1]+[0 for j in range(W)]+[-1] for i in range(H)]
m=m+mm+m
m[1][1]=1

counter0=0
for i in range(1, H+1):
  c=input()
  for j in range(1, W+1):
    if c[j-1]=='#':
      mm[i][j]=-1
    else:
      counter0+=1
      
def f(math, kazu, h, w):
  cha=0
  for i in range(1, h+1):
    for j in range(1, w+1):
      if math[i][j]==kazu:
        if math[i-1][j]==0:
          math[i-1][j]=kazu+1
          cha=1
        if math[i+1][j]==0:
          math[i+1][j]=kazu+1
          cha=1
        if math[i][j-1]==0:
          math[i][j-1]=kazu+1
          cha=1
        if math[i][j+1]==0:
          math[i][j+1]=kazu+1
          cha=1
  return math, cha

cha=1
i=1
while cha==1:
  m, cha=f(m, i, H, W)
  i+=1
  
if m[H][W]==0:
  out=-1
else:
  out=counter0-m[H][W]
  
print(out)
Problem p03452 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10**5)

def f(hito, zahyo):
  x[hito]=zahyo
  for tsugi in links[hito]:
    if x[tsugi[0]]==None:
      f(tsugi[0], zahyo+tsugi[1])
    else:
      if x[tsugi[0]]!=zahyo+tsugi[1]:
        print('No')
        exit()

N, M=map(int, input().split())
links=[[] for _ in range(N+1)]
for _ in range(M):
  l, r, d=map(int, input().split())
  links[l].append([r, d])
  links[r].append([l, -d])
  
x=[None]*(N+1)
for i in range(1, N+1):
  if x[i]==None:
    f(i, 0)
    
print('Yes')

Buggy submission (verdict: Runtime Error):
def f(hito, zahyo, mae=0):
  x[hito]=zahyo
  for tsugi in links[hito]:
    if tsugi[0]==mae:
      continue
      
    if x[tsugi[0]]==None:
      f(tsugi[0], zahyo+tsugi[1], hito)
    else:
      if x[tsugi[0]]==zahyo+tsugi[1]:
        pass
      else:
        print('No')
        exit()

N, M=map(int, input().split())
links=[[] for _ in range(N+1)]
for _ in range(M):
  l, r, d=map(int, input().split())
  links[l].append([r, d])
  links[r].append([l, -d])
  
x=[None]*(N+1)
for i in range(1, N+1):
  if x[i]==None:
    f(i, 0)
    
print('Yes')
Problem p03501 (python)

Fixed submission:
N, A, B=map(int, input().split())
print(min(A*N, B))

Buggy submission (verdict: Runtime Error):
N, A, B=map(int, input().split())
print(min(A*T, B))
Problem p03547 (python)

Fixed submission:
x, y=input().split()
alp='ABCDEF'
if x==y:
  print('=')
elif alp.index(x)<alp.index(y):
  print('<')
else:
  print('>')

Buggy submission (verdict: Runtime Error):
x, y=map(int, input().split())
alp='ABCDEF'
if x==y:
  print('=')
elif alp.index(x)<alp.index(y):
  print('<')
else:
  print('>')
Problem p03599 (python)

Fixed submission:
a, b, c, d, e, f=map(int, input().split())
def g(x, y):
  if y==0:
    return 0
  else:
    return x/y
  
maxnodo=g(e, 100+e)
a*=100
b*=100

candnodo=0
out=[a, 0]
q_max=f//b
for q in range(q_max, -1, -1):
  p_max=(f-b*q)//a
  for p in range(p_max, -1, -1):
    s_max=(f-(a*p+b*q))//d
    while s_max>0 and g(d*s_max, a*p+b*q+d*s_max)>maxnodo:
      s_max-=1
      
    for s in range(s_max, -1, -1):
      r=(f-(a*p+b*q+d*s))//c
      while r>0 and g(c*r+d*s, a*p+b*q+c*r+d*s)>maxnodo:
        r-=1
        
      if g(c*r+d*s, a*p+b*q+c*r+d*s)>candnodo:
        candnodo=g(c*r+d*s, a*p+b*q+c*r+d*s)
        out=[a*p+b*q+c*r+d*s, c*r+d*s]
        temp=[p, q, r, s]
print(*out)

Buggy submission (verdict: Runtime Error):
a, b, c, d, e, f=map(int, input().split())
def g(x, y):
  if y==0:
    return 0
  else:
    return x/y
  
maxnodo=g(e, 100+e)
a*=100
b*=100

candnodo=0

q_max=f//b
for q in range(q_max, -1, -1):
  p_max=(f-b*q)//a
  for p in range(p_max, -1, -1):
    s_max=(f-(a*p+b*q))//d
    while s_max>0 and g(d*s_max, a*p+b*q+d*s_max)>maxnodo:
      s_max-=1
      
    for s in range(s_max, -1, -1):
      r=(f-(a*p+b*q+d*s))//c
      while r>0 and g(c*r+d*s, a*p+b*q+c*r+d*s)>maxnodo:
        r-=1
        
      if g(c*r+d*s, a*p+b*q+c*r+d*s)>candnodo:
        candnodo=g(c*r+d*s, a*p+b*q+c*r+d*s)
        out=[a*p+b*q+c*r+d*s, c*r+d*s]
        temp=[p, q, r, s]
print(*out)
Problem p03603 (python)

Fixed submission:
N=int(input())
P=list(map(int, input().split()))
X=[0]+list(map(int, input().split()))
ko=[[] for _ in range(N+1)]
for i, p in enumerate(P, 2):
  ko[p].append(i)
  
def f(p):
  n=len(ko[p])
  if n==0:
    return X[p], 0
  
  dp=[[float('inf')]*5001 for _ in range(n+1)]
  dp[0][0]=0
  for i, c in enumerate(ko[p], 1):
    a, b=f(c)
    for j in range(a, 5001):
      dp[i][j]=min(dp[i][j], dp[i-1][j-a]+b)
    for j in range(b, 5001):
      dp[i][j]=min(dp[i][j], dp[i-1][j-b]+a)
      
  out=min(dp[-1][:X[p]+1])
  if out==float('inf'):
    print('IMPOSSIBLE')
    exit()
  elif out>X[p]:
    return out, X[p]
  else:
    return X[p], out
  
print('POSSIBLE') if min(f(1))<=X[1] else print('IMPOSSIBLE')

Buggy submission (verdict: Runtime Error):
N=int(input())
P=list(map(int, input().split()))
X=[0]+list(map(int, input().split()))
ko=[[] for _ in range(N+1)]
for i, p in enumerate(P, 2):
  ko[p].append(i)
  
def f(p):
  n=len(ko[p])
  if n==0:
    return X[p], 0
  
  dp=[[float('inf')]*(X[p]+1) for _ in range(n+1)]
  dp[0][0]=0
  for i, c in enumerate(ko[p], 1):
    a, b=f(c)
    for j in range(a, 5001):
      dp[i][j]=min(dp[i][j], dp[i-1][j-a]+b)
    for j in range(b, 5001):
      dp[i][j]=min(dp[i][j], dp[i-1][j-b]+a)
      
  out=min(dp[-1])
  if out==float('inf'):
    print('IMPOSSIBLE')
    exit()
  elif out>X[p]:
    return out, X[p]
  else:
    return X[p], out
  
print('POSSIBLE') if min(f(1))<=X[1] else print('IMPOSSIBLE')
Problem p03632 (python)

Fixed submission:
A, B, C, D=map(int, input().split())
X=set([i for i in range(A, B)])
print(sum([1 for i in range(C, D) if i in X]))

Buggy submission (verdict: Runtime Error):
A, B, C, D=map(int, input().split())
X=set([for i in range(A, B+1)])
print(sum([1 for i in range(C, D+1) if i in X]))
Problem p03645 (python)

Fixed submission:
N, M=map(int, input().split())
x=[]
y=[]
for i in range(M):
  a, b=map(int, input().split())
  if a==1:
    x.append(b)
  if b==N:
    y.append(a)
    
nx=len(x)
ny=len(y)

if nx==0 or ny==0:
  print('IMPOSSIBLE')
  exit()

x.sort()
y.sort()
i=0
j=0
out='IMPOSSIBLE'

while i+j<nx+ny-1:
  if x[i]==y[j]:
    out='POSSIBLE'
    break
  elif x[i]>y[j]:
    j+=1
  else:
    i+=1
    
print(out)

Buggy submission (verdict: Runtime Error):
N, M=map(int, input().split())
x=[]
y=[]
for i in range(M):
  a, b=map(int, input().split())
  if a==1:
    x.append(b)
  if b==1:
    x.append(a)
  if a==N:
    y.append(b)
  if b==N:
    y.append(a)
    
x.sort()
y.sort()
i=0
j=0
out='IMPOSSIBLE'
nx=len(x)
ny=len(y)
while i+j<nx+ny-1:
  if x[i]==y[j]:
    out='POSSIBLE'
    break
  elif x[i]>y[j]:
    j+=1
  else:
    i+=1
    
print(out)
Problem p03695 (python)

Fixed submission:
N=int(input())
a=list(map(int, input().split()))
c=[0]*9
for i in range(N):
  c[min(a[i]//400, 8)]+=1
  
temp=[1 for i in range(8) if c[i]>0]
x=len(temp)
y=x+c[8]
 
print(max(x, 1), y)

Buggy submission (verdict: Runtime Error):
N=int(input())
a=list(map(int, input().split()))
c=[0]*9
for i in range(N):
  c[a[i]//400]+=1
  
temp=[1 for i in range(8) if c[i]>0]
x=len(temp)
y=min(8, x+c[8])

print(x, y)

Buggy submission (verdict: Runtime Error):
N=int(input())
a=list(map(int, input().split()))
c=[0]*9
for i in range(N):
  c[a[i]//400]+=1
  
x=sum([1 for i in range(8) if c[i]>0])
y=min(8, x+c[8])

print(x, y)
Problem p02606 (python)

Fixed submission:
L, R, d = map(int, input().split())
  
cnt = 0
for i in range(L, R+1, 1):
  if i % d == 0:
    cnt += 1

print(cnt)

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

cnt = 0
for i in range(0, len(l), 2):
  if l[i] % 2 != 0:
    cnt += 1

print(cnt)

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

cnt = 0
for i in range(0, min(N, len(l)), 2):
  if l[i] % 2 != 0:
    cnt += 1

print(cnt)

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

cnt = 0
for i in range(0, N, 2):
  if l[i] % 2 != 0:
    cnt += 1

print(cnt)

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

cnt = 0
for i in range(1, N+1, 2):
  if l[i-1] % 2 != 0:
    cnt += 1

print(cnt)
Problem p02612 (python)

Fixed submission:
N = int(input())
if N % 1000 == 0:
  print(0)
else:
  print(1000 - N % 1000)

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

if N < 1000:
  out = 1000 - N
elif N % 1000 < 500:
  out = N % 1000
else:
  out = 1000 - N % 1000

print(out)

Buggy submission (verdict: Runtime Error):
N = input()
  
if N < 1000:
  out = 1000 - N
elif N % 1000 < 500:
  out = N % 1000
else:
  out = 1000 - N % 1000

print(out)
Problem p02782 (python)

Fixed submission:
#F
from operator import mul
from functools import reduce

r1, c1, r2, c2 = [int(i) for i in input().split()]
mod = 10**9 + 7

#pre-caluculation of the factorial
num = 10**6*2+3
fact=[0] * num
fact[0]=1
for i in range(1, num):
    fact[i] = (fact[i-1] * i) % mod

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

def f(rr,cc):
    #(0,0)~(r,c)までのコンビネーションの累積和
    #print(rr+cc+2, cc+1)
    #print(combinations_count(rr+cc+2, cc+1))
    #return combinations_count(rr+cc+2, cc+1) - 1
    return (fact[rr+cc+2]%mod * pow(fact[rr+1]*fact[cc+1], mod-2, mod)) % mod -1

ans = f(r2, c2) - f(r2, c1-1) - f(r1-1, c2) + f(r1-1, c1-1)
print(ans % mod)

Buggy submission (verdict: Runtime Error):
#F
from operator import mul
from functools import reduce

r1, c1, r2, c2 = [int(i) for i in input().split()]
mod = 10**9 + 7

#pre-caluculation of the factorial
num = 10**6
fact=[0] * num
fact[0]=1
for i in range(1, num):
    fact[i] = (fact[i-1] * i) % mod

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

def f(rr,cc):
    #(0,0)~(r,c)までのコンビネーションの累積和
    #print(rr+cc+2, cc+1)
    #print(combinations_count(rr+cc+2, cc+1))
    #return combinations_count(rr+cc+2, cc+1) - 1
    return (fact[rr+cc+2]%mod * pow(fact[rr+1]*fact[cc+1], mod-2, mod)) % mod -1

ans = f(r2, c2) - f(r2, c1-1) - f(r1-1, c2) + f(r1-1, c1-1)
print(ans % mod)
Problem p02822 (python)

Fixed submission:
#f
import sys
sys.setrecursionlimit(2 * 10 ** 5 + 10)
 

n = int(input())
E = [[] for _ in range(n)]
mod = 10**9 + 7

for i in range(n-1):
    a,b = [int(x) for x in input().split()]
    E[a-1].append((b-1, i)) 
    E[b-1].append((a-1, i)) 
    
X = [0] * n
    
def dfs(u,e):
    num = 1
    for v,c in E[u]:
        if c != e:
            num += dfs(v,c)
    X[e] = num 
    return num

dfs(0, -1)

I = [1]
inv = pow(2, mod-2, mod)
for i in range(n):
    I.append(I[-1] * inv % mod)

ans = 0
for i in range(n):
    x = X[i]
    ans += (1-I[x])*(1-I[n-x]) % mod
    
ans -= n * I[1]
ans += 1 - I[n]
ans %= mod
print(ans)

Buggy submission (verdict: Runtime Error):
#f
sys.setrecursionlimit(2 * 10 ** 5 + 10)


n = int(input())
E = [[] for _ in range(n)]
mod = 10**9 + 7

for i in range(n-1):
    a,b = [int(x) for x in input().split()]
    E[a-1].append((b-1, i)) 
    E[b-1].append((a-1, i)) 
    
X = [0] * n
    
def dfs(u,e):
    num = 1
    for v,c in E[u]:
        if c != e:
            num += dfs(v,c)
    X[e] = num 
    return num

dfs(0, -1)

I = [1]
for i in range(n):
    I.append(I[-1] * pow(2, mod-2, mod) % mod)

ans = 0
for i in range(n):
    x = X[i]
    ans += (1-I[x])*(1-I[n-x]) % mod
    
ans -= n * I[1]
ans += 1 - I[n]
ans %= mod
print(ans)

Buggy submission (verdict: Runtime Error):
#f

n = int(input())
E = [[] for _ in range(n)]
mod = 10**9 + 7

for i in range(n-1):
    a,b = [int(x) for x in input().split()]
    E[a-1].append((b-1, i)) 
    E[b-1].append((a-1, i)) 
    
X = [0] * n
    
def dfs(u,e):
    num = 1
    for v,c in E[u]:
        if c != e:
            num += dfs(v,c)
    X[e] = num 
    return num

dfs(0, -1)

I = [1]
for i in range(n):
    I.append(I[-1] * pow(2, mod-2, mod) % mod)

ans = 0
for i in range(n):
    x = X[i]
    ans += (1-I[x])*(1-I[n-x]) % mod
    
ans -= n * I[1]
ans += 1 - I[n]
ans %= mod
print(ans)

Buggy submission (verdict: Runtime Error):
#f

n = int(input())
E = [[] for _ in range(n)]
mod = 10**9 + 7

for i in range(n-1):
    a,b = [int(x) for x in input().split()]
    E[a-1].append((b-1, i)) 
    E[b-1].append((a-1, i)) 
    
X = [0] * n
    
def dfs(u,e):
    num = 1
    for v,c in E[u]:
        if c != e:
            num += dfs(v,c)
    X[e] = num 
    return num

dfs(0, -1)

I = [1]
for i in range(n):
    I.append(I[-1] * pow(2, mod-2, mod) % mod)

ans = 0
for i in range(n):
    x = X[i]
    ans += (1-I[x])*(1-I[n-x])
    
ans -= n * I[1]
ans += 1 - I[n]
ans %= mod
print(ans)

Buggy submission (verdict: Runtime Error):
#f

n = int(input())
E = [[] for _ in range(n)]
mod = 10**9 + 7

for i in range(n-1):
    a,b = [int(x) for x in input().split()]
    E[a-1].append((b-1, i)) 
    E[b-1].append((a-1, i)) 
    
X = [0] * n
    
def dfs(u,e):
    num = 1
    for v,c in E[u]:
        if c != e:
            num += dfs(v,c)
    X[e] = num 
    return num

dfs(0, -1)

I = [1]
for i in range(n):
    I.append(I[-1] * pow(2, mod-2, mod) % mod)

ans = 0
for i in range(n):
    ans += (1-I[i])*(1-I[n-i])
    
ans -= n * I[1]
ans += 1 - I[n]
ans %= mod
print(ans)
Problem p02900 (python)

Fixed submission:
#素因数分解をする
from fractions import gcd
import numpy as np
a,b = [int(i) for i in input().split()]
g = gcd(a,b)

primes = []
n=1

#約数に関して、常に、これが言える。
while n**2 <=g:
    n += 1
    q,r = divmod(g,n)
    if r!=0:
        continue
    while r==0:
        g = q
        q,r = divmod(g,n)
    primes.append(n)

#最後に素数が余るケース    
if g != 1:
    primes.append(g)
    
print(len(primes)+1)

Buggy submission (verdict: Runtime Error):
#素因数分解をする
from fraction import gcd
import numpy as np
a,b = [int(i) for i in input().split()]
g = gcd(a,b)

primes = []
n=1

#約数に関して、常に、これが言える。
while n**2 <=g:
    n += 1
    q,r = divmod(g,n)
    if r!=0:
        continue
    while r==0:
        g = q
        q,r = divmod(g,n)
    primes.append(n)

#最後に素数が余るケース    
if g != 1:
    primes.append(g)
    
print(len(primes)+1)

Buggy submission (verdict: Runtime Error):
#素因数分解をする
from math import gcd
import numpy as np
a,b = [int(i) for i in input().split()]
g = gcd(a,b)

primes = []
n=1

#約数に関して、常に、これが言える。
while n**2 <=g:
    n += 1
    q,r = divmod(g,n)
    if r!=0:
        continue
    while r==0:
        g = q
        q,r = divmod(g,n)
    primes.append(n)

#最後に素数が余るケース    
if g != 1:
    primes.append(g)
    
print(len(primes)+1)
Problem p02901 (python)

Fixed submission:
#dpがやや特殊なので、1次元的に走査したほうがよさそう。initializeもいらないし。
n,m = map(int, input().split())

inf = 10**9

dp =[inf for _ in range(2**n)]
dp[0] = 0

for i in range(m):
    a,b = map(int, input().split())
    d = sum((1<<(i-1)) for i in map(int, input().split()))
  
    for j in range(2**n):
        jord = j | d
        dp[jord] = min(dp[jord], dp[j] + a)
            
if dp[-1] == inf:
    print(-1)
else:
    print(dp[-1])

Buggy submission (verdict: Runtime Error):
#dpがやや特殊なので、1次元的に走査したほうがよさそう。initializeもいらないし。
n,m = map(int, input().split())

inf = 10**9

dp =[inf for _ in range(2**n)]
dp[0] = 0

for i in range(m):
    a,b = map(int, input().split())
    d = sum((1<<(i-1)) for i in map(int, input().split()))
  
    for j in range(2**n):
        jord = j | d
        dp[i][jord] = min(dp[i][jord], dp[i][j] + a)
            
if dp[-1] == inf:
    print(-1)
else:
    print(dp[-1])

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

dp = [[int("inf") for _ in range(2**n)] for _ in range(m)]
dp[0][0] = 0

for i in range(m):
    a,b = map(int, input().split())
    d = sum((1<<(i-1)) for i in map(int, input().split()))
    for j in range(2**n):
        jord = j | d
        
        #initialize
        if i==0:
            dp[0][d] = a
        else:
            dp[i][jord] = min(dp[i-1][jord], dp[i-1][j] + a)
            
if dp[m-1][2**n-1] == int("inf"):
    print(-1)
else:
    print(dp[m-1][2**n-1])
Problem p02937 (python)

Fixed submission:
from collections import defaultdict
import bisect

s = input()
t = input()

n = len(s)
m = len(t)

d = defaultdict(list)

for i,c in enumerate(s):
    if c in t:
        d[c].append(i)

for i,c in enumerate(s):
    if c in t:
        d[c].append(i+n)

pos = -1
ans = 0

for c in t:
    l = d[c]
    if l:
        ind = bisect.bisect_right(l, pos)
        ans += l[ind]-pos
        if l[ind] >= n:
            pos = l[ind] - n
        else:
            pos = l[ind]    
    else:
        ans = -1
        break

print(ans)

Buggy submission (verdict: Runtime Error):
#138-e
from collections import defaultdict
import bisect

s = input()
t = input()
n = len(s)
m = len(t)

ans=0
pos=-1

d = defaultdict(list)
for i in range(n):
    if s[i] in t:
        d[s[i]].append(i)
        
for i in range(n):
    if s[i] in t:
        d[s[i]].append(i+n)
        
for v in t:
    l = d[v]
    ind = bisect.bisect_right(l, pos)
    ans += l[ind]-pos
    if l:
        if l[ind]<n:
            pos = l[ind]
        else:
            pos = l[ind] - n
    else:
        ans = -1
        break
        
print(ans)

Buggy submission (verdict: Runtime Error):
seq = input()
sub = input()

n = len(seq)
m = len(sub)

sums = 0
pos  = -1

for i in range(m):
  char = sub[i]
  add  = 0
  pos += 1
  add += 1
  while(char != seq[pos]):
    add +=1
    pos = (pos + 1) % n
    if add > n :
      print(-1)
      exit()
  sums += add 

print(sums)