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

Fixed submission:
import sys
input = sys.stdin.readline
N, M = [int(x) for x in input().split()]
A = []
for _ in range(N):
    A.append(list(input().rstrip()))
B = []
for _ in range(M):
    B.append(list(input().rstrip()))
n = len(A[0])
m = len(B[0])
def search(point):
    x, y = point
    for i in range(M):
        if y > N - 1:
            return 0
        a = A[y][x:x + m]
        if a != B[i]:
            return 0
        y += 1
    return 1
for i in range(N):
    for j in range(n):
        if search([i, j]):
            print("Yes")
            sys.exit()
print("No")

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
N, M = [int(x) for x in input().split()]
A = []
for _ in range(N):
    A.append(list(input().rstrip()))
B = []
for _ in range(M):
    B.append(list(input().rstrip()))
m = len(B[0])
def search(point):
    x, y = point
    for i in range(M):
        if y > N:
            return 0
        a = A[y][x:x + m]
        if a != B[i]:
            return 0
        y += 1
    return 1
for i in range(N):
    for j in range(len(A[0])):
        if search([i, j]):
            print("Yes")
            sys.exit()
print("No")
Problem p03834 (python)

Fixed submission:
import sys
input = sys.stdin.readline
s = input().rstrip().split(",")
print(*s)

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
s = input().split(,)
print(*s)
Problem p02785 (python)

Fixed submission:
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
S = 0
for i in range(0, K):
    if len(A) > 0:
        A.pop(-1)
print(sum(A))

Buggy submission (verdict: Runtime Error):
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
S = 0
for i in range(0, K):
  if not A.empty():
    A.pop_back()
print(sum(A))
Problem p02689 (python)

Fixed submission:
def main():
    n, m = map(int,input().split())
    hlis = list(map(int, input().split()))
    hdic = {}
    rdic = {}
    for i in range(1, len(hlis)+1):
        hdic[i] = hlis[i-1]
    for j in range(m):
        a, b = map(int, input().split())
        if a in rdic:
            if rdic[a] < hdic[b]:
                rdic[a] = hdic[b]
        else:
            rdic[a] = hdic[b]
        if b in rdic:
            if rdic[b] < hdic[a]:
                rdic[b] = hdic[a]
        else:
            rdic[b] = hdic[a]
    ans = 0
    #print(hdic, rdic)
    for key in hdic:
        if key in rdic:
            if hdic[key] > rdic[key]:
                ans += 1
                #print(key)
        else:
            ans += 1
            #print(key)
    print(ans)



    
    
if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
def main()
    import itertools
    n, m = map(int, input().split())
    h_lis = list(map(int, input().split()))

    cnt = 0
    ans = 0
    tmp = 0

    ab_lis = []
    for _ in range(m):
        ab_lis.append(list(map(int, input().split())))
    h_dic = {}

    ab_total = list(itertools.chain.from_iterable(ab_lis))
    #print(len(set(ab_total)))
    ans = n - len(set(ab_total))

    for i in range(n):
        h_dic[i+1] = h_lis[i]
    print(h_dic)

    for mountain in h_dic:
        tmp = 0
        for ab in ab_lis:
            print(mountain, h_dic[mountain], ab, ans, tmp)
            if mountain == ab[0]:
                if h_dic[mountain] < h_dic[ab[1]]:
                    tmp += 1
                    print(mountain, h_dic[mountain], ab, ans, tmp)
            elif mountain == ab[1]:
                if h_dic[mountain] < h_dic[ab[0]]:
                    tmp+=1
                    print(mountain, h_dic[mountain], ab, ans, tmp)
        if tmp == 0:
            ans += 1

    print(ans)

if __name__ == "__main__":
    main()
Problem p03011 (python)

Fixed submission:
p, q, r = map(int, input().split())
print(p + q+ r - max(p, q, r))

Buggy submission (verdict: Runtime Error):
a, b, c= map(int, input().split())
print( sum(a, b, c) - max(a, b, c))
Problem p03041 (python)

Fixed submission:
def main():
    n, k = map(int, input().split())
    s = input()
    
    print(s[:k-1] + s[k-1].lower() + s[k:])

if __name__ == "__main__":
    main()

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

s[k-1] = s[k-1].lower()
print(s)
Problem p03803 (python)

Fixed submission:
a, b = map(int, input().split())
if a == b:
  print('Draw')
elif a > b and b!=1:
  print('Alice')
elif a==1:
  print('Alice')
else:
  print('Bob')

Buggy submission (verdict: Runtime Error):
a, b = map(int, input())
if a == b:
  print('Draw')
elif a > b and b!=1:
  print('Alice')
else:
  print('Bob')
Problem p02598 (python)

Fixed submission:
N, K = map(int, input().split())
A = list(map(int, input().split()))

# にぶたん: 答えをx以下にできるか？
ok, ng = 10 ** 9 + 1, 0
while abs(ok - ng) > 1:
    x = (ok + ng) // 2
    cnt = 0

    for a in A:
        if a <= x:
            continue

        cnt += a // x
        if cnt > K:
            ng = x
            break
    else:
        ok = x

print(ok)

Buggy submission (verdict: Runtime Error):
from math import ceil
N, K = map(int, input().split())
A = list(map(int, input().split()))

# にぶたん: 答えをx以下にできるか？
ok, ng = 10 ** 9 + 1, -1
while abs(ok - ng) > 1:
    x = (ok + ng) // 2
    cnt = 0

    for a in A:
        if a <= x:
            continue

        cnt += a // x
        if cnt > K:
            ng = x
            break
    else:
        ok = x

print(ok)
Problem p02762 (python)

Fixed submission:
def main():
    import sys
    from collections import defaultdict
    N, M, K = map(int, sys.stdin.readline().split())

    F = [set() for _ in range(N)]
    B = [set() for _ in range(N)]
    for m in range(M):
        a, b = map(int, sys.stdin.readline().split())
        a, b = a - 1, b - 1
        F[a].add(b)
        F[b].add(a)

    for k in range(K):
        c, d = map(int, sys.stdin.readline().split())
        c, d = c - 1, d - 1
        B[c].add(d)
        B[d].add(c)

    D = defaultdict(set)
    parents = [-1] * N
    visited = set()
    for s in range(N):
        if s in visited:
            continue

        stack = [s]
        D[s].add(s)
        while stack:
            n = stack.pop()
            visited.add(n)
            parents[n] = s
            for to in F[n]:
                if to in visited:
                    continue
                D[s].add(to)
                stack.append(to)

    ans = [0] * N
    for i in range(N):
        X = D[parents[i]]
        tmp_ans = 0
        tmp_ans += len(X)
        tmp_ans -= len(F[i])
        tmp_ans -= 1
        for b in B[i]:
            if b in X:
                tmp_ans -= 1
        ans[i] = tmp_ans

    print(*ans, sep=' ')


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def main():
    import sys
    from collections import defaultdict
    N, M, K = map(int, sys.stdin.readline().split())

    F = [set() for _ in range(N)]
    B = [set() for _ in range(N)]
    for m in range(M):
        a, b = map(int, sys.stdin.readline().split())
        a, b = a - 1, b - 1
        F[a].add(b)
        F[b].add(a)

    for k in range(K):
        c, d = map(int, sys.stdin.readline().split())
        c, d = c - 1, d - 1
        B[c].add(d)
        B[d].add(c)

    D = defaultdict(set)
    parents = [-1] * N
    visited = set()
    for s in range(N):
        if s in visited:
            continue

        stack = [s]
        D[s].add(s)
        while stack:
            n = stack.pop()
            visited.add(n)
            parents[n] = s
            for to in F[n]:
                if to in visited:
                    continue
                D[s].add(to)
                stack.append(to)

    print(1 / 0)
    ans = [0] * N
    #print(D)
    for i in range(N):
        #print(D[parents[i]] - F[i] - B[i] - {i}, F[i], B[i])
        ans[i] = len(D[parents[i]] - F[i] - B[i] - {i})

    print(*ans, sep=' ')


if __name__ == '__main__':
    main()
Problem p02763 (python)

Fixed submission:
from bisect import bisect_left, bisect_right
N = int(input())
S = list(input())
Q = int(input())

D = {chr(ord('a') + i): [] for i in range(26)}

for i, s in enumerate(S):
    D[s].append(i)

for q in range(Q):
    query = list(input().split())
    if query[0] == '1':
        i, x = int(query[1]), query[2]
        i -= 1
        s = S[i]
        if s == x:
            continue

        D[s].remove(i)
        next_i = bisect_left(D[x], i)
        D[x].insert(next_i, i)
        S[i] = x

    if query[0] == '2':
        l, r = int(query[1]), int(query[2])
        l, r = l - 1, r - 1
        ans = 0
        for i in range(26):
            s = chr(ord('a') + i)

            li = bisect_left(D[s], l)
            ri = bisect_right(D[s], r)

            if ri - li > 0:
                ans += 1

        print(ans)

Buggy submission (verdict: Runtime Error):
from bisect import bisect_left, bisect_right
N = int(input())
S = input()
Q = int(input())

D = {chr(ord('a') + i): [] for i in range(26)}

for i, s in enumerate(S):
    D[s].append(i)

for q in range(Q):
    query = list(input().split())
    if query[0] == '1':
        i, x = int(query[1]), query[2]
        i -= 1
        s = S[i]
        if s == x:
            continue

        D[s].remove(i)
        next_i = bisect_left(D[x], i)
        D[x].insert(next_i, i)

    if query[0] == '2':
        l, r = int(query[1]), int(query[2])
        l, r = l - 1, r - 1
        ans = 0
        for i in range(26):
            s = chr(ord('a') + i)

            li = bisect_left(D[s], l)
            ri = bisect_right(D[s], r)

            if ri - li > 0:
                ans += 1

        print(ans)

Buggy submission (verdict: Runtime Error):
from bisect import bisect_left, bisect_right
N = int(input())
S = input()
Q = int(input())

D = {chr(ord('a') + i): [] for i in range(26)}
for i, s in enumerate(S):
    D[s].append(i)

for q in range(Q):
    query = list(input().split())
    if query[0] == '1':
        i, x = int(query[1]), query[2]
        i -= 1
        s = S[i]
        if s == x:
            continue

        D[s].remove(i)
        next_i = bisect_left(D[x], i)
        D[x].insert(next_i, i)

    if query[0] == '2':
        l, r = int(query[1]), int(query[2])
        l, r = l - 1, r - 1
        ans = 0
        for i in range(26):
            s = chr(ord('a') + i)

            li = bisect_left(D[s], l)
            ri = bisect_right(D[s], r)

            if ri - li > 0:
                ans += 1

        print(ans)

print(D)
Problem p02862 (python)

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


if (X + Y) % 3 != 0:
    print(0)
    exit()


X, Y = min(X, Y), max(X, Y)
ALL_MOVE = (X + Y) // 3
for m1 in range(ALL_MOVE):
    m2 = ALL_MOVE - m1

    if (m1 * 2 + m2 == X) and (m1 + m2 * 2 == Y):
        move_1_cnt = m1
        move_2_cnt = m2
        break
else:
    print(0)
    exit()


factorial = [1]
inverse = [1]
for i in range(1, ALL_MOVE + 2):
    factorial.append(factorial[-1] * i % MOD)
    inverse.append(pow(factorial[-1], MOD - 2, MOD))


# 組み合わせ計算
def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % MOD


print(nCr(ALL_MOVE, move_1_cnt) % MOD)

Buggy submission (verdict: Runtime Error):
X, Y = map(int, input().split())
MOD = 10 ** 9 + 7


if (X + Y) % 3 != 0:
    print(0)
    exit()


X, Y = min(X, Y), max(X, Y)
ALL_MOVE = (X + Y) // 3

for m1 in range(ALL_MOVE):
    m2 = ALL_MOVE - m1

    if (m1 * 2 + m2 == X) and (m1 + m2 * 2 == Y):
        move_1_cnt = m1
        move_2_cnt = m2
        break


factorial = [1]
inverse = [1]
for i in range(1, ALL_MOVE + 2):
    factorial.append(factorial[-1] * i % MOD)
    inverse.append(pow(factorial[-1], MOD - 2, MOD))


# 組み合わせ計算
def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % MOD


print(nCr(ALL_MOVE, move_1_cnt) % MOD)
Problem p02863 (python)

Fixed submission:
N, T = map(int, input().split())
T -= 1
Meals = sorted([list(map(int, input().split())) for i in range(N)])
dp = [[0] * (T + 1) for i in range(N + 1)]
prev = [[-1] * (T + 1) for i in range(N + 1)]


for i, (cost, value) in enumerate(Meals):
    for j in range(T + 1):
        if j >= cost:
            if dp[i + 1][j] <= dp[i][j - cost] + value:
                dp[i + 1][j] = dp[i][j - cost] + value
                prev[i + 1][j] = j - cost

        if dp[i + 1][j] <= dp[i][j]:
            dp[i + 1][j] = dp[i][j]
            prev[i + 1][j] = j

# 復元
selected = set()
cur_w = T
for i in range(N - 1, -1, -1):
    if prev[i + 1][cur_w] == cur_w - Meals[i][0]:
        selected.add(i)
    cur_w = prev[i + 1][cur_w]

non_selected = set(list(range(N))) - selected
ans = dp[N][T]
add = 0
for ni in non_selected:
    add = max(add, Meals[ni][1])

print(dp[N][T] + add)

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

# dp1[i][j] := 商品0 ~ i が対象
dp = [[0] * (W + 1) for i in range(N + 1)]

# dpテーブルを埋める
for i in range(N):
    wi, vi = items[i]
    for j in range(W + 1):
        if j + wi <= W:
            dp[i + 1][j + wi] = max(dp[i + 1][j + wi], dp[i][j] + vi)
        dp[i + 1][j] = max(dp[i][j], dp[i + 1][j])


ans = 0
for i, (wi, vi) in enumerate(items):
    for j in range(W):
        ans = max(ans, dp[i] + vi)

print(ans)
Problem p02990 (python)

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

R = N - K + 1
# 階乗 & 逆元計算
factorial = [1]
inverse = [1]
for i in range(1, 2000 + 2):
    factorial.append(factorial[-1] * i % MOD)
    inverse.append(pow(factorial[-1], MOD - 2, MOD))


# 組み合わせ計算
def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % MOD


for i in range(1, K + 1):
    if i != K:
        print(nCr(R, i) * nCr(K - 1, i - 1) % MOD)
    if i == K:
        print(nCr(R, i) % MOD)

Buggy submission (verdict: Runtime Error):
N, K = map(int, input().split())
MOD = 10 ** 9 + 7

R = N - K + 1
# 階乗 & 逆元計算
factorial = [1]
inverse = [1]
for i in range(1, R + 2):
    factorial.append(factorial[-1] * i % MOD)
    inverse.append(pow(factorial[-1], MOD - 2, MOD))


# 重複組み合わせ
def nHk(n, k):
    value = 1
    nk = n + k - 1
    k = min(nk - k, k)
    for i in range(k):
        value = (value * nk) % MOD
        nk -= 1
    for x in range(1, k + 1):
        value = (value * pow(x, MOD - 2, MOD)) % MOD
    return value


# 組み合わせ計算
def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % MOD


for i in range(1, K + 1):
    if i != K:
        print(nCr(R, i) * nCr(K - 1, i - 1) % MOD)
    if i == K:
        print(nCr(R, i) % MOD)

Buggy submission (verdict: Runtime Error):
N, K = map(int, input().split())
MOD = 10 ** 9 + 7

R = N - K + 1
# 階乗 & 逆元計算
factorial = [1]
inverse = [1]
for i in range(1, R + 2):
    factorial.append(factorial[-1] * i % MOD)
    inverse.append(pow(factorial[-1], MOD - 2, MOD))


# 重複組み合わせ
def nHk(n, k):
    value = 1
    nk = n + k - 1
    k = min(nk - k, k)
    for i in range(k):
        value = (value * nk) % MOD
        nk -= 1
    for x in range(1, k + 1):
        value = (value * pow(x, MOD - 2, MOD)) % MOD
    return value


# 組み合わせ計算
def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % MOD


for i in range(1, K + 1):
    if i != K:
        print(nCr(R, i) * factorial[i] % MOD)
    if i == K:
        print(nCr(R, i) % MOD)
Problem p03017 (python)

Fixed submission:
N, A, B, C, D = map(int, input().split())
S = input()

A, B, C, D = A - 1, B - 1, C - 1, D - 1
if (A < C < B < D) or (A < B < C < D):
    if '##' in S[A: C + 1]:
        print('No')
        exit()

    if '##' in S[B: D + 1]:
        print('No')
        exit()
    print('Yes')


if A < B < D < C:
    if '##' in S[A: C + 1]:
        print('No')
        exit()

    if '##' in S[B: D + 1]:
        print('No')
        exit()

    if '...' in S[B - 1: D + 2]:
        print('Yes')
    else:
        print('No')

Buggy submission (verdict: Runtime Error):
N, A, B, C, D = map(int, input().split())
S = input()

A, B, C, D = A - 1, B - 1, C - 1, D - 1
if (A < C < B < D) or (A < B < C < D):
    for i in range(A, C + 1):
        if S[i] == '#' and S[i + 1] == '#':
            print('No')
            exit()
    for i in range(B, D + 1):
        if S[i] == '#' and S[i + 1] == '#':
            print('No')
            exit()
    print('Yes')
    exit()

if A < B < D < C:
    for i in range(A, C + 1):
        if S[i] == '#' and S[i + 1] == '#':
            print('No')
            exit()

    for i in range(B, D + 1):
        if S[i] == '#' and S[i + 1] == '#':
            print('No')
            exit()

    for i in range(B + 1, D + 1):
        if S[i] == '.' and S[i + 1] == '.' and S[i + 2] == '.':
            print('Yes')
            exit()
    print('No')
Problem p03033 (python)

Fixed submission:
def main():

    import sys
    import heapq

    N, Q = map(int, sys.stdin.readline().split())
    events = []

    for i in range(N):
        s, t, x = map(int, sys.stdin.readline().split())
        events.append((s - x, 1, x))  # 通行止め追加
        events.append((t - x, -1, x))  # 通行止め削除

    for i in range(Q):
        d = int(input())
        events.append((d, 2, 0))

    events.sort()
    events.append([float('inf'), 'guard', None])

    i = 0
    closing = set()
    hq = []  # 最小値を高速に入手するため
    while d >= events[i][0]:
        time, event, x = events[i]
        if event == 1:
            closing.add(x)
            heapq.heappush(hq, x)

        elif event == -1:
            closing.remove(x)

        else:
            while hq and (hq[0] not in closing):
                heapq.heappop(hq)

            if hq:
                print(hq[0])
            else:
                print(-1)

        i += 1


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
N, Q = map(int, input().split())
works = []
for i in range(N):
    s, t, x = map(int, input().split())
    if x < s:
        works.append([s - x, t - x - 1, x])

    elif s <= x <= t:
        works.append([0, t - x - 1, x])

    else:
        continue


works.sort(key=lambda w: w[1])
works.append([float('inf'), float('inf'), -1])
i = 0

for q in range(Q):
    d = int(input())
    while i < N:
        s, t, x = works[i]
        if s <= d <= t:
            print(x)
            break

        i += 1
        if d < works[i][0]:
            print(-1)
            break
Problem p03201 (python)

Fixed submission:
from collections import Counter

N = int(input())
A = sorted(list(map(int, input().split())), reverse=True)
C = Counter(A)
keys = set(A)

ans = 0
for a in A:
    target_2_pow = 2 ** a.bit_length()
    b = target_2_pow - a
    if b not in keys:
        continue

    if a != b:
        if C[a] == 0 or C[b] == 0:
            continue
    else:
        if C[b] < 2:
            continue
    ans += 1
    C[a] -= 1
    C[b] -= 1

print(ans)

Buggy submission (verdict: Runtime Error):
from collections import Counter
from bisect import bisect_left

N = int(input())
A = sorted(list(map(int, input().split())), reverse=True)

ans = 0
C = []
for x, num in dict(Counter(A)).items():
    C.append([x, num])
C.sort()

for i in range(N):
    for t in range(33, 0, -1):
        target = 2 ** t - A[i]
        if target < 0:
            continue
        target_t = bisect_left(C, [target, 0])

        if target_t >= N:
            continue

        x, num = C[target_t]
        if x == target and num > 0 and i != target_t:
            ans += 1
            C[i][1] -= 1
            C[target_t][1] -= 1
            break

print(ans)
Problem p03209 (python)

Fixed submission:
N, X = map(int, input().split())

a = [1]  # レベルiバーガーの長さ
p = [1]  # レベルiバーガーに含まれるパティの数
for i in range(N):
    a.append(2 * a[-1] + 3)
    p.append(2 * p[-1] + 1)


def f(N, X):
    if N == 0:
        return 0 if X <= 0 else 1

    elif X <= 1 + a[N - 1]:
        return f(N - 1, X - 1)

    else:
        return p[N - 1] + 1 + f(N - 1, X - 2 - a[N - 1])


print(f(N, X))

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

# レベルLバーガーの厚さ, レベルLバーガーに含まれるパティの数
thick, patti = [1], [1]
for i in range(N):
    thick.append(2 * thick[-1] + 3)
    patti.append(2 * patti[-1] + 1)


def solve(n, x):
    if x == 1:  # 一番下のバン(ただしレベル0バーガー参照時には+1)
        return 0 + (n == 0)

    # 一番下のバン + レベルL-1バーガーの途中まで
    elif 1 < x <= 1 + thick[n - 1]:
        return solve(n - 1, x - 1)

    # 一番下のバン + レベルL-1バーガー + 真ん中のパティ + レベルL-1バーガーの途中まで + (どうでもいい最後のバン)
    else:
        return patti[n - 1] + 1 + solve(n - 1, x - 1 - thick[n - 1] - 1)


print(solve(N, X))
Problem p03329 (python)

Fixed submission:
N = int(input())
dp = [float('inf')] * (10**5+1)
dp[0] = 0

for i in range(1, N+1):
    dp[i] = min(dp[i-1], dp[i-6], dp[i-6**2], dp[i-6**3], dp[i-6**4], dp[i-6**5], dp[i-6**6],
                dp[i-9], dp[i-9**2], dp[i-9**3], dp[i-9**4], dp[i-9**5]) + 1

print(dp[N])

Buggy submission (verdict: Runtime Error):
N = int(input())
dp = [float('inf')] * (2*10**5+1)
dp[0] = 0

for i in range(1, N+1):
    dp[i] = min(dp[i-1], dp[i-6], dp[i-6**2], dp[i-6**3], dp[i-6**4], dp[i-6**5], dp[i-6**7],
                dp[i-9], dp[i-9**2], dp[i-9**3], dp[i-9**4], dp[i-9**5]) + 1

print(dp[N])

Buggy submission (verdict: Runtime Error):
N = int(input())
dp = [float('inf')] * (10**5+1)
dp[0] = 0

for i in range(1, N+1):
    dp[i] = min(dp[i-1], dp[i-6], dp[i-6**2], dp[i-6**3], dp[i-6**4], dp[i-6**5], dp[i-6**7],
                dp[i-9], dp[i-9**2], dp[i-9**3], dp[i-9**4], dp[i-9**5]) + 1

print(dp[N])
Problem p03332 (python)

Fixed submission:
N, A, B, K = map(int, input().split())
mod = 998244353

# 階乗 & 逆元計算
factorial = [1]
inverse = [1]
for i in range(1, N+2):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod-2, mod))


# 組み合わせ計算
def nCr(n, r):
    if n < r:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % mod


ans = 0
for r in range(N+1):
    b = (K - A*r) / B
    # 青で塗る箇所が整数ならば
    if b == (K-A*r) // B and 0 <= b <= N:
        ans += nCr(N, r) * nCr(N, int(b)) % mod

print(ans % mod)

Buggy submission (verdict: Runtime Error):
N, A, B, K = map(int, input().split())
mod = 998244353

# 階乗 & 逆元計算
factorial = [1]
inverse = [1]
for i in range(1, N+2):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod-2, mod))


# 組み合わせ計算
def nCr(n, r):
    if n < r:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % mod


ans = 0
for r in range(N+1):
    b = (K - A*r) / B
    # 青で塗る箇所が整数ならば
    if b == (K-A*r) // B:
        ans += nCr(N, r) * nCr(N, int(b)) % mod

print(ans % mod)

Buggy submission (verdict: Runtime Error):
N, A, B, K = map(int, input().split())
mod = 998244353

# 階乗 & 逆元計算
factorial = [1]
inverse = [1]
for i in range(1, N+2):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod-2, mod))


# 組み合わせ計算
def nCr(n, r):
    if n < r or n == 0 or r == 0:
        return 0
    return factorial[n] * inverse[r] * inverse[n - r] % mod


ans = 0
for r in range(N+1):
    b = (K - A*r) / B
    # 青で塗る箇所が整数ならば
    if b == (K-A*r) // B and b <= N:
        ans += nCr(N, r) * nCr(N, int(b)) % mod

print(ans)

Buggy submission (verdict: Runtime Error):
N, A, B, K = map(int, input().split())
mod = 998244353

# 階乗 & 逆元計算
factorial = [1]
inverse = [1]
for i in range(1, N+2):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod-2, mod))


# 組み合わせ計算
def nCr(n, r):
    if n < r or n == 0 or r == 0:
        return 0
    return factorial[n] * inverse[r] * inverse[n - r] % mod


ans = 0
for r in range(N+1):
    b = (K - A*r) / B
    # 青で塗る箇所が整数ならば
    if b == (K-A*r) // B:
        ans += nCr(N, r) * nCr(N, int(b)) % mod

print(ans)