Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import numpy as np
def main():
    H, N = map(int, input().split())
    l = []
    for _ in range(N):
        a, b = map(int, input().split())
        l.append((a,b))
    dp = np.array([[0] * N for _ in range(H)])
    for w in range(H):
        if (w+1) % l[0][0] == 0:
            dp[w][0] = l[0][1] * ((w+1)//l[0][0])
        else:
            dp[w][0] = l[0][1] * (1 + ((w+1)//l[0][0]))
    for i in range(1, N):
        for w in range(H):
            if w + 1 > l[i][0]:
                m = min(dp.T[i][w-l[i][0]:w])
                dp[w][i] = min(m + l[i][1], dp[w][i-1])
            else:
                dp[w][i] = dp[w][i-1]
    print(min(dp[-1]))
main()


Fixed submission:
def main():
    H, N = map(int, input().split())
    l = []
    for _ in range(N):
        a, b = map(int, input().split())
        l.append((a,b))
    dp = [[0] * N for _ in range(H+1)]
    for w in range(H+1):
        if w % l[0][0] == 0:
            dp[w][0] = l[0][1] * (w//l[0][0])
        else:
            dp[w][0] = l[0][1] * (1 + (w//l[0][0]))
    for i in range(1, N):
        for w in range(H+1):
            if w > l[i][0]:
                dp[w][i] = min(dp[w-l[i][0]][i] + l[i][1], dp[w][i-1])
            else:
                dp[w][i] = min(dp[w][i-1], l[i][1])
    print(min(dp[-1]))
main()
Buggy python submission (verdict: Time Limit Exceeded):
import fractions
def main():
    N = int(input())
    A = list(map(int, input().split()))
    g = A[0]
    l = A[0]
    for i in A[1:]:
        g = fractions.gcd(g, i)
        l = l * i // fractions.gcd(l, i)
    r = 0
    mod = 10 ** 9 + 7
    n = l // g
    for i in A:
        r += (n // (i // g)) % mod
    print(r % mod)
main()




Fixed submission:
import fractions
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
def main():
    N = int(input())
    A = list(map(int, input().split()))
    g = A[0]
    l = A[0]
    for i in A[1:]:
        g = fractions.gcd(g, i)
        l = l * i // fractions.gcd(l, i)
    r = 0
    mod = 10 ** 9 + 7
    n = (l // g) % mod
    for i in A:
        r += n * modinv(i//g, mod)
    print(r % mod)
main()
Buggy python submission (verdict: Runtime Error):
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
def main():
    H, W = map(int, input().split())
    m = []
    for _ in range(H):
        l = input()
        m.append(l)
    edge = []
    v = H * W
    for i in range(H):
        for j in range(W):
            t = i * H + j
            edge.append([10 ** 9] * v)
            if m[i][j] == '.':
                if i > 0 and m[i-1][j] == '.':
                    edge[t][(i-1) * H + j] = 1
                if j > 0 and m[i][j -1] == '.':
                    edge[t][i * H + j - 1] = 1
                if i < H-1 and m[i+1][j] == '.':
                    edge[t][(i + 1)*H + j] = 1
                if j < W - 1 and m[i][j+1] == '.':
                    edge[t][i * H + j + 1] = 1
    G = csgraph_from_dense(edge, null_value=10**9)
    d = floyd_warshall(G)
    m = 0
    for i in range(v):
        for j in range(v):
            if d[i][j] != float('inf') and d[i][j] > m:
                m = d[i][j]
    print(int(m))
main()
    


Fixed submission:
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
def main():
    H, W = map(int, input().split())
    m = []
    for _ in range(H):
        l = input()
        m.append(l)
    edge = []
    v = H * W
    for i in range(H):
        for j in range(W):
            t = i * W + j
            edge.append([10 ** 9] * v)
            if m[i][j] == '.':
                if i > 0 and m[i-1][j] == '.':
                    edge[t][(i-1) * W + j] = 1
                if j > 0 and m[i][j -1] == '.':
                    edge[t][i * W + j - 1] = 1
                if i < H-1 and m[i+1][j] == '.':
                    edge[t][(i + 1)*W + j] = 1
                if j < W - 1 and m[i][j+1] == '.':
                    edge[t][i * W + j + 1] = 1
    G = csgraph_from_dense(edge, null_value=10**9)
    d = floyd_warshall(G)
    m = 0
    for i in range(v):
        for j in range(v):
            if d[i][j] != float('inf') and d[i][j] > m:
                m = d[i][j]
    print(int(m))
main()
Buggy python submission (verdict: Runtime Error):
import fractions
def main():
    N, M = map(int, input().split())
    a = tuple(map(int, input().split()))
    s = a[0]
    s2 = max(a)
    s3 = 0
    while True:
        if s2 % 2 == 0:
            s2 /= 2
            s3 +=1
        else:
            break
    for i in a:
        if i % (2 ** s3) != 0:
            print(0)
            return 0
    for i in range(1,N):
        s = s * a[i] // fractions.gcd(s, a[i])
    s /= 2
    a = int(M // (2*s))
    if (M // s) % 2 == 0:
        print(a)
    else:
        print(a+1)
main()



Fixed submission:
import fractions
def main():
    N, M = map(int, input().split())
    a = tuple(map(int, input().split()))
    s = a[0]
    s2 = a[0]
    s3 = 0
    while True:
        if s2 % 2 == 0:
            s2 /= 2
            s3 +=1
        else:
            break
    if s3 == 0:
        print(0)
        return 0
    for i in a:
        if i % (2 ** s3) != 0:
            print(0)
            return 0
        elif i % (2 ** (s3 + 1)) == 0:
            print(0)
            return 0
    for i in range(1,N):
        s = s * a[i] // fractions.gcd(s, a[i])
        if s > M*2:
            print(0)
            return 0
    s /= 2
    a = int(M // (2*s))
    if (M // s) % 2 == 0:
        print(a)
    else:
        print(a+1)
main()

Buggy python submission (verdict: Runtime Error):
import fractions
def main():
    N, M = map(int, input().split())
    a = tuple(map(int, input().split()))
    s = a[0]
    for i in range(1,N):
        s = s * a[i] // fractions.gcd(s, a[i])
    s /= 2
    a = int(M // (2*s))
    if (M // s) % 2 == 0:
        print(a)
    else:
        print(a+1)
main()


Fixed submission:
import fractions
def main():
    N, M = map(int, input().split())
    a = tuple(map(int, input().split()))
    s = a[0]
    s2 = a[0]
    s3 = 0
    while True:
        if s2 % 2 == 0:
            s2 /= 2
            s3 +=1
        else:
            break
    if s3 == 0:
        print(0)
        return 0
    for i in a:
        if i % (2 ** s3) != 0:
            print(0)
            return 0
        elif i % (2 ** (s3 + 1)) == 0:
            print(0)
            return 0
    for i in range(1,N):
        s = s * a[i] // fractions.gcd(s, a[i])
        if s > M*2:
            print(0)
            return 0
    s /= 2
    a = int(M // (2*s))
    if (M // s) % 2 == 0:
        print(a)
    else:
        print(a+1)
main()
Buggy python submission (verdict: Time Limit Exceeded):
class cmbs(object):
    def __init__(self, mod):
        self.mod = mod
        self.g1 = [1, 1]
        self.g2 = [1, 1]
        inverse = [0, 1]
        for i in range(2, 10 ** 6 + 1):
            self.g1.append((self.g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod // i)) % mod)
            self.g2.append((self.g2[-1] * inverse[-1]) % mod)

    def cmb(self, n, r):
        if n > 10 ** 6:
            return self.cmbl(n, r)
        return self.cmbr(n, r)

    def cmbr(self, n, r):
        if r < 0 or r > n:
            return 0
        r = min(r, n - r)
        return self.g1[n] * self.g2[r] * self.g2[n-r] % self.mod

    def cmbl(self, n, r):
        t = 1
        r = min(r, n-r)
        for i in range(n - r + 1, n + 1):
            t = t * i % self.mod
        return t * self.g2[r] % self.mod
def main():
    N = int(input())
    mod = 10**9 + 7
    C = list(map(int, input().split()))
    C.sort()
    c = cmbs(mod)
    r = 0
    for i, v in enumerate(C):
        t = 0
        for j in range(i, N):
            t += (j - i + 1) * c.cmb(N-i-1, j-i)
        t *= v * pow(2, i, mod)
        r += t
    r *= pow(2, N, mod)
    r %= mod
    return r
print(main())


Fixed submission:
class cmbs(object):
    def __init__(self, mod):
        self.mod = mod
        self.g1 = [1, 1]
        self.g2 = [1, 1]
        inverse = [0, 1]
        for i in range(2, 10 ** 6 + 1):
            self.g1.append((self.g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod // i)) % mod)
            self.g2.append((self.g2[-1] * inverse[-1]) % mod)

    def cmb(self, n, r):
        if n > 10 ** 6:
            return self.cmbl(n, r)
        return self.cmbr(n, r)

    def cmbr(self, n, r):
        if r < 0 or r > n:
            return 0
        r = min(r, n - r)
        return self.g1[n] * self.g2[r] * self.g2[n-r] % self.mod

    def cmbl(self, n, r):
        t = 1
        r = min(r, n-r)
        for i in range(n - r + 1, n + 1):
            t = t * i % self.mod
        return t * self.g2[r] % self.mod
def main():
    N = int(input())
    mod = 10**9 + 7
    C = list(map(int, input().split()))
    C.sort()
    r = 0
    for i, v in enumerate(C[:-1]):
        t = pow(2, N-i-2, mod) * (N- i + 1)
        t *= v * pow(2, i, mod)
        r += t
    r += C[-1] * pow(2, N-1, mod)
    r *= pow(2, N, mod)
    r %= mod
    return r
print(main())
Buggy python submission (verdict: Runtime Error):
import math
def main():
    N = int(input())
    if N % 2 == 1:
        return 0
    t = int(math.log(N, 5))
    a = 0
    for i in range(1, t+1):
        a += N // (2 * (5 ** i))
    return a
print(main())


Fixed submission:
import math
def main():
    N = int(input())
    if N < 5:
        return 0
    if N % 2 == 1:
        return 0
    t = int(math.log(N, 5))
    a = 0
    for i in range(1, t+1):
        a += N // (2 * (5 ** i))
    return a
print(main())
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N = int(input())
    A = map(int, input().split())
    l0 = [0] * 61
    l1 = [0] * 61
    for i in A:
        t = format(i, 'b').zfill(61)
        for j, v in enumerate(t):
            if v == '1':
                l1[j] += 1
            else:
                l0[j] += 1
    a = 0
    for i in range(61):
        a += ((2 ** i) * (l0[60-i] * l1[60-i])) % (10 ** 9 + 7)
    return a % (10**9 + 7)

print(main())





Fixed submission:
def main():
    N = int(input())
    A = map(int, input().split())
    l0 = [0] * 61
    l1 = [0] * 61
    for i in A:
        t = format(i, 'b').zfill(61)
        for j, v in enumerate(t):
            if v == '1':
                l1[j] += 1
            else:
                l0[j] += 1
    a = 0
    for i in range(61):
        a += ((2 ** i) * (l0[60-i] * l1[60-i])) % (10 ** 9 + 7)
    return a % (10**9 + 7)

print(main())
Buggy python submission (verdict: Runtime Error):
def main():
    N, T = map(int, input().split())
    l = []
    for _ in range(N):
        a, b = map(int, input().split())
        l.append((a,b))
    l.sort(key=lambda x: x[0])
    m = [[0] * T for _ in range(N)]
    m[0] = [0 if t < l[0][0] else l[0][1] for t in range(T)]
    for i in range(1, N):
        t, v = l[i]
        for j in range(t):
            m[i][j] = m[i-1][j]
        for j in range(t, T):
            m[i][j] = max(l[i][1] + m[i-1][j-t], m[i-1][j])
    return max(l[i][1] + m[i-1][-1] if i > 0 else l[i][1] for i in range(N))

print(main())


Fixed submission:
def main():
    N, T = map(int, input().split())
    l = []
    for _ in range(N):
        a, b = map(int, input().split())
        l.append((a,b))
    l.sort(key=lambda x: x[0])
    m = [[0] * T for _ in range(N)]
    m[0] = [0 if t < l[0][0] else l[0][1] for t in range(T)]
    for i in range(1, N):
        t, v = l[i]
        for j in range(min(t, T)):
            m[i][j] = m[i-1][j]
        for j in range(t, T):
            m[i][j] = max(l[i][1] + m[i-1][j-t], m[i-1][j])
    return max(l[i][1] + m[i-1][-1] if i > 0 else l[i][1] for i in range(N))

print(main())
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
a = int(input())
b = list(map(int, input().split()))
for i in range(1, a+1):
    d = Counter(b)
    if d.most_common(1)[0][1] == 1:
        print(a // i)
    else:
        r = 0
        while d:
            t = d.most_common(i)
            if len(t) < i:
                break
            d.subtract(Counter([k[0] for k in t]))
            if d.most_common()[-1][1] < 0:
                break
            r += 1
        print(r)


Fixed submission:
from collections import Counter
def main():
    N = int(input())
    A = list(map(int, input().split()))
    m = max(list(Counter(A).values()))
    d = Counter(Counter(A).values())
    l = []
    t = 0
    for i in range(m, 0, -1):
        t += d[i]
        l.append(t)
    l.reverse()
    t = 0
    r = []
    for i in range(N):
        if m > i:
            t += l[i]
        r.append(t//(i+1))
    p = -1
    a = []
    for i, v in enumerate(reversed(r)):
        if p != v:
            a.append((v, N-i))
        p = v
    a.append((N, 0))
    t = 0
    aa = []
    for i in range(1, N+1):
        if a[t][0] < i:
            t += 1
        aa.append(a[t][1])
    for i in aa:
        print(i)
main()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
a = int(input())
b = list(map(int, input().split()))
for i in range(1, a+1):
    d = Counter(b)
    if d.most_common(1)[0][1] == 1:
        print(a // i)
    else:
        r = 0
        while d:
            t = d.most_common(i)
            if len(t) < i:
                break
            d.subtract(Counter([k[0] for k in t]))
            if d.most_common()[-1][1] < 0:
                break
            r += 1
        print(r)


Fixed submission:
from collections import Counter
def main():
    N = int(input())
    A = list(map(int, input().split()))
    m = max(list(Counter(A).values()))
    d = Counter(Counter(A).values())
    l = []
    t = 0
    for i in range(m, 0, -1):
        t += d[i]
        l.append(t)
    l.reverse()
    t = 0
    r = []
    for i in range(N):
        if m > i:
            t += l[i]
        r.append(t//(i+1))
    p = -1
    a = []
    for i, v in enumerate(reversed(r)):
        if p != v:
            a.append((v, N-i))
        p = v
    a.append((N, 0))
    t = 0
    aa = []
    for i in range(1, N+1):
        if a[t][0] < i:
            t += 1
        aa.append(a[t][1])
    for i in aa:
        print(i)
main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N = int(input())
    S = input()
    m = 0
    for i in range(N-1):
        A = z_algo(S[i:])
        m = max(m, max(min(i,v) for i, v in enumerate(A)))
    return m

def z_algo(S):
    N = len(S)
    A = [0]*N
    i = 1; j = 0
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return A
print(main()) 


Fixed submission:
def main():
    N = int(input())
    S = input()
    m = 0
    for i in range(N-1):
        A = z_algo(S[i:])
        m = max(m, max(min(i,v) for i, v in enumerate(A)))
    return m

def z_algo(S):
    N = len(S)
    A = [0]*N
    i = 1; j = 0
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return A
print(main())
Buggy python submission (verdict: Runtime Error):
S = input()
T = input()
r = 0
for i in range(3):
	if S[i] == T[i]:
    	r += 1
print(r)

Fixed submission:
S = input()
T = input()
r = 0
for i in range(3):
    if S[i] == T[i]:
        r += 1
print(r)
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N = int(input())
    A = []
    for _ in range(N):
        a = list(map(int, input().split()))
        a = [i-1 for i in a]
        a.reverse()
        A.append(a)
    t = []
    d = 0
    n = set(range(N))
    while True:
        p = 0
        l = set()
        d += 1
        for i in n:
            if A[i] == [] or i in l:
                continue
            j = A[i][-1]
            if A[i][-1] not in l and A[j][-1] == i:
                l.add(i)
                l.add(A[i][-1])
                A[j] = A[j][:-1]
                A[i] = A[i][:-1]
                p += 1
        n = l
        if p == 0:
            print(-1)
            break
        if sum([len(i) for i in A]) == 0:
            print(d)
            break
main()


Fixed submission:
def main():
    N = int(input())
    A = []
    for _ in range(N):
        a = list(map(int, input().split()))
        a = [i-1 for i in a]
        a.reverse()
        A.append(a)
    t = N * (N - 1) / 2
    d = 0
    n = set(range(N))
    while True:
        p = 0
        l = set()
        d += 1
        for i in n:
            if A[i] == [] or i in l:
                continue
            j = A[i][-1]
            if A[i][-1] not in l and A[j][-1] == i:
                l.add(i)
                l.add(A[i][-1])
                A[j].pop() 
                A[i].pop()
                t -= 1
                p += 1
        n = l
        if t == 0:
            print(d)
            break
        if p == 0:
            print(-1)
            break
main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N = int(input())
    A = []
    for _ in range(N):
        a = list(map(int, input().split()))
        a = [i-1 for i in a]
        a.reverse()
        A.append(a)
    t = []
    d = 0
    while True:
        p = 0
        l = set()
        d += 1
        for i in range(N):
            if A[i] == [] or i in l:
                continue
            j = A[i][-1]
            if A[i][-1] not in l and A[j][-1] == i:
                l.add(i)
                l.add(A[i][-1])
                A[j] = A[j][:-1]
                A[i] = A[i][:-1]
                p += 1
        if p == 0:
            print(-1)
            break
        if sum([len(i) for i in A]) == 0:
            print(d)
            break
main()


Fixed submission:
def main():
    N = int(input())
    A = []
    for _ in range(N):
        a = list(map(int, input().split()))
        a = [i-1 for i in a]
        a.reverse()
        A.append(a)
    t = N * (N - 1) / 2
    d = 0
    n = set(range(N))
    while True:
        p = 0
        l = set()
        d += 1
        for i in n:
            if A[i] == [] or i in l:
                continue
            j = A[i][-1]
            if A[i][-1] not in l and A[j][-1] == i:
                l.add(i)
                l.add(A[i][-1])
                A[j].pop() 
                A[i].pop()
                t -= 1
                p += 1
        n = l
        if t == 0:
            print(d)
            break
        if p == 0:
            print(-1)
            break
main()
Buggy python submission (verdict: Runtime Error):
import bisect
def main():
    s = input()
    t = input()
    if not set(t).issubset(set(s)):
        return -1
    d = {}
    n = len(s)
    for i, v in enumerate(s):
        if v in d:
            d[v].append(i)
            d[v].append(i + n)
        else:
            d[v] = [i, i+n]
    m = 0
    j = 0
    for i in t:
        ind = bisect.bisect_left(d[i], j)
        m += d[i][ind] - j + 1
        if d[i][ind] > n:
            j = d[i][ind] - n + 1
        else:
            j = d[i][ind] + 1
    return m
print(main())


Fixed submission:
def main():
    s = input()
    t = input()
    if not set(t).issubset(set(s)):
        return -1
    m = 0
    st = s
    for i in t:
        if i in st:
            j = st.index(i)
            m += j + 1
            st = st[j+1:]
        else:
            m += len(st)
            st = s
            j = st.index(i)
            st = st[j+1:]
            m += j + 1
    return m
print(main())

Buggy python submission (verdict: Runtime Error):
import bisect
def main():
    s = input()
    t = input()
    if not set(t).issubset(set(s)):
        return -1
    d = {}
    n = len(s)
    for i, v in enumerate(s):
        if v in d:
            d[v].append(i)
            d[v].append(i + n)
        else:
            d[v] = [i, i+n]
    m = 1
    j = 0
    for i in t:
        ind = bisect.bisect_right(d[i], j)
        m += d[i][ind] - j
        if d[i][ind] > n:
            j = d[i][ind] - n
        else:
            j = d[i][ind]
    return m
print(main())


Fixed submission:
def main():
    s = input()
    t = input()
    if not set(t).issubset(set(s)):
        return -1
    m = 0
    st = s
    for i in t:
        if i in st:
            j = st.index(i)
            m += j + 1
            st = st[j+1:]
        else:
            m += len(st)
            st = s
            j = st.index(i)
            st = st[j+1:]
            m += j + 1
    return m
print(main())

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    s = input()
    t = input()
    if not set(t).issubset(set(s)):
        return -1
    m = 0
    st = s
    for i in t:
        if i in st:
            j = st.index(i)
            m += j + 1
            st = st[j+1:]
        else:
            m += len(st)
            st = s
            j = st.index(i)
            st = st[j+1:]
            m += j + 1
    return m
print(main())


Fixed submission:
def main():
    s = input()
    t = input()
    if not set(t).issubset(set(s)):
        return -1
    m = 0
    st = s
    for i in t:
        if i in st:
            j = st.index(i)
            m += j + 1
            st = st[j+1:]
        else:
            m += len(st)
            st = s
            j = st.index(i)
            st = st[j+1:]
            m += j + 1
    return m
print(main())