Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
Q = int(input())
query = [list(input().split()) for _ in range(Q)]
is_reverse = False
for q in query:
    if q[0] == "1":
        is_reverse = not is_reverse
    else:
        if is_reverse:
            if q[1] == "2":
                S = q[2] + S
            else:
                S += q[2]
        else:
            if q[1] == "1":
                S = q[2] + S
            else:
                S += q[2]

if is_reverse:
    print(S[::-1])
else:
    print(S)


Fixed submission:
S = list(input())
Q = int(input())
query = [list(input().split()) for _ in range(Q)]
mae = []
ato = []
is_reverse = False
for q in query:
    if q[0] == "1":
        is_reverse = not is_reverse
    else:
        if is_reverse:
            if q[1] == "2":
                mae.append(q[2])
            else:
                ato.append(q[2])
        else:
            if q[1] == "1":
                mae.append(q[2])
            else:
                ato.append(q[2])
mae.reverse()
mae.extend(S)
mae.extend(ato)
if is_reverse:
    mae.reverse()
    print("".join(mae))
else:
    print("".join(mae))
Buggy python submission (verdict: Time Limit Exceeded):
H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort(reverse=True)
dp = [10**10] * (10**4+5)
dp[0] = 0
# ぴったり倒せるときだけ更新して、答えを出力するときに最小値を出力する
for i in range(len(dp)):
    for a, b in AB:
        dp[i] = min(dp[i], dp[i-a]+b)

print(min(dp[H:]))


Fixed submission:
H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort(reverse=True)
dp = [10**10] * (10**4+5)
dp[0] = 0
# ぴったり倒せるときだけ更新して、答えを出力するときに最小値を出力する
for i in range(len(dp)):
    for a, b in AB:
        dp[i] = min(dp[i], dp[i-a]+b)

print(min(dp[H:]))

Buggy python submission (verdict: Time Limit Exceeded):
H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort(reverse=True)
dp = [10**10] * (10**5)
dp[0] = 0
# ぴったり倒せるときだけ更新して、答えを出力するときに最小値を出力する
for i in range(len(dp)):
    for a, b in AB:
        dp[i] = min(dp[i], dp[i-a]+b)

print(min(dp[H:]))


Fixed submission:
H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort(reverse=True)
dp = [10**10] * (10**4+5)
dp[0] = 0
# ぴったり倒せるときだけ更新して、答えを出力するときに最小値を出力する
for i in range(len(dp)):
    for a, b in AB:
        dp[i] = min(dp[i], dp[i-a]+b)

print(min(dp[H:]))

Buggy python submission (verdict: Runtime Error):
import math
H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

# モンスターの体力を0にすることができる魔力の最小値
dp = [[10**9] * (H+1) for _ in range(N+1)]
for i in range(N+1):
    dp[i][0] = 0


for i in range(1, N+1):
    for j in range(1, H+1):
        # j 倒すモンスターのHP
        a, b = AB[i-1]
        # a 攻撃力
        # b 消耗する魔力
        h = math.ceil(j/a)
        # h AB[i]のみを使った場合に必要な魔力
        dp[i][j] = min(dp[i][j], h*b, dp[i-1][j], dp[i-1][j-a]+b)

print(dp[-1][-1])

Fixed submission:
H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort(reverse=True)
dp = [10**10] * (10**4+5)
dp[0] = 0
# ぴったり倒せるときだけ更新して、答えを出力するときに最小値を出力する
for i in range(len(dp)):
    for a, b in AB:
        dp[i] = min(dp[i], dp[i-a]+b)

print(min(dp[H:]))
Buggy python submission (verdict: Runtime Error):
n = int(input())
XL = [list(map(int, input().split())) for _ in range(n)]
N = 0
for x, l in XL:
    N = max(N, x+l)
# N: 処理する区間の長さ
INF = 2**31-1

LV = (N-1).bit_length()
N0 = 2**LV
data = [0]*(2*N0)
lazy = [0]*(2*N0)

def gindex(l, r):
    L = (l + N0) >> 1; R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1

# 遅延伝搬処理
def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if not v:
            continue
        lazy[2*i-1] += v; lazy[2*i] += v
        data[2*i-1] += v; data[2*i] += v
        lazy[i-1] = 0

# 区間[l, r)にxを加算
def update(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)

    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] += x; data[R-1] += x
        if L & 1:
            lazy[L-1] += x; data[L-1] += x
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[i-1] = min(data[2*i-1], data[2*i])

# 区間[l, r)内の合計を求める
def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r

    s = 0
    while L < R:
        if R & 1:
            R -= 1
            s += data[R-1]
        if L & 1:
            s += data[L-1]
            L += 1
        L >>= 1; R >>= 1
    return s


for x, l in XL:
    update(x-l, x+l, 1)

tmp = [0] * N
for i in range(len(XL)):
    mn = XL[i][0] - XL[i][1]
    mx = XL[i][0] + XL[i][1]
    XL[i].append(query(mn, mx))

XL.sort(key=lambda x:x[2])

LV = (N-1).bit_length()
N0 = 2**LV
data = [0]*(2*N0)
lazy = [0]*(2*N0)

cnt = 0
for x, l, z in XL:
    if query(x-l, x+l) == 0:
        cnt += 1
        update(x-l, x+l, 1)

print(cnt)



Fixed submission:
N = int(input())
XL = [tuple(map(int, input().split())) for _ in range(N)]
XL.sort(key=lambda x: x[0]+x[1])
cnt = 0
now = 10 ** 9 * -1
for x, l in XL:
    if now <= x - l:
        cnt += 1
        now = x + l

print(cnt)
Buggy python submission (verdict: Runtime Error):
from copy import deepcopy
N, u, v = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    edge[a].append(b)
    edge[b].append(a)

aoki = [0] * N
takahasi = [0] * N
dist_list = [0] * N
def dfs(pv, v, dist):
    dist_list[v] = dist
    for nv in edge[v]:
        if nv == pv:
            continue
        dfs(v, nv, dist+1)

dfs(-1,u-1,0)
takahasi = deepcopy(dist_list)
dist_list = [0] * N
dfs(-1,v-1,0)
aoki = deepcopy(dist_list)
print(takahasi)
print(aoki)



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

N, u, v = map(int, input().split())
u, v = u-1, v-1
edge = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    edge[a].append(b)
    edge[b].append(a)

taka = [0] * N
aoki = [0] * N

def dfs(v, pre, cost, i):
    for e in edge[v]:
        if e == pre:
            continue
        cost = dfs(e, v, cost, i+1)
    cost[v] = i
    return cost

taka = dfs(u, -1, [0] * N, 0)
aoki = dfs(v, -1, [0] * N, 0)

m = 0
for i in range(N):
    if taka[i] < aoki[i]:
        m = max(m, aoki[i])

print(m-1)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7
mask = 1
ret = 0
for i in range(70):
    on = 0
    off = 0
    for a in A:
        if a & mask:
            on += 1
        else:
            off += 1
    ret += (on * off) * mask
    ret %= MOD
    mask *= 2

print(ret)
    


Fixed submission:
N = int(input())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7
mask = 1
ret = 0
for i in range(70):
    on = 0
    off = 0
    for a in A:
        if a & mask:
            on += 1
        else:
            off += 1
    ret += (on * off) * mask
    ret %= MOD
    mask *= 2

print(ret)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()
s = list(S)
ret = set()
from itertools import combinations
for i in combinations(s, 3):
    ret.add(i)
print(len(ret))


Fixed submission:
import bisect
N = int(input())
S = input()

str_dict = {}
for s in S:
    str_dict[s] = []

for i, s in enumerate(S):
    bisect.insort_right(str_dict[s], i)
cnt = 0
for i in range(10):
    for j in range(10):
        for t in range(10):
            test_str = str(i) + str(j) + str(t)
            now_idx = -1
            flg = True
            for k in test_str:
                if not k in str_dict.keys():
                    flg = False
                    break
                try:
                    tmp = str_dict[k][bisect.bisect_left(str_dict[k], now_idx+1)]
                    if tmp != now_idx:
                        now_idx = tmp
                    else:
                        flg = False
                        break
                except:
                    flg = False
                    break
            if flg:
                cnt += 1

print(cnt)
Buggy python submission (verdict: Runtime Error):
N, T = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
dp = [[0] * (T+1) for _ in range(N+1)]
AB.sort(key = lambda x:x[0], reverse=True)
AB[0][0] = 0
for i in range(1,N+1):
    for j in range(1,T+1):
        if j < AB[i-1][0]:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j-AB[i-1][0]] + AB[i-1][1], dp[i-1][j])
print(dp[N][T])


Fixed submission:
r = int(input())
print(r**2)
Buggy python submission (verdict: Runtime Error):
from copy import deepcopy
s = list(input())
K = int(input())
dummy = "A"
S = deepcopy(s)
if len(set(S)) == 1:
    print(len(S)*K//2)
else:
    replace_cnt = 0
    for i in range(1, len(S)):
        if S[i] == S[i-1]:
            S[i] = dummy
            replace_cnt += 1
    if S[0] != S[-1]:
        print(replace_cnt*K)
    else:
        S = deepcopy(s)
        replace_cnt_two = 0
        l = len(S)
        for i in range(1, l*2):
            if S[i%l] == S[(i-1)%l]:
                S[i] = dummy
                replace_cnt_two += 1
        diff = replace_cnt_two - replace_cnt
        print(diff*(K-1)+replace_cnt)


Fixed submission:
from copy import deepcopy
s = list(input())
K = int(input())
dummy = "A"
S = deepcopy(s)
if len(set(S)) == 1:
    print(len(S)*K//2)
else:
    replace_cnt = 0
    for i in range(1, len(S)):
        if S[i] == S[i-1]:
            S[i] = dummy
            replace_cnt += 1
    if S[0] != S[-1]:
        print(replace_cnt*K)
    else:
        S = s+s
        replace_cnt_two = 0
        for i in range(1, len(S)):
            if S[i] == S[i-1]:
                S[i] = dummy
                replace_cnt_two += 1
        diff = replace_cnt_two - replace_cnt
        print(diff*(K-1)+replace_cnt)
Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappush, heappop
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort(reverse=True)
hp = []
ret = 0
for i in range(1, M+1):
    # push
    while len(AB) > 0 and AB[len(AB)-1][0] <= i:
        # heappush(hp, AB.pop()[1]*-1)
        hp.append(AB.pop()[1])
    # pop
    if len(hp) > 0:
        hp.sort()
        ret += hp.pop()
        # ret += heappop(hp)*-1

print(ret)


Fixed submission:
from heapq import heappush, heappop
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort(reverse=True)
hp = []
ret = 0
for i in range(1, M+1):
    # push
    while len(AB) > 0 and AB[len(AB)-1][0] <= i:
        heappush(hp, AB.pop()[1]*-1)
    # pop
    if len(hp) > 0:
        ret += heappop(hp)*-1

print(ret)

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
AB = {}
for i in range(N):
    a, b = map(int, input().split())
    if a in AB.keys():
        AB[a].append(b)
    else:
        AB[a] = [b]
dp = [0] * (M+1)
for i in range(1, M+1):
    tmp = 0
    km = -1
    tm = -1
    for k in range(i+1):
        if k not in AB.keys():
            continue
        for t in range(len(AB[k])):
            if tmp < AB[k][t]:
                tmp = AB[k][t]
                km = k
                tm = t
    if km >= 0:
        dp[i] = dp[i-1] + tmp
        AB[km][tm] = 0
    else:
        dp[i] = dp[i-1]

print(dp[len(dp)-1])


Fixed submission:
from heapq import heappush, heappop
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort(reverse=True)
hp = []
ret = 0
for i in range(1, M+1):
    # push
    while len(AB) > 0 and AB[len(AB)-1][0] <= i:
        heappush(hp, AB.pop()[1]*-1)
    # pop
    if len(hp) > 0:
        ret += heappop(hp)*-1

print(ret)

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort()
dp = [0] * (M+1)
for i in range(1, M+1):
    tmp = 0
    idx = -1
    for idxab, ab in enumerate(AB):
        if ab[0] <= i:
            if tmp < ab[1]:
                idx = idxab
                tmp = ab[1]
        else:
            break
    if idx >= 0:
        AB[idx][1] = 0
    dp[i] = dp[i-1] + tmp

print(dp[len(dp)-1])

Fixed submission:
from heapq import heappush, heappop
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort(reverse=True)
hp = []
ret = 0
for i in range(1, M+1):
    # push
    while len(AB) > 0 and AB[len(AB)-1][0] <= i:
        heappush(hp, AB.pop()[1]*-1)
    # pop
    if len(hp) > 0:
        ret += heappop(hp)*-1

print(ret)
Buggy python submission (verdict: Runtime Error):
S = input()
L = len(S)

MOD = 10 ** 9 + 7
dp = [[0] * 13 for _ in range(15)]
dp[0][0] = 1
for i in range(L):
    j = -1 if S[i] == "?" else int(S[i])
    if j > -1:
        # jが確定しているので、jを全探索する必要はなく、前回桁までの組み合わせの数にjを足して次のDPへ入れる
        # jが確定しているから数字の組み合わせ自体が増えるわけではない
        # そのためこれまで確定していた桁に対して、jを追加した場合のあまりを単純に移送することになる
        
        # 前回桁までの数 * 10 + j をすると、今回桁をjにしたときのあまりがわかる
        # 3?1 → 301 % 13 = 2, 30 % 13 = 4であるから、ki=4のとき、dp[i][4]の数値をdp[i+1][2]に足す
        # 30と4はmod13の世界では合同になっている
        # すなわち*10した結果である300と40も合同
        # そこにjを足した数 300+jと40+jもまた合同であると言える、ともにあまりは2
        # ここでは具体的な値である30は計算していないが、その具体的な数と合同である数字を用いて、今回桁で作成可能な数字のmodを数えているdp[i+1][2]にdp[i][4]を突っ込むことになる
        # modの世界では両辺に同じ数をかけても合同であるという性質を用いて、10をかけながら、桁ごとに数値を足していっていることになる

        for ki in range(13):
            dp[i+1][(ki * 10 + j) % 13] += dp[i][ki]
    else:
        # jが確定していないので、jになりうる値を全て試す
        # 0-9の10パターンの数字が考えられるので、全ての組み合わせ自体は*10になる
        # ? だと10パターン ??だと100パターンになるので、?が来ると、数字の組み合わせが10倍になるのは自明
        # 10**(?の数) の組み合わせの総数になる
        for j in range(10):
            for ki in range(13):
                dp[i+1][(ki * 10 + j) % 13] += dp[i][ki]
    
    for j in range(13):
        dp[i+1][j] %= MOD

print(dp[L][5])


Fixed submission:
S = input()
L = len(S)

MOD = 10 ** 9 + 7
dp = [[0] * 13 for _ in range(10**5+10)]
dp[0][0] = 1
for i in range(L):
    j = -1 if S[i] == "?" else int(S[i])
    if j > -1:
        # jが確定しているので、jを全探索する必要はなく、前回桁までの組み合わせの数にjを足して次のDPへ入れる
        # jが確定しているから数字の組み合わせ自体が増えるわけではない
        # そのためこれまで確定していた桁に対して、jを追加した場合のあまりを単純に移送することになる
        
        # 前回桁までの数 * 10 + j をすると、今回桁をjにしたときのあまりがわかる
        # 3?1 → 301 % 13 = 2, 30 % 13 = 4であるから、ki=4のとき、dp[i][4]の数値をdp[i+1][2]に足す
        # 30と4はmod13の世界では合同になっている
        # すなわち*10した結果である300と40も合同
        # そこにjを足した数 300+jと40+jもまた合同であると言える、ともにあまりは2
        # ここでは具体的な値である30は計算していないが、その具体的な数と合同である数字を用いて、今回桁で作成可能な数字のmodを数えているdp[i+1][2]にdp[i][4]を突っ込むことになる
        # modの世界では両辺に同じ数をかけても合同であるという性質を用いて、10をかけながら、桁ごとに数値を足していっていることになる

        for ki in range(13):
            dp[i+1][(ki * 10 + j) % 13] += dp[i][ki]
    else:
        # jが確定していないので、jになりうる値を全て試す
        # 0-9の10パターンの数字が考えられるので、全ての組み合わせ自体は*10になる
        # ? だと10パターン ??だと100パターンになるので、?が来ると、数字の組み合わせが10倍になるのは自明
        # 10**(?の数) の組み合わせの総数になる
        for j in range(10):
            for ki in range(13):
                dp[i+1][(ki * 10 + j) % 13] += dp[i][ki]
    
    for j in range(13):
        dp[i+1][j] %= MOD

print(dp[L][5])
Buggy python submission (verdict: Runtime Error):
import math
S = int(input())
m = 10 ** 9
y = S // m
x = S % y
print("{} 0 {} 0 0 {}".format(m, x, y))

Fixed submission:
S = int(input())
m = 10 ** 9
x = (m-S%m)%m
y = (S+x)//m
print("0 0 {} 1 {} {}".format(m, x, y))
Buggy python submission (verdict: Runtime Error):
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
ret = 'No'
c = Counter(A)
if all([i == 0 for i in c]):
    ret = 'Yes'
else:
    v = set(list([i[1] for i in c.items()]))
    if len(c) == 3 all([i == N/3 for i in v]):
        ret = 'Yes'
    elif len(c) == 2 and 0 in c:
        for i in c.items():
            if i[0] == 0 and i[1] == N/3:
                ret = 'Yes'

print(ret)

Fixed submission:
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
ret = 'No'
c = Counter(A)
if all([i == 0 for i in c]):
    ret = 'Yes'
else:
    v = set(list([i[1] for i in c.items()]))
    if len(c) == 3 and all([i == N/3 for i in v]):
        c = list(c)
        if c[0] ^ c[1] == c[2]:
            ret = 'Yes'
    elif len(c) == 2 and 0 in c:
        for i in c.items():
            if i[0] == 0 and i[1] == N/3:
                ret = 'Yes'

print(ret)
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10 ** 9 + 7

c = [[0 for i in range(4005)] for j in range(4005)]
c[0][0] = 1
for i in range(4001):
    for j in range(i+1):
        c[i+1][j] += c[i][j]
        c[i+1][j+1] += c[i][j]

def comb(n, k):
    return c[n][k]

def f2(n, k):
    return comb(n+k-1, k-1)

def f(n, k):
    if n == k: return 1
    if n < k: return 0
    if k < 1: return 0
    return f2(n-k, k)

n, k = map(int, input().split())
for i in range(1, k+1):
    blue = f(k, i)
    # 赤が両端含まない
    red = f(n-k, i-1)
    # 赤が右側含む
    red += f(n-k,i)
    # 赤が左側含む
    red += f(n-k,i)
    # 赤が両端含む1
    red += f(n-k,i+1)
    print(blue*red%MOD)




Fixed submission:
N, K = map(int, input().split())
MOD = 10 ** 9 + 7

MAX = 4000
fact = [0] * MAX
invfact = [0] * MAX
fact[0] = 1
for i in range(1, MAX):
    fact[i] = fact[i - 1] * i % MOD
invfact[MAX - 1] = pow(fact[MAX - 1], MOD-2, MOD)
for i in range(MAX - 2, -1, -1):
    invfact[i] = invfact[i+1] * (i+1) % MOD

def nCk(n, k):
    if k < 0 or n < k: return 0
    return (fact[n] * invfact[k] % MOD) * invfact[n-k] % MOD

ans = 0
red = N - K
for i in range(1,1+K):
    ans = nCk(red+1, i) * nCk(K-1, i-1)
    ans %= MOD
    print(ans)

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

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

n, k = map(int, input().split())
for i in range(1, k+1):
    red = cmb(k-1, i-1)
    blue = cmb(n-k+1, i)
    print(red*blue%(10**9+7))


Fixed submission:
N, K = map(int, input().split())
MOD = 10 ** 9 + 7

MAX = 4000
fact = [0] * MAX
invfact = [0] * MAX
fact[0] = 1
for i in range(1, MAX):
    fact[i] = fact[i - 1] * i % MOD
invfact[MAX - 1] = pow(fact[MAX - 1], MOD-2, MOD)
for i in range(MAX - 2, -1, -1):
    invfact[i] = invfact[i+1] * (i+1) % MOD

def nCk(n, k):
    if k < 0 or n < k: return 0
    return (fact[n] * invfact[k] % MOD) * invfact[n-k] % MOD

ans = 0
red = N - K
for i in range(1,1+K):
    ans = nCk(red+1, i) * nCk(K-1, i-1)
    ans %= MOD
    print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
mod =  1000000007
ret = [0] * (N+1)
ret[0] = 1
for i in range(1,N+1):
    if i in a:
        continue
    elif i == 1:
        ret[1] = 1
    else:
        ret[i] = ret[i-2] + ret[i-1]

print(ret[len(ret)-1]%mod)


Fixed submission:
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
mod =  1000000007
ret = [-1] * (N+1)
ret[0] = 1
for i in a:
    ret[i] = 0

for i in range(1,N+1):
    if ret[i] == 0:
        continue
    elif i == 1:
        ret[1] = 1
    else:
        ret[i] = ret[i-2] + ret[i-1]

print(ret[len(ret)-1]%mod)
Buggy python submission (verdict: Runtime Error):
N, X = map(int, input().split())
a, p = [1], [1]
for i in range(N):
    a.append(a[i] * 2 + 3)
    p.append(a[i] * 2 + 1)

def f(N, X):
    if N == 0:
        return 0 if X <= 0 else 1
    elif X <= 1 + a[N-1]:
        # B(N-1) | P(N-1)B の真ん中のパティの前までの範囲がわかればいい場合
        # Xから先頭のバンの数を引いて、N-1の先頭からX-1までの数を数えるために再帰で呼び出す
        return f(N-1,X-1)
    else:
        # 真ん中のパティ以上の枚数を数える必要がある場合
        # 一つ前のレベルのパティの数 + 真ん中のパティ + f(レベル-1, この関数呼び出しで知りたいトータルの枚数-2(先頭のバンと真ん中のパティ)-一つ前のレベルのハンバーガーのトータルの枚数)
        # X-2-a[N-1] → X - (B(N-1)P)|ここから後ろの先頭からK枚を数えるために再帰で呼び出す
        return p[N-1] + 1 + f(N-1, X-2-a[N-1])

print(f(N,X))


Fixed submission:
s = input()
l = len(s)
s += "0"
ans = 0
a_cnt = 0
skip = False
for i in range(l):
    if skip:
        skip = False
        continue
    if s[i] == "A":
        a_cnt += 1
    elif s[i] == "B" and s[i+1] == "C":
        ans += a_cnt
        skip = True
    else:
        a_cnt = 0

print(ans)
Buggy python submission (verdict: Runtime Error):
5
1 2
1 3
1 4
1 5
3141 59 26 53 59

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

N = int(input())
edge = [[] for _ in range(N)]
cnt = [[0,i] for i in range(N)]

for i in range(N-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    edge[a].append(b)
    edge[b].append(a)
    cnt[a][0] += 1
    cnt[b][0] += 1


cnt.sort(reverse=True)
start = cnt[0][1]
C = list(map(int, input().split()))
C.sort(reverse=True)
nodes = [0] * N

#print(nodes)
cidx = -1
ans = []
def dfs(v, pv, w):
    global cidx
    cidx += 1
    nodes[v] = C[cidx]
    ans.append(min(w, C[cidx]))
    for nv in edge[v]:
        if pv == nv: continue
        dfs(nv, v, C[cidx])

dfs(start, 0, 0)
print(sum(ans))
print(*nodes, sep=" ")

Buggy python submission (verdict: Runtime Error):
N = int(input())
edge = [[] for _ in range(N)]
cnt = [[0,i] for i in range(N)]

for i in range(N-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    edge[a].append(b)
    edge[b].append(a)
    cnt[a][0] += 1
    cnt[b][0] += 1

cnt.sort()
C = list(map(int, input().split()))
C.sort()
nodes = [0] * N
for idx, (c, i) in enumerate(cnt):
    nodes[i] = C[idx]

#print(nodes)

ans = []

def dfs(v, pv, w):
    ans.append(min(w, nodes[v]))
    for nv in edge[v]:
        if pv == nv: continue
        dfs(nv, v, nodes[v])

dfs(0, 0, 0)
print(sum(ans))
print(*nodes, sep=" ")


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

N = int(input())
edge = [[] for _ in range(N)]
cnt = [[0,i] for i in range(N)]

for i in range(N-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    edge[a].append(b)
    edge[b].append(a)
    cnt[a][0] += 1
    cnt[b][0] += 1


cnt.sort(reverse=True)
start = cnt[0][1]
C = list(map(int, input().split()))
C.sort(reverse=True)
nodes = [0] * N

#print(nodes)
cidx = -1
ans = []
def dfs(v, pv, w):
    global cidx
    cidx += 1
    nodes[v] = C[cidx]
    ans.append(min(w, C[cidx]))
    for nv in edge[v]:
        if pv == nv: continue
        dfs(nv, v, C[cidx])

dfs(start, 0, 0)
print(sum(ans))
print(*nodes, sep=" ")