Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
Mod = 10**9+7
S = input()
N = len(S)
O = 1
A = [0]*N
AB = [0]*N
ABC = [0]*N

for i in range(N):
    A[i] = A[i-1]
    AB[i] = AB[i-1]
    ABC[i] = ABC[i-1]
    if S[i] == 'A':
        A[i] += O
    if S[i] == 'B':
        AB[i] += A[i-1]
    if S[i] == 'C':
        ABC[i] += AB[i-1]
    if S[i] == '?':
        A[i] *= 3
        A[i] += O
        AB[i] *= 3
        AB[i] += A[i-1]
        ABC[i] *= 3
        ABC[i] += AB[i-1]
        O *= 3
    A[i] %= Mod
    AB[i] %= Mod
    ABC[i] %= Mod

print(ABC[-1])

Fixed submission:
Mod = 10**9+7
S = input()
N = len(S)
O = 1
A = [0]*N
AB = [0]*N
ABC = [0]*N

for i in range(N):
    A[i] = A[i-1]
    AB[i] = AB[i-1]
    ABC[i] = ABC[i-1]
    if S[i] == 'A':
        A[i] += O
    if S[i] == 'B':
        AB[i] += A[i-1]
    if S[i] == 'C':
        ABC[i] += AB[i-1]
    if S[i] == '?':
        A[i] *= 3
        A[i] += O
        AB[i] *= 3
        AB[i] += A[i-1]
        ABC[i] *= 3
        ABC[i] += AB[i-1]
        O *= 3
    A[i] %= Mod
    AB[i] %= Mod
    ABC[i] %= Mod
    O %= Mod
print(ABC[-1])
Buggy python submission (verdict: Runtime Error):
K = int(input())

snuke = [1,2,3,4,5,6,7,8,9,19,29,39,49,59,69,79,89,99,199,299,399,499,599,699,799,899,999]

for n in range(3,16):
    for k in range(1,11):
        snuke.append(10**(n-1)*(10+k)-1)
    for k in range(2,10):
        snuke.append((k+1)*10**n-1)

for k in range(K):
    print(snuke[k])

Fixed submission:
def snk_cal(i):
    snk = i
    i = str(i)
    q = 0
    for j in range(len(i)):
        q += int(i[j])
    snk /= q
    return snk

K = int(input())
if K <= 9:
    for i in range(K):
        print(i+1)
else:
    for i in range(9):
        print(i+1)
    K -= 9
    snk = 9
    while K > 0:
        res = snk+1
        d = len(str(res))
        l = []
        for i in range(d):
            n = int(str(res)[:-i-1]+'9'*(i+1))
            l.append(snk_cal(n))
        i = l.index(min(l))
        snk = int(str(res)[:-i-1]+'9'*(i+1))
        print(snk)
        K -= 1

Buggy python submission (verdict: Runtime Error):
K = int(input())

snuke = [1,2,3,4,5,6,7,8,9,19,29,39,49,59,69,79,89,99,199,299,399,499,599,699,799,899,999]

for n in range(3,16):
    for k in range(1,10):
        snuke.append(10**(n-1)*(10+k)-1)
    for k in range(2,10):
        snuke.append((k+1)*10**n-1)

for k in range(K):
    print(snuke[k])

Fixed submission:
def snk_cal(i):
    snk = i
    i = str(i)
    q = 0
    for j in range(len(i)):
        q += int(i[j])
    snk /= q
    return snk

K = int(input())
if K <= 9:
    for i in range(K):
        print(i+1)
else:
    for i in range(9):
        print(i+1)
    K -= 9
    snk = 9
    while K > 0:
        res = snk+1
        d = len(str(res))
        l = []
        for i in range(d):
            n = int(str(res)[:-i-1]+'9'*(i+1))
            l.append(snk_cal(n))
        i = l.index(min(l))
        snk = int(str(res)[:-i-1]+'9'*(i+1))
        print(snk)
        K -= 1
Buggy python submission (verdict: Runtime Error):
inf = 1000*500*500
D = []
c = []
d = {}
N,C = map(int,input().split())
for i in range(C):
    D.append(list(map(int,input().split())))
for i in range(N):
    c.append(list(map(int,input().split())))

for C1 in range(C):
    for C2 in range(C):
        for C3 in range(C):
            if C1 != C2 and C2 != C3 and C3 != C1:
                d[(C1+1,C2+1,C3+1)]=0
            else:
                d[C1+1,C2+1,C3+1]=inf

for i in range(N):
    for j in range(N):
        for C1 in range(C):
            for C2 in range(C):
                for C3 in range(C):
                    if (i+j)%3==0:
                        d[(C1+1,C2+1,C3+1)]+=D[c[i][j]-1][C1]
                    elif (i+j)%3==1:
                        d[(C1+1,C2+1,C3+1)]+=D[c[i][j]-1][C2]
                    else:
                        d[(C1+1,C2+1,C3+1)]+=D[c[i][j]-1][C3]

l = []
for x in d:
    l.append(d[x])
print(min(l))


Fixed submission:
n = int(input())
if n > 999:
    print("ABD")
else:
    print("ABC")
Buggy python submission (verdict: Runtime Error):
N,A,B,K = map(int,input().split())
n = 0
MOD = 998244353
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


memo = [0]*(N+1)
memo[0] = memo[N] = 1
for k in range(1,N//2+1):
  v = memo[k-1]*(N-k+1)*modinv(k,MOD)
  v %= MOD
  memo[k] = memo[N-k] = v
for i in range(N+1):
    j = K-A*i
    if j < 0:
        break
    if (K-A*i)%B==0:
        j //= B
        n+=(memo[i]*memo[j])%998244353
        n%=998244353
print(n%998244353)

Fixed submission:
N,A,B,K = map(int,input().split())
n = 0
MOD = 998244353
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


memo = [0]*(N+1)
memo[0] = memo[N] = 1
for k in range(1,N//2+1):
  v = memo[k-1]*(N-k+1)*modinv(k,MOD)
  v %= MOD
  memo[k] = memo[N-k] = v
for i in range(N+1):
    j = K-A*i
    if j < 0:
        break
    if j%B==0 and j/B <= N:
        j //= B
        n+=memo[i]*memo[j]
        n%=998244353
print(n%998244353)

Buggy python submission (verdict: Runtime Error):
MOD = 998244353
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


memo = [0]*(N+1)
memo[0] = memo[N] = 1
for k in range(1,N//2+1):
  v = memo[k-1]*(N-k+1)*modinv(k,MOD)
  v %= MOD
  memo[k] = memo[N-k] = v

N,A,B,K = map(int,input().split())
n = 0

for i in range(N+1):
    j = K-A*i
    if j < 0:
        break
    if (K-A*i)%B==0:
        j //= B
        n+=(memo[i]*memo[j])%998244353
        n%=998244353
print(n%998244353)

Fixed submission:
N,A,B,K = map(int,input().split())
n = 0
MOD = 998244353
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


memo = [0]*(N+1)
memo[0] = memo[N] = 1
for k in range(1,N//2+1):
  v = memo[k-1]*(N-k+1)*modinv(k,MOD)
  v %= MOD
  memo[k] = memo[N-k] = v
for i in range(N+1):
    j = K-A*i
    if j < 0:
        break
    if j%B==0 and j/B <= N:
        j //= B
        n+=memo[i]*memo[j]
        n%=998244353
print(n%998244353)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [0]*N
for i in range(N):
    A[i] = int(input())

B = [0]*N
possible = True
tot = 0
for i in range(N):
    if A[-(i+1)] > N-i-1:
        possible = False
        break
    elif B[-(i+1)] > A[-(i+1)]:
        possible = False
        break
    elif B[-(i+1)] == A[-(i+1)]:
        continue
    else:
        if i == 0:
            B[-(i+1+A[-(i+1)]):] = range(A[-(i+1)]+1)
            tot += A[-(i+1)]
        else:
            B[-(i+1+A[-(i+1)]):-i] = range(A[-(i+1)]+1)
            tot += A[-(i+1)]
if not possible:
    print(-1)
else:
    print(tot)

Fixed submission:
N = int(input())
A = [0]*N
for i in range(N):
    A[i] = int(input())

B = [0]*N
possible = True
tot = 0
if A[0] == 0:
    for i in range(N-1):
        if A[-(i+1)] > N-i-1:
            possible = False
            break
        elif B[-(i+1)] > A[-(i+1)]:
            possible = False
            break
        elif B[-(i+1)] == A[-(i+1)]:
            B[-(i+2)] = A[-(i+1)]-1
            continue
        else:
            B[-(i+2)] = A[-(i+1)]-1
            tot += A[-(i+1)]
    if not possible:
        print(-1)
    else:
        print(tot)
else:
    print(-1)
Buggy python submission (verdict: Runtime Error):
p = []
def is_prime_trial_division(n):
    if n < 2:
        return False
    else:
        for i in range(2, n):
            if i * i > n:
                break
            elif n % i == 0:
                return False
        return True
for i in range(2,55555):
    if is_prime_trial_division(i):
        p.append(i)
N = int(input())
s = ""
for i in range(N):
    s += str(p[5500+i*2]) + " "
s = s[:-1]
print(s)

Fixed submission:
a,b = map(int,input().split())
if b < a:
    a -= 1
print(a)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
a = list(map(int,input().split()))
s = [0]*(len(a)+1)
for i in range(len(a)):
    s[i+1] = s[i] + a[i]
s.sort()
n = 0
for x in set(s):
    l = s.count(x)
    n += l*(l-1)/2
print(int(n))

Fixed submission:
N = int(input())
a = list(map(int,input().split()))
s = [0]*(len(a)+1)
for i in range(len(a)):
    s[i+1] = s[i] + a[i]
b = {}
for x in s:
    if str(x) not in b:
        b[str(x)] = 1
    else:
        b[str(x)] += 1
n = 0
for x in b:
    n += b[x]*(b[x]-1)/2
print(int(n))

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
a = list(map(int,input().split()))
n = 0
for i in range(1,N+1):
    for j in range(N+1-i):
        b = a[j:j+i]
        S = 0
        for x in b:
            S += x
        if S == 0:
            n += 1
print(n)

Fixed submission:
N = int(input())
a = list(map(int,input().split()))
s = [0]*(len(a)+1)
for i in range(len(a)):
    s[i+1] = s[i] + a[i]
b = {}
for x in s:
    if str(x) not in b:
        b[str(x)] = 1
    else:
        b[str(x)] += 1
n = 0
for x in b:
    n += b[x]*(b[x]-1)/2
print(int(n))

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
a = list(map(int,input().split()))
n = 0
for i in range(1,N+1):
    for j in range(N+1-i):
        S = 0
        for x in a[j:j+i]:
            S += x
        if S == 0:
            n += 1
print(n)

Fixed submission:
N = int(input())
a = list(map(int,input().split()))
s = [0]*(len(a)+1)
for i in range(len(a)):
    s[i+1] = s[i] + a[i]
b = {}
for x in s:
    if str(x) not in b:
        b[str(x)] = 1
    else:
        b[str(x)] += 1
n = 0
for x in b:
    n += b[x]*(b[x]-1)/2
print(int(n))

Buggy python submission (verdict: Runtime Error):
a = list(map(int,input().split()))
n = 0
for i in range(1,N+1):
    for j in range(N+1-i):
        S = 0
        for x in a[j:j+i]:
            S += x
        if S == 0:
            n += 1
print(n)

Fixed submission:
N = int(input())
a = list(map(int,input().split()))
s = [0]*(len(a)+1)
for i in range(len(a)):
    s[i+1] = s[i] + a[i]
b = {}
for x in s:
    if str(x) not in b:
        b[str(x)] = 1
    else:
        b[str(x)] += 1
n = 0
for x in b:
    n += b[x]*(b[x]-1)/2
print(int(n))

Buggy python submission (verdict: Time Limit Exceeded):
from numpy import array as arr
N = int(input())
a = arr(list(map(int,input().split())))
n = 0
for i in range(1,N+1):
    for j in range(N+1-i):
        if a[j:j+i].sum() == 0:
            n += 1
print(n)

Fixed submission:
N = int(input())
a = list(map(int,input().split()))
s = [0]*(len(a)+1)
for i in range(len(a)):
    s[i+1] = s[i] + a[i]
b = {}
for x in s:
    if str(x) not in b:
        b[str(x)] = 1
    else:
        b[str(x)] += 1
n = 0
for x in b:
    n += b[x]*(b[x]-1)/2
print(int(n))
Buggy python submission (verdict: Runtime Error):
N,X = map(int, input())
m = [int(input()) for i in range(N)]
for x in m:
  X -= x
m.sort()
n = int(X/m[0])
print(n + len(m))

Fixed submission:
N,X = map(int, input().split())
m = [int(input()) for i in range(N)]
for x in m:
  X -= x
m.sort()
n = int(X/m[0])
print(n + len(m))
Buggy python submission (verdict: Runtime Error):
N = int(input())
import numpy as np
l = np.array(map(int,input().split()))
for i in range(N):
    print(np.delete(l,i).median())

Fixed submission:
N = int(input())
l = list(map(int,input().split()))
ll = sorted(l)
n = int(N/2)
a = ll[n-1]
b = ll[n]
for i in range(N):
    if l[i] <= a:
        print(b)
    else:
        print(a)
Buggy python submission (verdict: Time Limit Exceeded):
Q = int(input())
for i in range(Q):
    a = list(map(int,input().split()))
    a.sort()
    A = a[0]
    B = a[1]
    n = 0
    if A==B:
        n = 2*A-2
    elif B == A+1:
        n = 2*A-2
    else:
        j = 0
        while True:
            j+=1
            if j*j >= A*B:
                C = j-1
                break
        if C*(C+1)>=A*B:
            n = 2*C-2
        else:
            n = 2*C-1
    print(n)

Fixed submission:
import math
Q = int(input())
for i in range(Q):
    a = list(map(int,input().split()))
    a.sort()
    A = a[0]
    B = a[1]
    n = 0
    if A==B:
        n = 2*A-2
    elif B == A+1:
        n = 2*A-2
    else:
        C = math.ceil(math.sqrt(A*B)-1)
        if C*(C+1)>=A*B:
            n = 2*C-2
        else:
            n = 2*C-1
    print(n)

Buggy python submission (verdict: Runtime Error):
Q = int(input())
for i in range(Q):
    a = list(map(int,input().split()))
    a.sort()
    A = a[0]
    B = a[1]
    n = 0
    if A==B:
        n = 2*A-2
    elif B == A+1:
        n = 2*A-2
    else:
        j = 0
        while True:
            j+=1
            if j*j >= A*B:
                C = j-1
                break
        if C*(C+1)>=A*B:
            n = 2*C-2
        else:
            n = 2*C-1
    print(C)

Fixed submission:
import math
Q = int(input())
for i in range(Q):
    a = list(map(int,input().split()))
    a.sort()
    A = a[0]
    B = a[1]
    n = 0
    if A==B:
        n = 2*A-2
    elif B == A+1:
        n = 2*A-2
    else:
        C = math.ceil(math.sqrt(A*B)-1)
        if C*(C+1)>=A*B:
            n = 2*C-2
        else:
            n = 2*C-1
    print(n)
Buggy python submission (verdict: Runtime Error):
A,B = map(int,input().split())

l = [["."]*100]*50
ll = [["#"]*100]*50

a = 1
b = 1

for i in range(5):
    for j in range(50):
        l[i*2][j*2] = "."
        a += 1
        if a == B:
            break
            break
for i in range(5):
    for j in range(50):
        ll[i*2][j*2] = "#"
        b += 1
        if b == A:
            break
            break

print(100 100)
def l_to_str(l):
    s = ""
    for x in l:
        s+=x
    return s
for i in l:
    print(l_to_str(i))
for i in ll:
    print(l_to_str(i))

Fixed submission:
A,B = map(int,input().split())

d = {}
for i in range(50):
    d[i] = ["."]*100
for i in range(50,100):
    d[i] = ["#"]*100
a = 1
b = 1

for i in range(10):
    if a == B:
        break
    for j in range(50):
        if a == B:
            break
        else:
            d[i*2][j*2] = "#"
            a += 1
    
        
        
for i in range(10):
    if b == A:
        break
    for j in range(50):
        if b == A:
            break
        else:
            d[i*2+51][j*2] = "."
            b += 1
    

print("100 100")
def l_to_str(l):
    s = ""
    for x in l:
        s+=x
    return s
for i in range(100):
    print(l_to_str(d[i]))
Buggy python submission (verdict: Runtime Error):
print(inpit()[0]+input()[1]+input()[2])

Fixed submission:
print(input()[0]+input()[1]+input()[2])
Buggy python submission (verdict: Runtime Error):
S = input()
T = []
for i in range(len(S)-1):
    if S[i] != S[i+1]:
        T.append(max(i+1,len(S)-i-1))
print(min(T))

Fixed submission:
S = input()
T = []
for i in range(len(S)-1):
    if S[i] != S[i+1]:
        T.append(max(i+1,len(S)-i-1))
if T != []:
    print(min(T))
else:
    print(len(S))
Buggy python submission (verdict: Runtime Error):
N,C = map(int,input().split())
cum = [0]*(10**5+1)
d = {}
for i in range(10**5):
    d[i] = []
for i in range(N):
    s,t,c = map(int,input().split())
    if c not in d[s]:
        cum[s-1] += 1
        cum[t] -= 1
    else:
        cum[s] += 1
        cum[t] -= 1
    d[t].append(c)
import numpy as np
print(np.cumsum(cum).max())

Fixed submission:
N,C = map(int,input().split())
r = [[0]*(10**5) for c in range(C)]
for i in range(N):
    s,t,c = map(int,input().split())
    r[c-1][s-1:t] = [1]*(t-s+1)
print(max(map(sum,zip(*r))))
Buggy python submission (verdict: Time Limit Exceeded):
import copy
N = int(input())
A = [list(map(int,input().split())) for i in range(N)]
cost = copy.deepcopy(A)
edge = copy.deepcopy(A)
for k in range(N):
    for i in range(N):
        for j in range(i):
            if i != k and j != k:
                if cost[i][j] == cost[i][k]+cost[k][j]:
                    edge[i][j] = 0
                if cost[i][j] > cost[i][k]+cost[k][j]:
                    cost[i][j] = cost[i][k]+cost[k][j]
ans = True
for i in range(N):
    for j in range(i):
        if A[i][j] != cost[i][j]:
            ans = False
            break
if not ans:
    print(-1)
else:
    ans = 0
    for i in range(N):
        for j in range(i):
            ans += edge[i][j]
    print(ans)

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

from scipy.sparse.csgraph import floyd_warshall as fw
import numpy as np
a = fw(A)
ans = 0
for i in range(N):
    a[i][i] = np.inf
for i in range(N):
    for j in range(i):
        if A[i][j]!=a[i][j]:
            print(-1)
            exit()
        else:
            if a[i][j] < np.min(a[i]+a[j]):
                ans += a[i][j]
print(int(ans))

Buggy python submission (verdict: Time Limit Exceeded):
import copy
N = int(input())
A = [list(map(int,input().split())) for i in range(N)]
cost = copy.deepcopy(A)
edge = [[True for i in range(N)] for i in range(N)]
for k in range(N):
    for i in range(N):
        for j in range(N):
            if i != k and j != k:
                if cost[i][j] == cost[i][k]+cost[k][j]:
                    edge[i][j] = False
                if cost[i][j] > cost[i][k]+cost[k][j]:
                    cost[i][j] = cost[i][k]+cost[k][j]

if A != cost:
    print(-1)
else:
    import numpy as np
    A = np.array(A)
    edge = np.array(edge)
    print(A[edge].sum()//2)

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

from scipy.sparse.csgraph import floyd_warshall as fw
import numpy as np
a = fw(A)
ans = 0
for i in range(N):
    a[i][i] = np.inf
for i in range(N):
    for j in range(i):
        if A[i][j]!=a[i][j]:
            print(-1)
            exit()
        else:
            if a[i][j] < np.min(a[i]+a[j]):
                ans += a[i][j]
print(int(ans))
Buggy python submission (verdict: Time Limit Exceeded):
from scipy.sparse.csgraph import dijkstra
import numpy as np

N = int(input())
edge = [[np.inf for i in range(N)] for i in range(N)]
for i in range(N-1):
    a,b,c = map(int,input().split())
    edge[a-1][b-1] = c
    edge[b-1][a-1] = c
Q,K = map(int,input().split())
cost = dijkstra(edge,False,K-1)
for i in range(Q):
    x,y = map(int,input().split())
    print(int(cost[x-1]+cost[y-1]))

Fixed submission:
N = int(input())
graph = [[] for i in range(N)]
for i in range(N-1):
    a,b,c = map(int,input().split())
    graph[a-1].append((c,b-1))
    graph[b-1].append((c,a-1))
Q,K = map(int,input().split())

from heapq import heappush, heappop
def dijkstra(graph:list, node:int, start:int) -> list:
    # graph[node] = [(cost, to)]
    inf = float('inf')
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    while heap:
        cost,thisNode = heappop(heap)
        for NextCost,NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    return dist
    # dist = [costs to nodes]

cost = dijkstra(graph,N,K-1)
for i in range(Q):
    x,y = map(int,input().split())
    print(int(cost[x-1]+cost[y-1]))

Buggy python submission (verdict: Time Limit Exceeded):
from scipy.sparse.csgraph import dijkstra
import numpy as np

N = int(input())
edge = [[np.inf for i in range(N+1)] for i in range(N+1)]
for i in range(N-1):
    a,b,c = map(int,input().split())
    edge[a][b] = c
    edge[b][a] = c
Q,K = map(int,input().split())
cost = dijkstra(edge,indices=K)
for i in range(Q):
    x,y = map(int,input().split())
    print(int(cost[x]+cost[y]))

Fixed submission:
N = int(input())
graph = [[] for i in range(N)]
for i in range(N-1):
    a,b,c = map(int,input().split())
    graph[a-1].append((c,b-1))
    graph[b-1].append((c,a-1))
Q,K = map(int,input().split())

from heapq import heappush, heappop
def dijkstra(graph:list, node:int, start:int) -> list:
    # graph[node] = [(cost, to)]
    inf = float('inf')
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    while heap:
        cost,thisNode = heappop(heap)
        for NextCost,NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    return dist
    # dist = [costs to nodes]

cost = dijkstra(graph,N,K-1)
for i in range(Q):
    x,y = map(int,input().split())
    print(int(cost[x-1]+cost[y-1]))
Buggy python submission (verdict: Runtime Error):
N,A,B=map(int,input().split())
H = [int(input()) for i in range(N)]
H.sort()
from math import ceil
def KnockOut(t):
    base = B*t
    res = 0
    for i in range(j,N):
        h = H[i]
        h -= base
        if h > 0:
            res += ceil(h/(A-B))
    return res <= t
l = 1
r = ceil(sum(H)/(N*B))
while l != r-1:
    t = int((l+r)/2)
    if KnockOut(t):
        r = t
    else:
        l = t
print(r)            

Fixed submission:
N,A,B=map(int,input().split())
H = [int(input()) for i in range(N)]
H.sort()
from math import ceil
def KnockOut(t):
    base = B*t
    for i in range(N):
        h = H[i]
        h -= base
        if h > 0:
            t -= ceil(h/(A-B))
            if t < 0:
                return False
    return True
l = 0
r = ceil(max(H)/B)
while l != r-1:
    t = int((l+r)/2)
    if KnockOut(t):
        r = t
    else:
        l = t
print(r)
Buggy python submission (verdict: Runtime Error):
N,M = map(int,input().split())
edge = [0]*M
for i in range(M):
    a,b,c=map(int,input().split())
    a -= 1
    b -= 1
    c *= -1
    edge[i] = (a,b,c)

inf = float('inf')
V = N
E = M
d = [inf]*V
d[0] = 0
for i in range(V):
    update = False
    for j in range(E):
        From,To,cost = edge[j]
        if d[From] != inf and d[To]>d[From]+cost:
            d[To]=d[From]+cost
            update = True
    if not update:
        break
loop = False
for j in range(E):
    From,To,cost = edge[j]
    if d[From] != inf and d[To]>d[From]+cost:
        loop = True
        break

if loop:
    print('inf')
else:
    print(-ans)

Fixed submission:
N,M = map(int,input().split())
edge = [0]*M
for i in range(M):
    a,b,c=map(int,input().split())
    a -= 1
    b -= 1
    c *= -1
    edge[i] = (a,b,c)

inf = float('inf')
V = N
E = M
d = [inf]*V
d[0] = 0
for i in range(V):
    for j in range(E):
        From,To,cost = edge[j]
        if d[From] != inf and d[To]>d[From]+cost:
            d[To]=d[From]+cost
ans = d[N-1]
for i in range(V):
    for j in range(E):
        From,To,cost = edge[j]
        if d[From] != inf and d[To]>d[From]+cost:
            d[To]=d[From]+cost

if d[N-1]!=ans:
    print('inf')
else:
    print(-ans)

Buggy python submission (verdict: Runtime Error):
N,M = map(int,input().split())
edge = [0]*M
for i in range(M):
    a,b,c=map(int,input().split())
    a -= 1
    b -= 1
    c *= -1
    edge[i] = (a,b,c)

inf = float('inf')
V = N
E = M
def shortest_path(s,d):
    for i in range(V):
        for j in range(E):
            From,To,cost = edge[j]
            if d[From] != inf and d[To]>d[From]+cost:
                d[To]=d[From]+cost                
    return d
d = [inf]*V
d[0] = 0
d = shortest_path(0,d)
d_ = shortest_path(0,d)
if d[N-1]!=d_[N-1]
    print('inf')
else:
    print(-d[N-1])

Fixed submission:
N,M = map(int,input().split())
edge = [0]*M
for i in range(M):
    a,b,c=map(int,input().split())
    a -= 1
    b -= 1
    c *= -1
    edge[i] = (a,b,c)

inf = float('inf')
V = N
E = M
d = [inf]*V
d[0] = 0
for i in range(V):
    for j in range(E):
        From,To,cost = edge[j]
        if d[From] != inf and d[To]>d[From]+cost:
            d[To]=d[From]+cost
ans = d[N-1]
for i in range(V):
    for j in range(E):
        From,To,cost = edge[j]
        if d[From] != inf and d[To]>d[From]+cost:
            d[To]=d[From]+cost

if d[N-1]!=ans:
    print('inf')
else:
    print(-ans)