Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
n=int(input())
a=list(map(int,input().split()))

cnt=0
for i in a:
  if i%2=1:
    cnt+=1
    
if cnt%2==1:
  print('NO')
  
else:
  print('YES')

Fixed submission:
n=int(input())
x=list(map(int,input().split()))
a=[]
for i in x:
  if i%2==1:
      a+=[i]
if len(a)%2==1:
  print('NO')
else:
  print('YES')

Buggy python submission (verdict: Runtime Error):
n=int(input())
a=list(map(int,input().split()))
a=[i if i%2==1 else None  for i in a]
if a.count()%2==1:
  print('NO')
else:
  print('YES')

Fixed submission:
n=int(input())
x=list(map(int,input().split()))
a=[]
for i in x:
  if i%2==1:
      a+=[i]
if len(a)%2==1:
  print('NO')
else:
  print('YES')
Buggy python submission (verdict: Runtime Error):
cnt=0
k,s=map(int,input().split())
for i in range(k+1):
    for j in range(k+1):
        if (0<=s-x-y<=k):
                cnt+=1
print(cnt)


Fixed submission:
cnt=0
k,s=map(int,input().split())
for i in range(k+1):
    for j in range(k+1):
        if (0<=s-i-j<=k):
                cnt+=1
print(cnt)

Buggy python submission (verdict: Time Limit Exceeded):
cnt=0
k,s=map(int,input().split())
for i in range(k+1):
    for j in range(k+1):
        for k in range(k+1):
            if i+j+k==s:
                cnt+=1
print(cnt)


Fixed submission:
cnt=0
k,s=map(int,input().split())
for i in range(k+1):
    for j in range(k+1):
        if (0<=s-i-j<=k):
                cnt+=1
print(cnt)
Buggy python submission (verdict: Runtime Error):
x,y=map(int,input().split())

ans=abs(abs(x)-abs(y))

if y<x<0 or 0<y<x:
    ans+=2

elif y<x x<0<y:
    ans+=1

print(ans)

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

ans=abs(abs(x)-abs(y))

if y<x<0 or 0<y<x:
    ans+=2

elif y<x or x<0<y:
    ans+=1

print(ans)
Buggy python submission (verdict: Runtime Error):
n=int(input())
a=list(map(int,input().split()))
m=int(input())
b=[map(int,input().split()) for _ in range(m)]
for i in b:
    print(sum(a)-a[i[0]]+i[1])

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
m=int(input())
for i in range(m):
    s,t=map(int,input().split())
    print(sum(a)-a[s-1]+t)
Buggy python submission (verdict: Runtime Error):
c=input()
if c== ['a'|'i'|'u'|'e'|'o']:
  print('vowel')
else:
  print('consonant')


Fixed submission:
c=input()
if c in ['a','i','u','e','o']:
  print('vowel')
else:
  print('consonant')

Buggy python submission (verdict: Runtime Error):
c=input()
if c== 'a'|'i'|'u'|'e'|'o':
  print('vowel')
else:
  print('consonant')

Fixed submission:
c=input()
if c in ['a','i','u','e','o']:
  print('vowel')
else:
  print('consonant')
Buggy python submission (verdict: Time Limit Exceeded):
a,b,x=map(int,input().split())
ans=(b-a+1)//x
z=(b-a+1)%x
for i in range(a,a+z):
  if i%x==0:
    ans+=1
    break
print(ans)

Fixed submission:
a,b,x=map(int,input().split())
if a>2:
  s=b//x
  t=(a-1)//x
  print(s-t)
elif a==1:
  print(b//x)
elif a==0:
  print(b//x+1)
Buggy python submission (verdict: Runtime Error):
s=list(input())
ans=0
pin=s[0]
for i in s[1:]:
  if s[i]==pin:
    ans+=1
    pin=s[i]
print(ans)

Fixed submission:
s=list(input())
ans=0
pin=s[0]
for i in range(1,len(s)):
  if s[i]!=pin:
    ans+=1
    pin=s[i]
print(ans)
Buggy python submission (verdict: Runtime Error):
n=int(input())
s=input()
t=input()
while True:
  if s==t:
    break
  s=s[1:]
  t=[:-1]
  n+=1
print(n)

Fixed submission:
n=int(input())
s=input()
t=input()
while True:
  if s==t:
    break
  s=s[1:]
  t=t[:-1]
  n+=1
print(n)
Buggy python submission (verdict: Runtime Error):
s=input()
ans='No'
for i in range(len(s)):
  if s[i]=='C':
    for j in s[i+1:]:
      if s[j]=='F':
        ans='Yes'
print(ans)

Fixed submission:
s=input()
ans='No'
for i in range(len(s)):
  if s[i]=='C':
    for j in s[i+1:]:
      if j=='F':
        ans='Yes'
print(ans)
Buggy python submission (verdict: Runtime Error):
s=int(input())
t='CODEFESTIVAL2016'
ans=0
for i in range(16):
  if s[i]!=t[i]:
    ans+=1
print(ans)


Fixed submission:
s=input()
t='CODEFESTIVAL2016'
ans=0
for i in range(16):
  if s[i]!=t[i]:
    ans+=1
print(ans)

Buggy python submission (verdict: Runtime Error):
s=int(input())
t='CODEFESTIVAL2016'
ans=0
for i in range(16):
  if s!=t:
    ans+=1
print(ans)

Fixed submission:
s=input()
t='CODEFESTIVAL2016'
ans=0
for i in range(16):
  if s[i]!=t[i]:
    ans+=1
print(ans)
Buggy python submission (verdict: Runtime Error):
a=list(input())
b=list(input())
c=list(input())
order='a'
while True:
  if order='a':
    order=a[0]
    if len(a)==1:
      print('A')
      break
    else:
      a=a[1:]
  elif order='b':
    order=b[0]
    if len(b)==1:
      print('B')
      break
    else:
      b=b[1:]
  elif order='c':
    order=c[0]
    if len(c)==1:
      print('C')
      break
    else:
      c=c[1:]

Fixed submission:
a=list(input())
b=list(input())
c=list(input())
order='a'
while True:
  if order=='a':
    if len(a)==0:
      print('A')
      break
    else:
      order=a[0]
      a=a[1:]
  elif order=='b':
    if len(b)==0:
      print('B')
      break
    else:
      order=b[0]
      b=b[1:]
  elif order=='c':
    if len(c)==0:
      print('C')
      break
    else:
      order=c[0]
      c=c[1:]

Buggy python submission (verdict: Runtime Error):
a=list(input())
b=list(input())
c=list(input())
x=a
y=''
While True:
  y=x[0]
  x.pop(0)
  x=y
  if len(a)==0:
    print('A'):
      break
  if len(b)==0:
    print('B')
    break
  if len(c)==0:
    print('C')
    break

Fixed submission:
a=list(input())
b=list(input())
c=list(input())
order='a'
while True:
  if order=='a':
    if len(a)==0:
      print('A')
      break
    else:
      order=a[0]
      a=a[1:]
  elif order=='b':
    if len(b)==0:
      print('B')
      break
    else:
      order=b[0]
      b=b[1:]
  elif order=='c':
    if len(c)==0:
      print('C')
      break
    else:
      order=c[0]
      c=c[1:]
Buggy python submission (verdict: Runtime Error):
n,a=map(int,input().split())
lst=list(map(int,input().split()))

z=len(lst)
dp=[[[0]*2501 for i in range(51)] for j in range(z+1)]
dp[0][0][0]=1

for i in range(z):
  x=lst[i]
  for j in range(i+1):
    for k in range((i+1)*50):
      dp[i+1][j][k]+=dp[i][j][k]
      dp[i+1][j+1][k+x]+=dp[i][j][k]

ans=0

for i in range(50):
  ans+=dp[-1][i][i*a]

print(ans-1)


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

z=len(lst)
dp=[[[0]*2501 for i in range(51)] for j in range(z+1)]
dp[0][0][0]=1

for i in range(z):
  x=lst[i]
  for j in range(z):
    for k in range(2451):
      dp[i+1][j][k]+=dp[i][j][k]
      dp[i+1][j+1][k+x]+=dp[i][j][k]

ans=0

for i in range(z+1):
  ans+=dp[-1][i][i*a]

print(ans-1)
Buggy python submission (verdict: Runtime Error):
s=input()
x=''
for i in s:
    if i=='B':
        if i!='':
            x=x.replace(x[-1],'')
    else:
        x+=i
print(x)

Fixed submission:
s=input()
x=''
for i in s:
    if i=='B':
        if x!='':
            x=x[:-1]
    else:
        x+=i
print(x)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
readline = sys.stdin.readline
read = sys.stdin.read

R, C, K = map(int, readline().split())
g = [[-float('inf')]*C for _ in range(R)]
for i in range(K):
    r, c, k = map(int, readline().split())
    r -= 1
    c -= 1
    g[r][c] = k

dp = [[[0]*4 for _ in range(C+1)] for _ in range(R+1)]
for r in range(R):
    for c in range(C):
        # k[0..3] = 0個拾っている状態から3個拾っている状態
        # indexが大きいほど、小さいアイテムとなるので、小さいものから更新していく
        for k in range(2, -1, -1):
            dp[r][c][k+1] = max(
                dp[r][c][k+1],
                dp[r][c][k]+g[r][c]
            )

        for k in range(4):
            dp[r+1][c][0] = max(dp[r+1][c][0], dp[r][c][k])
            dp[r][c+1][k] = max(dp[r][c+1][k], dp[r][c][k])
print(max(dp[R-1][C-1]))


Fixed submission:
R, C, K = map(int, input().split())
g = [[-float('inf')]*C for _ in range(R)]
for i in range(K):
    r, c, k = map(int, input().split())
    r -= 1
    c -= 1
    g[r][c] = k

dp = [[[0]*(C+1) for _ in range(R+1)] for _ in range(4)]
for r in range(R):
    for c in range(C):
        # k[0..3] = 0個拾っている状態から3個拾っている状態
        # indexが大きいほど、小さいアイテムとなるので、小さいものから更新していく
        for k in range(2, -1, -1):
            dp[k+1][r][c] = max(
                dp[k+1][r][c],
                dp[k][r][c]+g[r][c]
            )

        for k in range(4):
            dp[0][r+1][c] = max(dp[0][r+1][c], dp[k][r][c])
            dp[k][r][c+1] = max(dp[k][r][c+1], dp[k][r][c])

ans = 0
for i in range(4):
    ans = max(dp[i][R-1][C-1], ans)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
R, C, K = map(int, input().split())
g = [[-float('inf')]*C for _ in range(R)]
for i in range(K):
    r, c, k = map(int, input().split())
    r -= 1
    c -= 1
    g[r][c] = k

dp = [[[0]*4 for _ in range(C+1)] for _ in range(R+1)]
for r in range(R):
    for c in range(C):
        # k[0..3] = 0個拾っている状態から3個拾っている状態
        # indexが大きいほど、小さいアイテムとなるので、小さいものから更新していく
        for k in range(2, -1, -1):
            dp[r][c][k+1] = max(
                dp[r][c][k+1],
                dp[r][c][k]+g[r][c]
            )

        for k in range(4):
            dp[r+1][c][0] = max(dp[r+1][c][0], dp[r][c][k])
            dp[r][c+1][k] = max(dp[r][c+1][k], dp[r][c][k])
print(max(dp[R-1][C-1]))


Fixed submission:
R, C, K = map(int, input().split())
g = [[-float('inf')]*C for _ in range(R)]
for i in range(K):
    r, c, k = map(int, input().split())
    r -= 1
    c -= 1
    g[r][c] = k

dp = [[[0]*(C+1) for _ in range(R+1)] for _ in range(4)]
for r in range(R):
    for c in range(C):
        # k[0..3] = 0個拾っている状態から3個拾っている状態
        # indexが大きいほど、小さいアイテムとなるので、小さいものから更新していく
        for k in range(2, -1, -1):
            dp[k+1][r][c] = max(
                dp[k+1][r][c],
                dp[k][r][c]+g[r][c]
            )

        for k in range(4):
            dp[0][r+1][c] = max(dp[0][r+1][c], dp[k][r][c])
            dp[k][r][c+1] = max(dp[k][r][c+1], dp[k][r][c])

ans = 0
for i in range(4):
    ans = max(dp[i][R-1][C-1], ans)
print(ans)
Buggy python submission (verdict: Runtime Error):
N, D = map(int, input().split())
ans = 0
D2 = D*D
for i in range(N):
    x, y = map(int, input().split())
    if (x*x+y*y) <= D2:
        ans += 1

print(ans)


Fixed submission:
N, D = map(int, input().split())
ans = 0
D2 = D*D
for i in range(N):
    x, y = map(int, input().split())
    if (x*x+y*y) <= D2:
        ans += 1

print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
c = input().strip()
r = c.count("R")
ans = 0
for i in range(r):
    if c[i] == "W":
        ans += 1
print(ans)


Fixed submission:
N = int(input())
c = input().strip()
r = c.count("R")
ans = 0
for i in range(r):
    if c[i] == "W":
        ans += 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
*A, = map(int, input().split())
c = 1
for i in range(N):
    d = c*A[i]
    if i >= K:
        d //= A[i-K]
        if d > c:
            print("Yes")
        else:
            print("No")
    c = d


Fixed submission:
N, K = map(int, input().split())
*A, = map(int, input().split())
for i in range(N):
    if i >= K:
        if A[i] > A[i-K]:
            print("Yes")
        else:
            print("No")
Buggy python submission (verdict: Time Limit Exceeded):
import math
N = int(input())
for n in range(1, N+1):
    nn = int(n**0.5+1)
    ans = 0
    for x in range(1, nn):
        for y in range(1, nn):
            d = n-x*x-y*y-x*y
            if d < 0:
                break
            for z in range(1, nn):
                zz = z*z+z*(x+y)
                if d == zz:
                    ans += 1
                elif zz > d:
                    break
    print(ans)


Fixed submission:
import math
N = int(input())
for n in range(1, N+1):
    nn = int(n**0.5+1)
    ans = 0
    for x in range(1, nn):
        for y in range(1, nn):
            d = n-x*x-y*y-x*y
            if d < 0:
                break
            l, r = 0, nn
            while (r-l) > 1:
                m = (r+l)//2
                z = m*m+m*(x+y)
                if z == d:
                    ans += 1
                    break
                elif z < d:
                    l = m
                else:
                    r = m
    print(ans)
Buggy python submission (verdict: Runtime Error):
N, M, K = map(int, input().split())
*A, = map(int, input().split())
*B, = map(int, input().split())

for i in range(1, N):
    A[i] += A[i-1]
for i in range(1, M):
    B[i] += B[i-1]

A = [0]+A
B = [0]+B
a, b = 0, M
for i in range(N+1):
    k = K-A[i]
    if k < 0:
        break
    while b[j] > k:
        j -= 1
    ans = max(ans, i+j)

print(ans)

Fixed submission:
import bisect
N, M, K = map(int, input().split())
*A, = map(int, input().split())
*B, = map(int, input().split())
for i in range(1, N):
    A[i] += A[i-1]
for i in range(1, M):
    B[i] += B[i-1]

A = [0]+A
ans = 0
for i in range(N+1):
    b = K-A[i]
    if b < 0:
        break
    j = bisect.bisect_right(B, b)
    if ans < (i+j):
        ans = i+j

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
T = "X"+input()
ans = ""
for i in range(1, len(T)):
    if T[i] == "?":
        if T[i-1] == "D":
            ans += "P"
        else:
            ans += "D"
    else:
        ans += T[i]
print(ans)


Fixed submission:
T = list("X"+input())
for i in range(1, len(T)):
    if T[i] == "?":
        T[i] = "D"

print("".join(T[1:]))
Buggy python submission (verdict: Time Limit Exceeded):
from math import gcd

MOD = 10**9+7
N = int(input())
d = {}
zero = 0
for i in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zero += 1
        continue

    flip = 0
    while not (a > 0 and b > 0):
        a, b = -b, a
        flip ^= 1

    g = gcd(a, b)
    a //= g
    b //= g
    if not (a, b) in d:
        d[(a, b)] = [0, 0]
    d[(a, b)][flip] += 1

ans = 1
for (v1, v2) in d.values():
    ans *= pow(2, v1, MOD) + pow(2, v2, MOD)-1
    ans %= MOD
ans -= 1
ans += zero
ans %= MOD
print(ans)


Fixed submission:
from math import gcd

MOD = 10**9+7
N = int(input())
d = {}
zero = 0
for i in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zero += 1
        continue

    if a < 0 or a == 0 and b < 0:
        a, b = -a, -b
    if b <= 0:
        a, b = -b, a
        flip = 1
    else:
        flip = 0

    g = gcd(a, b)
    a //= g
    b //= g
    if not (a, b) in d:
        d[(a, b)] = [0, 0]
    d[(a, b)][flip] += 1

ans = 1
for (v1, v2) in d.values():
    ans *= pow(2, v1, MOD) + pow(2, v2, MOD)-1
    ans %= MOD
ans -= 1
ans += zero
ans %= MOD
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import bisect
N = int(input())
*A, = map(int, input().split())
t = [[A[i], i] for i in range(N)]
t.sort()

ta = [v for v, i in t]
ti = [i for v, i in t]

ans = 0
for i in range(N):
    r = N-1-ta[i]
    ri = bisect.bisect_right(ta, r, lo=i+1)
    for j in range(i+1, ri):
        if (ta[i]+ta[j]) == abs(ti[i]-ti[j]):
            ans += 1

print(ans)


Fixed submission:
from collections import Counter

N = int(input())
*A, = map(int, input().split())

l = Counter([i-A[i] for i in range(N)])
r = Counter([i+A[i] for i in range(N)])

ans = 0
for k, v in l.items():
    ans += v*r[k]
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import bisect
N = int(input())
*A, = map(int, input().split())
t = [[A[i], i] for i in range(N)]
t.sort()

ta = [v for v, i in t]
ti = [i for v, i in t]

ans = 0
for i in range(N):
    r = N-1-ta[i]
    ri = bisect.bisect_right(ta, r)
    for j in range(i+1, ri):
        if (ta[i]+ta[j]) == abs(ti[i]-ti[j]):
            ans += 1

print(ans)


Fixed submission:
from collections import Counter

N = int(input())
*A, = map(int, input().split())

l = Counter([i-A[i] for i in range(N)])
r = Counter([i+A[i] for i in range(N)])

ans = 0
for k, v in l.items():
    ans += v*r[k]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict


def nC2(n):
    return n*(n-1)//2


N = int(input())
*A, = map(int, input().split())

h = defaultdict(int)
for a in A:
    h[a] += 1

for k in range(N):
    t = A[k]
    h[t] -= 1

    ans = 0
    for a, n in h.items():
        if n >= 2:
            ans += nC2(n)
    print(ans)

    h[t] += 1


Fixed submission:
from collections import defaultdict


def nC2(n):
    if n < 2:
        return 0
    return n*(n-1)//2


N = int(input())
*A, = map(int, input().split())

h = defaultdict(int)
for a in A:
    h[a] += 1

total = 0
for k, v in h.items():
    total += nC2(v)

for k in range(N):
    t = A[k]
    print(total - h[t] + 1)

Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
from scipy.special import comb


def nCr(n, r):
    return comb(n, r, exact=True)


N = int(input())
*A, = map(int, input().split())

h = defaultdict(int)
for a in A:
    h[a] += 1

for k in range(N):
    t = A[k]
    h[t] -= 1

    ans = 0
    for a, n in h.items():
        if n >= 2:
            ans += nCr(n, 2)
    print(ans)

    h[t] += 1


Fixed submission:
from collections import defaultdict


def nC2(n):
    if n < 2:
        return 0
    return n*(n-1)//2


N = int(input())
*A, = map(int, input().split())

h = defaultdict(int)
for a in A:
    h[a] += 1

total = 0
for k, v in h.items():
    total += nC2(v)

for k in range(N):
    t = A[k]
    print(total - h[t] + 1)

Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
from scipy.special import comb


def nCr(n, r):
    return comb(n, r, exact=True)


N = int(input())
*A, = map(int, input().split())

h = defaultdict(int)
for a in A:
    h[a] += 1

for k in range(N):
    t = A[k]
    h[t] -= 1

    ans = 0
    for a, n in h.items():
        if n >= 2:
            ans += nCr(n, 2)
    print(ans)

    h[t] += 1


Fixed submission:
from collections import defaultdict


def nC2(n):
    if n < 2:
        return 0
    return n*(n-1)//2


N = int(input())
*A, = map(int, input().split())

h = defaultdict(int)
for a in A:
    h[a] += 1

total = 0
for k, v in h.items():
    total += nC2(v)

for k in range(N):
    t = A[k]
    print(total - h[t] + 1)
Buggy python submission (verdict: Time Limit Exceeded):
s = input().strip()
q = int(input())
l, r = "", ""
rev = 0
for i in range(q):
    a = input().split()
    t = int(a[0])
    if t == 1:
        rev += 1
    else:
        f = int(a[1])
        c = a[2]
        if f == 1:
            if rev % 2 == 0:
                l = c+l
            else:
                r = r+c
        else:
            if rev % 2 == 0:
                r = r+c
            else:
                l = c+l

if rev % 2 == 0:
    print(l+s+r)
else:
    print(r[::-1]+s[::-1]+l[::-1])


Fixed submission:
s = input().strip()
q = int(input())
l, r = "", ""
rev = 0
for i in range(q):
    a = input().split()
    t = int(a[0])
    if t == 1:
        rev += 1
    else:
        f = int(a[1])
        c = a[2]
        if f == 1:
            if rev % 2 == 0:
                l = c+l
            else:
                r = r+c
        else:
            if rev % 2 == 0:
                r = r+c
            else:
                l = c+l

if rev % 2 == 0:
    print(l+s+r)
else:
    print(r[::-1]+s[::-1]+l[::-1])

Buggy python submission (verdict: Time Limit Exceeded):
s = input().strip()
q = int(input())
for i in range(q):
    a = input().split()
    t = int(a[0])
    if t == 1:
        s = s[::-1]
    else:
        f = int(a[1])
        c = a[2]
        if f == 1:
            s = c+s
        else:
            s = s+c
print(s)


Fixed submission:
s = input().strip()
q = int(input())
l, r = "", ""
rev = 0
for i in range(q):
    a = input().split()
    t = int(a[0])
    if t == 1:
        rev += 1
    else:
        f = int(a[1])
        c = a[2]
        if f == 1:
            if rev % 2 == 0:
                l = c+l
            else:
                r = r+c
        else:
            if rev % 2 == 0:
                r = r+c
            else:
                l = c+l

if rev % 2 == 0:
    print(l+s+r)
else:
    print(r[::-1]+s[::-1]+l[::-1])
Buggy python submission (verdict: Runtime Error):
from math import factorial

N = int(input())
K = int(input())


def ncr(n, r):
    if n <= 0:
        return 0
    return factorial(n) // factorial(r) // factorial(n - r)


def k1(n):
    s = str(n)
    return (len(s) - 1) * 9 + int(s[0])


def k2(n):
    if n < 10:
        return 0
    s = str(n)
    res = ncr(len(s)-1, 2) * 9 * 9
    res += (int(s[0]) - 1) * k1(10 ** (len(s) - 1) - 1) + k1(int(s[1:]))
    return res


def k3(n):
    s = str(n)
    res = ncr(len(s)-1, 3)*9*9*9
    res += (int(s[0]) - 1) * k2(10 ** (len(s) - 1) - 1) + k2(int(s[1:]))
    return res


kf = [k1, k2, k3]
print(kf[K-1](N))


Fixed submission:
# 0でない数字がちょうどK個
S = input().strip()
K = int(input())
N = len(S)

'''
桁DP
dp[i][j][k] := 
i桁目まで使って
j個の0ではない数値を使って
k=0:i桁目までSと一致
  1:S未満(以下？)
'''
dp = [[[0]*2 for _ in range(K+1)] for _ in range(101)]
dp[0][0][0] = 1

for i in range(N):
    for j in range(K+1):
        for k in range(2):
            nd = int(S[i])
            # 0-9まで調べていく
            for d in range(10):
                ni, nj, nk = i+1, j, k
                if d > 0:
                    nj += 1
                if nj > K:
                    continue
                if k == 0:
                    if d > nd:
                        continue
                    elif d != nd:
                        nk = 1
                dp[ni][nj][nk] += dp[i][j][k]

print(sum(dp[N][K]))

Buggy python submission (verdict: Runtime Error):
from math import factorial

N = int(input())
K = int(input())


def ncr(n, r):
    return factorial(n) // factorial(r) // factorial(n - r)


def k1(n):
    s = str(n)
    return (len(s) - 1) * 9 + int(s[0])


def k2(n):
    if n < 10:
        return 0
    s = str(n)
    res = ncr(len(s)-1, 2) * 9 * 9
    res += (int(s[0]) - 1) * k1(10 ** (len(s) - 1) - 1) + k1(int(s[1:]))
    return res


def k3(n):
    s = str(n)
    res = ncr(len(s)-1, 3)*9*9*9
    res += (int(s[0]) - 1) * k2(10 ** (len(s) - 1) - 1) + k2(int(s[1:]))
    return res


kf = [k1, k2, k3]
print(kf[K-1](N))


Fixed submission:
# 0でない数字がちょうどK個
S = input().strip()
K = int(input())
N = len(S)

'''
桁DP
dp[i][j][k] := 
i桁目まで使って
j個の0ではない数値を使って
k=0:i桁目までSと一致
  1:S未満(以下？)
'''
dp = [[[0]*2 for _ in range(K+1)] for _ in range(101)]
dp[0][0][0] = 1

for i in range(N):
    for j in range(K+1):
        for k in range(2):
            nd = int(S[i])
            # 0-9まで調べていく
            for d in range(10):
                ni, nj, nk = i+1, j, k
                if d > 0:
                    nj += 1
                if nj > K:
                    continue
                if k == 0:
                    if d > nd:
                        continue
                    elif d != nd:
                        nk = 1
                dp[ni][nj][nk] += dp[i][j][k]

print(sum(dp[N][K]))
Buggy python submission (verdict: Time Limit Exceeded):
H = int(input())
n = 1
h = H
while True:
    n *= 2
    h = h//2
    if h == 1:
        break
print(n*2-1)


Fixed submission:
H = int(input())
n = 1
h = H
while True:
    if h == 1:
        break
    n *= 2
    h = h//2

print(n*2-1)
Buggy python submission (verdict: Runtime Error):
H, N = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]

dp = [10**9]*(H+1)
dp[0] = 0

for i in range(1, N+1):
    for j in range(H+1):
        a, b = ab[i-1]
        if j < a:
            dp[j] = min([dp[0]+b, dp[j]])
        else:
            dp[j] = min([dp[j-a]+b, dp[j]])
print(dp[N][H])


Fixed submission:
H, N = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]

dp = [10**9]*(H+1)
dp[0] = 0

for i in range(1, N+1):
    for j in range(H+1):
        a, b = ab[i-1]
        if j < a:
            dp[j] = min([dp[0]+b, dp[j]])
        else:
            dp[j] = min([dp[j-a]+b, dp[j]])
print(dp[H])