Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import math

n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [math.inf] * n
dp[0] = 0
for i in range(1, n):
    for j in range(max(0, i - k), i):
        dp[i] = min(dp[i], dp[j] + abs(h[i] - h[j]))
print(dp[n - 1])


Fixed submission:
import math

n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [math.inf] * n
dp[0] = 0
for i in range(1, n):
    dp[i] = min(dp[j] + abs(h[i] - h[j]) for j in range(max(0, i - k), i))
print(dp[n - 1])

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

n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [math.inf] * n
dp[0] = 0
for i in range(1, n):
    for j in range(max(0, i - k), k):
        dp[i] = min(dp[i], dp[j] + abs(h[i] - h[j]))
print(dp[n - 1])


Fixed submission:
import math

n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [math.inf] * n
dp[0] = 0
for i in range(1, n):
    dp[i] = min(dp[j] + abs(h[i] - h[j]) for j in range(max(0, i - k), i))
print(dp[n - 1])

Buggy python submission (verdict: Time Limit Exceeded):
import math

n, k = map(int, input().split())
h = list(map(int, input().split())) + [0] * 100

dp = [math.inf for _ in range(n + 100)]
dp[0] = 0
for i in range(n):
    for j in range(1, k + 1):
        dp[i + j] = min(dp[i + j], dp[i] + abs(h[i] - h[i + j]))

print(dp[n - 1])


Fixed submission:
import math

n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [math.inf] * n
dp[0] = 0
for i in range(1, n):
    dp[i] = min(dp[j] + abs(h[i] - h[j]) for j in range(max(0, i - k), i))
print(dp[n - 1])
Buggy python submission (verdict: Runtime Error):
from collections import Counter
n, k = map(int, input().split())
a = list(map(int, input().split()))
a = Counter(a)
a = sorted(a.values())
print(sum[a[:len(a) - k]])



Fixed submission:
i = input()
print(int(i[0] == '1') + int(i[1] == '1') + int(i[2] == '1'))

Buggy python submission (verdict: Runtime Error):
from collections import Counter
N, K = map(int, input().split())
A = list(map(int, input().split()))
A = Counter(A)
A = sorted(A.values())
print(sum[A[:len(A) - k]])



Fixed submission:
i = input()
print(int(i[0] == '1') + int(i[1] == '1') + int(i[2] == '1'))

Buggy python submission (verdict: Runtime Error):
N = int(input())
A = [int(i) for i in input().split(',')]

is_all_even = True
counter = 0
while True:
    for i, v in enumerate(A):
        if v % 2 == 0:
            A[i] = A[i] // 2
        else:
            is_all_even = False
    if is_all_even:
        counter += 1
    else:
        break
print(counter)



Fixed submission:
i = input()
print(int(i[0] == '1') + int(i[1] == '1') + int(i[2] == '1'))

Buggy python submission (verdict: Runtime Error):

A = map(int, input().split(','))

N = int(input())
A = [int(i) for i in input().split(',')]

is_all_even = True
counter = 0
while True:
    for i in range(len(A)):
        if A[i] % 2 == 0:
            A[i] = int(A[i] // 2)
        else:
            is_all_even = False
    if is_all_even:
        counter += 1
    else:
        break
print(counter)


Fixed submission:
i = input()
print(int(i[0] == '1') + int(i[1] == '1') + int(i[2] == '1'))

Buggy python submission (verdict: Runtime Error):
N = int(input())
A = [int(i) for i in input().split(',')]

is_all_even = True
counter = 0
while True:
    for i in range(len(A)):
        if A[i] % 2 == 0:
            A[i] = int(A[i] / 2)
        else:
            is_all_even = False
    if is_all_even:
        counter += 1
    else:
        break
print(counter)


Fixed submission:
i = input()
print(int(i[0] == '1') + int(i[1] == '1') + int(i[2] == '1'))

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

is_all_odd = True
counter = 0
while True:
    for i in range(len(A)):
        if A[i] % 2 == 0:
            A[i] = int(A[i] / 2)
        else:
            is_all_odd = False
    if is_all_odd:
        counter += 1
    else:
        break
print(counter)


Fixed submission:
i = input()
print(int(i[0] == '1') + int(i[1] == '1') + int(i[2] == '1'))
Buggy python submission (verdict: Runtime Error):
"""Shift Only
【問題概要】
黒板に N 個の正の整数 A1,…,AN が書かれています。
すぬけ君は，黒板に書かれている整数がすべて偶数であるとき，次の操作を行うことができます。

黒板に書かれている整数すべてを，2 で割ったものに置き換える。
すぬけ君は最大で何回操作を行うことができるかを求めてください。

【制約】

1≤N≤2001≤N≤200
1≤Ai≤1091≤Ai≤109
【数値例】
1)
　N=3
　A=(16,12,24)
"""
N = int(input())
A = list(map(int, input().split(',')))

is_all_odd = True
counter = 0
while True:
    for i in range(N):
        if A[i] % 2 == 0:
            A[i] = A[i] / 2
        else:
            is_all_odd = False
    if is_all_odd:
        counter += 1
    else:
        break
print(counter)


Fixed submission:
N = int(input())
A = [int(i) for i in input().split()]

is_all_even = True
counter = 0
while True:
    for i, v in enumerate(A):
        if v % 2 == 0:
            A[i] = A[i] // 2
        else:
            is_all_even = False
    if is_all_even:
        counter += 1
    else:
        break
print(counter)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
A = list(map(int, input().split()))
n_count = []
for a in set(A):
    n_count.append(A.count(a))
print(sum(sorted(n_count)[:len(set(A)) - K]))


Fixed submission:
from collections import Counter
n, k = map(int, input().split())
A = list(map(int, input().split()))
a = Counter(A)
a = sorted(a.values())
print(sum(a[:len(a) - k]))
Buggy python submission (verdict: Time Limit Exceeded):
K, S = map(int, input().split())

counter = 0
for x in range(K + 1):
    for y in range(K + 1):
        for z in range(K + 1):
            if S == x + y + z:
                counter += 1
print(counter)


Fixed submission:
K, S = map(int, input().split())

counter = 0
for x in range(K + 1):
    for y in range(K + 1):
        z = S - x - y
        if 0 <= z and z <= K:
            counter += 1
print(counter)
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(1000000) # 再帰上限を増やす

def main():
    input = sys.stdin.readline  # 文字列に対してinputした場合は、rstripするのを忘れずに！
    N, W = map(int, input().rstrip().split())
    item_list = []
    for _ in range(N):
        w, v = map(int, input().rstrip().split())
        item_list.append((w, v))

    # dp[i][v] = i番目まで見て価値vを達成できる最小の重さ
    dp = [[float("inf")] * (10001) for _ in range(N+1)]
    dp[0][0] = 0

    max_value = 0
    for i, item in enumerate(item_list, 1):
        for v in range(10001):
            # もし品物iが入れられる
            if dp[i-1][v] + item[0] <= W:
                dp[i][v+item[1]] = min(dp[i][v+item[1]], dp[i-1][v]+item[0])
                max_value = max(max_value, v+item[1])
            # 入れないパターン
            dp[i][v] = min(dp[i][v], dp[i-1][v])
    print(max_value)

if __name__ == '__main__':
    main()

Fixed submission:
import sys
sys.setrecursionlimit(1000000) # 再帰上限を増やす

def main():
    input = sys.stdin.readline  # 文字列に対してinputした場合は、rstripするのを忘れずに！
    N, W = map(int, input().rstrip().split())
    item_list = []
    for _ in range(N):
        w, v = map(int, input().rstrip().split())
        item_list.append((w, v))

    # dp[i][v] = i番目まで見て価値vを達成できる最小の重さ
    dp = [[float("inf")] * (100001) for _ in range(N+1)]
    dp[0][0] = 0

    max_value = 0
    for i, item in enumerate(item_list, 1):
        for v in range(100001):
            # もし品物iが入れられる
            if dp[i-1][v] + item[0] <= W:
                dp[i][v+item[1]] = min(dp[i][v+item[1]], dp[i-1][v]+item[0])
                max_value = max(max_value, v+item[1])
            # 入れないパターン
            dp[i][v] = min(dp[i][v], dp[i-1][v])
    print(max_value)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(1000000) # 再帰上限を増やす

def main():
    input = sys.stdin.readline  # 文字列に対してinputした場合は、rstripするのを忘れずに！
    S = input().rstrip()
    T = input().rstrip()

    # dp[i][j] = sのi番目とtのj番目まででえられる最長部分列の長さ
    dp = [[(0, "")] * (len(T) + 1) for _ in range(len(S) + 1)]

    for i, s in enumerate(S, 1):
        for j, t in enumerate(T, 1):
            # 一致するとき
            if s == t:
                # 一致する文字の一つ左側までの最大部分列に一致した文字を加える
                if dp[i][j][0] < dp[i-1][j-1][0] + 1:
                    dp[i][j] = (dp[i-1][j-1][0] + 1, dp[i-1][j-1][1] + s)
            # 一致しない場合も、一つ手前の文字までの最大文字列を引き継ぐ
            if dp[i][j][0] < dp[i-1][j][0]:
                dp[i][j] = dp[i-1][j]
            if dp[i][j][0] < dp[i][j-1][0]:
                dp[i][j] = dp[i][j-1]
    print(dp[len(S)][len(T)][1])

if __name__ == '__main__':
    main()

Fixed submission:
import sys
sys.setrecursionlimit(1000000) # 再帰上限を増やす

def main():
    input = sys.stdin.readline  # 文字列に対してinputした場合は、rstripするのを忘れずに！
    S = input().rstrip()
    T = input().rstrip()

    # dp[i][j] = sのi番目とtのj番目まででえられる最長部分列の長さ
    dp = [[0] * (len(T) + 1) for _ in range(len(S) + 1)]

    # 最長部分列の長さを探索
    for i, s in enumerate(S, 1):
        for j, t in enumerate(T, 1):
            # 一致するとき
            if s == t:
                # 一致する文字の一つ左側までの最大部分列に一致した文字を加える
                dp[i][j] = max(dp[i][j], dp[i-1][j-1]+1)
            # 一致しない場合も、一つ手前の文字までの最大文字列を引き継ぐ
            dp[i][j] = max(dp[i][j], dp[i-1][j], dp[i][j-1])

    # 最長だった場合の具体例を復元する
    i, j = len(S), len(T)
    ans = ""
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            ans = S[i-1] + ans
            i -= 1
            j -= 1
    print(ans)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
inp = input()
remain = inp[1:-2] + inp[-1]
if inp[0] == "A" && inp[-2] == "C":
  if remain.islower():
    return "AC"
return "WC"

Fixed submission:
inp = input()
count = 0
index = 0
for i in range(len(inp[2:-1])):
  if inp[2:-1][i] == "C":
      count += 1
      index = i
if inp[0] == "A" and count == 1 and (inp[1:2+index]+inp[3+index:]).islower():
  print("AC")
else: 
  print("WA")
Buggy python submission (verdict: Time Limit Exceeded):
K, S = map(int , input().strip().split(" "))


count = 0
for x in range(K+1):
    if x > S :
        break
    elif S - x > 2*K:
        continue
    for y in range(K+1):
        if x + y > S:
            break
        elif S - (x+y) > K:
            continue
        for z in range(K+1):
            if x + y + z > S:
                break
            elif x + y + z == S:
                count +=1
print(count)


Fixed submission:
K, S = map(int , input().strip().split(" "))


count = 0
for x in range(K+1):
    if x > S :
        break
    elif S - x > 2*K:
        continue
    for y in range(K+1):
        if x + y > S:
            break
        elif S - (x+y) > K:
            continue
        count+= 1
print(count)

Buggy python submission (verdict: Time Limit Exceeded):
K, S = map(int , input().strip().split(" "))


count = 0
for x in range(K+1):
    if x > S or S - x > 2*K:
        continue
    for y in range(K+1):
        if x + y > S or S - (x+y) > K:
            continue
        for z in range(K+1):
            if x + y + z > S:
                continue
            elif x + y + z == S:
                count +=1
print(count)

Fixed submission:
K, S = map(int , input().strip().split(" "))


count = 0
for x in range(K+1):
    if x > S :
        break
    elif S - x > 2*K:
        continue
    for y in range(K+1):
        if x + y > S:
            break
        elif S - (x+y) > K:
            continue
        count+= 1
print(count)

Buggy python submission (verdict: Time Limit Exceeded):
K, S = map(int , input().strip().split(" "))


count = 0
for x in range(K+1):
    if x > S:
        continue
    for y in range(K+1):
        if x + y > S:
            continue
        for z in range(K+1):
            if x + y + z > S:
                continue
            elif x + y + z == S:
                count +=1
print(count)


Fixed submission:
K, S = map(int , input().strip().split(" "))


count = 0
for x in range(K+1):
    if x > S :
        break
    elif S - x > 2*K:
        continue
    for y in range(K+1):
        if x + y > S:
            break
        elif S - (x+y) > K:
            continue
        count+= 1
print(count)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**7)

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

combination = [[-1]*(N+1) for i in range(N+1)]

def comb(n, k):
    if n < k:
        return 0
    elif k == n or k == 0:
        return 1
    elif k == 1:
        return n
    elif combination[n][k] != -1:
        return combination[n][k]
    else:
        combination[n][k] = (comb(n-1,k-1)+comb(n-1,k))%MOD
        return combination[n][k]

for i in range(1,K+1):
    print(comb(N-K+1,i)*comb(K-1,i-1)%MOD)
    

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

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

combination = [[-1]*(N+1) for i in range(N+1)]

def comb(n, k):
    if n < k:
        return 0
    elif k == n or k == 0:
        return 1
    elif k == 1:
        return n
    elif combination[n][k] != -1:
        return combination[n][k]
    else:
        combination[n][k] = (comb(n-1,k-1)+comb(n-1,k))%MOD
        return combination[n][k]

for i in range(1,K+1):
    print(comb(N-K+1,i)*comb(K-1,i-1)%MOD)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import queue

input = sys.stdin.readline

N, M = map(int,input().split())
vy = [list(map(lambda x:int(x)-1,input().split())) for i in range(M)]
s, t = map(lambda x:int(x)-1,input().split())

nlist = [[] for i in range(N)]
for v, y in vy:
    nlist[v].append(y)

newnlist = [set() for i in range(N)]
for i in range(N):
    for first in nlist[i]:
        for second in nlist[first]:
            for third in nlist[second]:
                newnlist[i].add(third)

def bfs():
    visit = [False] * N
    Q = queue.Queue()
    visit[s] = True
    Q.put([s,0])
    while not Q.empty():
        node = Q.get()
        if node[0] == t:
            return node[1]
        for i in newnlist[node[0]]:
            if not visit[i]:
                visit[i] = True
                Q.put([i,node[1]+1])
    return -1

ans = bfs()
print(ans)




Fixed submission:
import sys
import queue

input = sys.stdin.readline

N, M = map(int,input().split())
vy = [list(map(lambda x:int(x)-1,input().split())) for i in range(M)]
s, t = map(lambda x:int(x)-1,input().split())

nlist = [[[] for j in range(3)] for i in range(N)]
for v, y in vy:
    nlist[v][0].append([y,1])
    nlist[v][1].append([y,2])
    nlist[v][2].append([y,0])

visit = [[False]*3 for i in range(N)]

def bfs(visit):
    Q = queue.Queue()
    visit[s][0] = True
    Q.put([[s,0],0])
    while not Q.empty():
        node = Q.get()
        if node[0][0] == t and node[0][1] == 0:
            return node[1]
        for i in nlist[node[0][0]][node[0][1]]:
            if not visit[i[0]][i[1]]:
                visit[i[0]][i[1]] = True
                Q.put([[i[0],i[1]],node[1]+1])
    return -1

ans = bfs(visit)
if visit[t][0]:
    print(ans//3)
else:
    print(ans)
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
MOD = 10**9+7
a = set()
for i in range(M):
    a.add(int(input()))

memo = [-1]*(N+1)
memo[0] = 1

def dodp(x):
    if memo[x] != -1:
        pass
    elif x in a:
        memo[x] = 0
    elif x == 1:
        memo[x] = dodp(x-1)
    else:
        memo[x] = dodp(x-1)+dodp(x-2)
    memo[x] %= MOD
    return memo[x]
    
dodp(N)
print(memo[N])


Fixed submission:
N, M = map(int, input().split())
MOD = 10**9+7
a = set()
for i in range(M):
    a.add(int(input()))
step = [0]*(N+1)
step[0] = 1
for i in range(N+1):
    if i == 0:
        pass
    elif i in a:
        step[i] = 0
    elif i == 1:
        step[i] = step[0]
    else:
        step[i] = step[i-1]+step[i-2]
    step[i] %= MOD
print(step[N])
Buggy python submission (verdict: Time Limit Exceeded):
N, M, K = map(int,input().split())
MOD = 10**9+7

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

# 0~N*M-1までの1次元上と考える
ans = 0

def f(x):
    return x*(x+1)//2

c = cmb(N*M-2,K-2)

for i in range(N*M):
    tate, yoko = i//M, i%M
    migi = f(M-1-yoko)
    hidari = f(yoko)
    sita = (hidari+migi)*(N-1-tate) + M*f(N-1-tate)
    coef = migi + sita
    ans += coef*c
    ans %= MOD
print(ans)


    
    
    

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

def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod

# 0~N*M-1までの1次元上と考える
ans = 0

def f(x):
    return x*(x+1)//2

c = comb(N*M-2,K-2,MOD)

for i in range(N*M):
    tate, yoko = i//M, i%M
    migi = f(M-1-yoko)
    hidari = f(yoko)
    sita = (hidari+migi)*(N-1-tate) + M*f(N-1-tate)
    coef = migi + sita
    ans += coef*c
    ans %= MOD
print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
import heapq

input = sys.stdin.readline

X, Y, Z, K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

q = [[(A[0]+B[0]+C[0])*(-1),0,0,0]]
heapq.heapify(q)
count = 0
x, y, z = 0, 0, 0
alr = [[1,1,1]]

while count < K:
    poped = heapq.heappop(q)
    ans = poped[0]*(-1)
    print(ans)
    i, j, k = poped[1], poped[2], poped[3]
    if i+1 < X and not [i+1,j,k] in alr:
        heapq.heappush(q, [(A[i+1]+B[j]+C[k])*(-1), i+1, j, k])
        alr.append([i+1,j,k])
    if j+1 < Y and not [i,j+1,k] in alr:
        heapq.heappush(q, [(A[i]+B[j+1]+C[k])*(-1), i, j+1, k])
        alr.append([i,j+1,k])
    if k+1 < Z and not [i,j,k+1] in alr:
        heapq.heappush(q, [(A[i]+B[j]+C[k+1])*(-1), i, j, k+1])
        alr.append([i,j,k+1])
    count += 1


Fixed submission:
import sys

input = sys.stdin.readline

X, Y, Z, K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
AB = []
ABC = []

for a in A:
    for b in B:
        AB.append(a+b)

AB.sort(reverse=True)
for i in range(min(len(AB), 3000)):
    for c in C:
        ABC.append(AB[i]+c)
        
ABC.sort(reverse=True)

for i in range(K):
    print(ABC[i])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import heapq

input = sys.stdin.readline

X, Y, Z, K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

q = [[(A[0]+B[0]+C[0])*(-1),0,0,0]]
heapq.heapify(q)
count = 0
alr = [[[False]*Z for i in range(Y)] for i in range(X)]
alr[0][0][0] = True

while count < K:
    poped = heapq.heappop(q)
    ans = poped[0]*(-1)
    print(ans)
    i, j, k = poped[1], poped[2], poped[3]
    if i+1 < X and not alr[i+1][j][k]:
        alr[i+1][j][k] = True
        heapq.heappush(q, [(A[i+1]+B[j]+C[k])*(-1), i+1, j, k])
    if j+1 < Y and not alr[i][j+1][k]:
        alr[i][j+1][k] = True
        heapq.heappush(q, [(A[i]+B[j+1]+C[k])*(-1), i, j+1, k])
    if k+1 < Z and not alr[i][j][k+1]:
        alr[i][j][k+1] = True
        heapq.heappush(q, [(A[i]+B[j]+C[k+1])*(-1), i, j, k+1])
    count += 1


Fixed submission:
import sys

input = sys.stdin.readline

X, Y, Z, K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
AB = []
ABC = []

for a in A:
    for b in B:
        AB.append(a+b)

AB.sort(reverse=True)
for i in range(min(len(AB), 3000)):
    for c in C:
        ABC.append(AB[i]+c)
        
ABC.sort(reverse=True)

for i in range(K):
    print(ABC[i])
Buggy python submission (verdict: Time Limit Exceeded):
N, X = map(int,input().split())
S = list(map(int,input().split()))
S.sort()
S.reverse()
S.insert(0,0) # 1-indexed
MOD = 10**9+7
dp = [[0]*(10**5+1) for i in range(N+1)]
dp[0][X] = 1
for i in range(N):
    for x in range(10**5+1):
        dp[i+1][x%S[i+1]] += dp[i][x]
        dp[i+1][x] += dp[i][x]*(N-(i+1))
ans = 0
for x in range(10**5+1):
    ans += (x*dp[N][x])%MOD
print(ans%MOD)

Fixed submission:
N, X = map(int,input().split())
S = list(map(int,input().split()))
S.sort(reverse=True)
S = [0] + S # 1-indexed 
MOD = 10**9+7
dp = [[0]*(10**5+1) for i in range(N+1)]
dp[0][X] = 1
for i in range(N):
    for x in range(10**5+1):
        dp[i+1][x%S[i+1]] += dp[i][x]
        dp[i+1][x] += dp[i][x]*(N-(i+1))
        dp[i+1][x%S[i+1]] %= MOD
        dp[i+1][x] %= MOD
ans = 0
for x in range(10**5+1):
    ans += (x*dp[N][x])%MOD
print(ans%MOD)

Buggy python submission (verdict: Time Limit Exceeded):
N, X = map(int,input().split())
S = list(map(int,input().split()))
S.sort()
S.reverse()
S.insert(0,0) # 1-indexed
MOD = 10**9+7
dp = [[0]*(10**5+1) for i in range(N+1)]
dp[0][X] = 1
for i in range(N):
    for x in range(10**5+1):
        dp[i+1][x%S[i+1]] += dp[i][x]
        dp[i+1][x] += dp[i][x]*(N-(i+1))
ans = 0
for x in range(10**5+1):
    ans = (ans+(x*dp[N][x]))%MOD
print(ans)

Fixed submission:
N, X = map(int,input().split())
S = list(map(int,input().split()))
S.sort(reverse=True)
S = [0] + S # 1-indexed 
MOD = 10**9+7
dp = [[0]*(10**5+1) for i in range(N+1)]
dp[0][X] = 1
for i in range(N):
    for x in range(10**5+1):
        dp[i+1][x%S[i+1]] += dp[i][x]
        dp[i+1][x] += dp[i][x]*(N-(i+1))
        dp[i+1][x%S[i+1]] %= MOD
        dp[i+1][x] %= MOD
ans = 0
for x in range(10**5+1):
    ans += (x*dp[N][x])%MOD
print(ans%MOD)
Buggy python submission (verdict: Runtime Error):
import fraction
from functools import reduce
 
def gcd(*numbers):
    return reduce(fraction.gcd, numbers)
 
n = int(input())
a = list(map(int, input().split()))
print(gcd(*a))

Fixed submission:
import fractions
from functools import reduce
 
def gcd(*numbers):
    return reduce(fractions.gcd, numbers)
 
n = int(input())
a = list(map(int, input().split()))
print(gcd(*a))

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

def gcd(*numbers):
    return reduce(math.gcd, numbers)

n = int(input())
a = list(map(int, input().split()))
print(gcd(*a))

Fixed submission:
import fractions
from functools import reduce
 
def gcd(*numbers):
    return reduce(fractions.gcd, numbers)
 
n = int(input())
a = list(map(int, input().split()))
print(gcd(*a))
Buggy python submission (verdict: Runtime Error):
4 2 6

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

if a >= b:
    print(1+k)
else:
    p1 = [1,1]
    p2 = [b-a,2]
    proc = [p1,p2]
    proc.sort(key=lambda x:x[0]/x[1])
    proc.reverse()
    if proc[0] == p1:
        print(1+k)
    elif proc[0] == p2:
        if a-1 > k:
            print(1+k)
        else:
            print(a+((k-a+1)//2)*(b-a)+(k-a+1)%2)