Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
def solve(H, W, field):
    ret = []
    operated = set()
    for y in range(0, H):
        for x in range(0, W):
            if field[y][x] % 2 == 0:
                continue
            else:
                for (xi, yi) in [(x + 1, y), (x, y + 1)]:
                    if 0 <= xi < W and 0 <= yi < H:
                        ret.append(" ".join([str(y + 1), str(x + 1), str(yi + 1), str(xi + 1)]))
                    field[yi][xi] += 1
                    field[y][x] -= 1
                    break
    return [len(ret)] + ret

if __name__ == "__main__":
    l = input()
    H, W = int(l.split()[0]), int(l.split()[1])
    field = [[int(c) for c in input().split(" ")] for _ in range(0, H)]
    [print(l) for l in solve(H, W, field)]


Fixed submission:
def solve(H, W, field):
    ret = []
    for y in range(0, H):
        for x in range(0, W):
            if field[y][x] % 2 == 1:
                for (xi, yi) in [(x + 1, y), (x, y + 1)]:
                    if 0 <= xi < W and 0 <= yi < H:
                            ret.append(" ".join([str(y + 1), str(x + 1), str(yi + 1), str(xi + 1)]))
                            field[y][x] -= 1
                            field[yi][xi] += 1
                            break
    return [len(ret)] + ret


if __name__ == "__main__":
    l = input()
    H, W = int(l.split()[0]), int(l.split()[1])
    field = [[int(c) for c in input().split(" ")] for _ in range(0, H)]
    [print(l) for l in solve(H, W, field)]

Buggy python submission (verdict: Runtime Error):
def solve(H, W, field):
    ret = []
    operated = set()
    for y in range(0, H):
        for x in range(0, W):
            if field[y][x] % 2 == 0:
                continue
            else:
                for (xi, yi) in [(x + 1, y), (x, y + 1)]:
                    if 0 <= xi < W and 0 <= yi < H:
	                    ret.append(" ".join([str(y + 1), str(x + 1), str(yi + 1), str(xi + 1)]))
                        field[yi][xi] += 1
                        field[y][x] -= 1
                        break
 
    return [len(ret)] + ret

Fixed submission:
def solve(H, W, field):
    ret = []
    for y in range(0, H):
        for x in range(0, W):
            if field[y][x] % 2 == 1:
                for (xi, yi) in [(x + 1, y), (x, y + 1)]:
                    if 0 <= xi < W and 0 <= yi < H:
                            ret.append(" ".join([str(y + 1), str(x + 1), str(yi + 1), str(xi + 1)]))
                            field[y][x] -= 1
                            field[yi][xi] += 1
                            break
    return [len(ret)] + ret


if __name__ == "__main__":
    l = input()
    H, W = int(l.split()[0]), int(l.split()[1])
    field = [[int(c) for c in input().split(" ")] for _ in range(0, H)]
    [print(l) for l in solve(H, W, field)]
Buggy python submission (verdict: Runtime Error):
def solve(N, K):
    ans = 0
    k = len([n for n in range(1, N + 1) if n % K == 0])
    ans += k * k * k
    if K % 2 == 0:
        k = len([n for n in range(1, N + 1) if n % K == K // 2])
        ans += k * k * k

    return ans

if __name__ == "__main__":
    N, K = tuple(map(int, input(" ")))
    print(solve(N, K))


Fixed submission:
def solve(N, K):
    ans = 0
    k = len([n for n in range(1, N + 1) if n % K == 0])
    ans += k * k * k
    if K % 2 == 0:
        k = len([n for n in range(1, N + 1) if n % K == K // 2])
        ans += k * k * k

    return ans

if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    print(solve(N, K))
Buggy python submission (verdict: Time Limit Exceeded):
def solve(N, K, Xs):
    plus = sorted([x for x in Xs if x >= 0])
    minus = sorted([abs(x) for x in Xs if x < 0])
    ans = 10 ** 9
    for i in range(0, max(K, len(plus)) + 1):
        ps = plus[:i]
        ms = minus[:K - i]
        if len(ps) == K:
            ans = min(ans, ps[-1])
            continue
        if len(ms) == K:
            ans = min(ans, ms[-1])
            continue
        if len(ps) + len(ms) == K:
            p, m = ps[-1], ms[-1]
            ans = min(ans, p * 2 + m, m * 2 + p)

    return ans
  
if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    Xs = list(map(int, input().split(" ")))
    print(solve(N, K, Xs))


Fixed submission:
def solve(N, K, Xs):
    plus = sorted([x for x in Xs if x >= 0])
    minus = sorted([abs(x) for x in Xs if x < 0])
    ans = 10 ** 9
    for i in range(0, K + 1):
        j = K - i
        if i <= len(plus) and i == K:
            p = plus[i-1]
            ans = min(ans, p)
        elif j <= len(minus) and j == K:
            m = minus[j-1]
            ans = min(ans, m)
        elif i <= len(plus) and j <= len(minus):
            p = plus[i - 1]
            m = minus[j - 1]
            ans = min(ans, p * 2 + m, m * 2 + p)

    return ans
  
if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    Xs = list(map(int, input().split(" ")))
    print(solve(N, K, Xs))
Buggy python submission (verdict: Runtime Error):
def solve(N, As):
    def f(n):
        c = 0
        while n % 2 == 0:
            c += 1
            n //= 2
        return c
    return sum([f(a) for a in As])


if __name__ == "__main__":
    N = int(input())
    As = list(map(int, input().split(" ")))
    print(solve(N))


Fixed submission:
def solve(N, As):
    def f(n):
        c = 0
        while n % 2 == 0:
            c += 1
            n //= 2
        return c
    return sum([f(a) for a in As])


if __name__ == "__main__":
    N = int(input())
    As = list(map(int, input().split(" ")))
    print(solve(N, As))
Buggy python submission (verdict: Time Limit Exceeded):
def solve(N, As, Bs, Cs):
    # print(As, Bs, Cs)
    ans = 0
    As.sort()
    Bs.sort()
    Cs.sort()
    
    memo = {}
    for b in Bs:
        bans = 0
        for i, c in enumerate(Cs):
            if b < c:
                bans += N - i
                break
        memo[b] = bans

    for a in As:
        for b in Bs:
            if b > a and b in memo:
                ans += memo[b]

    return ans

if __name__ == "__main__":
    N = int(input())
    As = list(map(int, input().split(" ")))
    Bs = list(map(int, input().split(" ")))
    Cs = list(map(int, input().split(" ")))
    print(solve(N, As, Bs, Cs))


Fixed submission:
import bisect
N = int(input())
A = list(map(int, input().split(" ")))
B = list(map(int, input().split(" ")))
C = list(map(int, input().split(" ")))
A.sort()
B.sort()
C.sort()

ans = 0
for b in B:
    i = bisect.bisect_left(A, b)
    j = bisect.bisect_right(C, b)
    ans += i * (N - j)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
def solve(N, As, Bs, Cs):
    # print(As, Bs, Cs)
    ans = 0
    As.sort()
    Bs.sort()
    Cs.sort()
    memo = {}
    for a in As:
        for b in Bs:
            if b <= a:
                continue
            if b in memo:
                ans += memo[b]
                continue
            bans = 0
            for i, c in enumerate(Cs):
                if b < c:
                    bans += N - i
                    break
            memo[b] = bans
            ans += bans
    return ans


if __name__ == "__main__":
    N = int(input())
    As = list(map(int, input().split(" ")))
    Bs = list(map(int, input().split(" ")))
    Cs = list(map(int, input().split(" ")))
    print(solve(N, As, Bs, Cs))


Fixed submission:
import bisect
N = int(input())
A = list(map(int, input().split(" ")))
B = list(map(int, input().split(" ")))
C = list(map(int, input().split(" ")))
A.sort()
B.sort()
C.sort()

ans = 0
for b in B:
    i = bisect.bisect_left(A, b)
    j = bisect.bisect_right(C, b)
    ans += i * (N - j)
print(ans)
Buggy python submission (verdict: Runtime Error):
def solve(N, M, ABs):
    ans = 0
    for i in range(M):
        m = {j: j for j in range(M)}
        for k, (a, b) in enumerate(ABs):
            a -= 1
            b -= 1
            if k == i:
                continue
            d = min(m[a], m[b])
            for mk in m:
                if m[mk] == m[a] or m[mk] == m[b]:
                    m[mk] = d
        if len(set(m.values())) != 1:
            ans += 1
    return ans

if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    ABs = [tuple(map(int, input().split(" "))) for _ in range(M)]
    print(solve(N, M, ABs))


Fixed submission:
def solve(N, M, ABs):
    ans = 0
    for i in range(M):
        adjMat = [[0 for _ in range(N)] for _ in range(N)]
        for k, (a, b) in enumerate(ABs):
            if k != i:
                adjMat[a - 1][b - 1] = 1
                adjMat[b - 1][a - 1] = 1

        def dps(a, visited):
            n = [i for i, b in enumerate(adjMat[a]) if b == 1]
            for nn in n:
                if nn not in visited:
                    visited.append(nn)
                    dps(nn, visited)
            return visited

        visited = dps(0, [])
        if len(visited) != N:
            ans += 1
    return ans


if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    ABs = [tuple(map(int, input().split(" "))) for _ in range(M)]
    print(solve(N, M, ABs))
Buggy python submission (verdict: Time Limit Exceeded):
def factor(N):
    ret = []
    i = 2
    while N > 1:
        if N % i == 0:
            ret.append(i)
            N //= i
        else:
            i += 1
    return ret


from collections import Counter


def solve(N, K, As):
    if K > max(As):
        return "IMPOSSIBLE"

    factors = [Counter(factor(a)) for a in As]
    iter = factors[0]
    for f in factors[1:]:
        for k, v in iter.items():
            if k not in f:
                iter[k] = 0
            else:
                iter[k] = min(v, f[k])

    if all([v == 0 for v in iter.values()]):
        return "POSSIBLE"
    else:
        d = 1
        for k, v in iter.items():
            if v != 0:
                d *= k ** v
        if K % d == 0:
            return "POSSIBLE"
    return "IMPOSSIBLE"

if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    As = list(map(int, input().split(" ")))
    print(solve(N, K, As))


Fixed submission:
def factor(N):
    ret = []
    i = 2
    while N > 1:
        if N % i == 0:
            ret.append(i)
            N //= i
        else:
            i += 1
    return ret


assert (factor(4) == [2, 2])
assert (factor(2) == [2])
assert (factor(3) == [3])
assert (factor(10) == [2, 5])

from collections import Counter


def solve(N, K, As):
    if K > max(As):
        return "IMPOSSIBLE"
    iter = Counter(factor(min(As)))
    for a in As:
        for k, v in iter.items():
            if a % k != 0:
                iter[k] = 0
            else:
                count = 0
                kk = k
                while a % kk == 0:
                    kk *= k
                    count += 1
                iter[k] = min(v, count)

    if all([v == 0 for v in iter.values()]):
        return "POSSIBLE"
    else:
        d = 1
        for k, v in iter.items():
            if v != 0:
                d *= k ** v
        if K % d == 0:
            return "POSSIBLE"
    return "IMPOSSIBLE"


if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    As = list(map(int, input().split(" ")))
    print(solve(N, K, As))
Buggy python submission (verdict: Runtime Error):
def solve(N, As):
    colors = set()
    allcount = 0
    for a in As:
        if a // 400 < 8:
            colors.add(n)
        else:
            allcount += 1
    return max(len(colors), 1), len(colors) + allcount


if __name__ == "__main__":
    N = int(input())
    As = map(int, input().split(" "))
    m1, m2 = solve(N, As)
    print(m1, m2)


Fixed submission:
def solve(N, As):
    colors = set()
    allcount = 0
    for a in As:
        a -= a % 400
        n = a // 400
        if n < 8:
            colors.add(n)
        else:
            allcount += 1
    return max(len(colors), 1), len(colors) + allcount


if __name__ == "__main__":
    N = int(input())
    As = map(int, input().split(" "))
    m1, m2 = solve(N, As)
    print(m1, m2)
Buggy python submission (verdict: Time Limit Exceeded):

def solve(N, W, WVs):
    Ws = {}
    # print(N, ",", W, ",", WVs)
    for w, v in WVs:
        Ws.setdefault(w, []).append(v)
    for w, v in Ws.items():
        Ws[w] = sorted(v, key=lambda x: -x)
    wkeys = sorted(Ws.keys())

    m = 0
    for n1 in range(N + 1):
        w1 = n1 * wkeys[0]
        v1 = sum(Ws[wkeys[0]][:n1])
        if w1 > W:
            break
        for n2 in range(N - n1 + 1):
            if len(wkeys) >= 2:
                w2 = n2 * wkeys[1]
                v2 = sum(Ws[wkeys[1]][:n2])
            else:
                w2, v2 = 0, 0
            if w1 + w2 > W:
                break
            for n3 in range(N - n1 - n2 + 1):
                if len(wkeys) >= 3:
                    w3 = n3 * wkeys[2]
                    v3 = sum(Ws[wkeys[2]][:n3])
                else:
                    w3, v3 = 0, 0
                if w1 + w2 + w3 > W:
                    break
                for n4 in range(N - n1 - n2 - n3 + 1):
                    if len(wkeys) >= 4:
                        w4 = n4 * wkeys[3]
                        v4 = sum(Ws[wkeys[3]][:n4])
                    else:
                        w4, v4 = 0, 0

                    if w1 + w2 + w3 + w4 > W:
                        break
                    m = max(m, v1 + v2 + v3 + v4)

    return m


if __name__ == "__main__":
    N, W = map(int, input().split(" "))
    WVs = [tuple(map(int, input().split(" "))) for _ in range(N)]
    print(solve(N, W, WVs))


Fixed submission:
def solve(N, W, WVs):
    Ws = {}
    for w, v in WVs:
        Ws.setdefault(w, []).append(v)
    for w, v in Ws.items():
        Ws[w] = sorted(v, key=lambda x: -x)
    wkeys = sorted(Ws.keys())

    m = 0
    for n1 in range(N + 1):
        w1 = n1 * wkeys[0]
        if w1 > W:
            break
        v1 = sum(Ws[wkeys[0]][:n1])
        for n2 in range(N - n1 + 1):
            if len(wkeys) >= 2:
                w2 = n2 * wkeys[1]
                if w1 + w2 > W:
                    break
                v2 = sum(Ws[wkeys[1]][:n2])
            else:
                w2, v2 = 0, 0
            for n3 in range(N - n1 - n2 + 1):
                if len(wkeys) >= 3:
                    w3 = n3 * wkeys[2]
                    if w1 + w2 + w3 > W:
                        break
                    v3 = sum(Ws[wkeys[2]][:n3])
                else:
                    w3, v3 = 0, 0
                for n4 in range(N - n1 - n2 - n3 + 1):
                    if len(wkeys) >= 4:
                        w4 = n4 * wkeys[3]
                        if w1 + w2 + w3 + w4 > W:
                            break
                        v4 = sum(Ws[wkeys[3]][:n4])
                    else:
                        w4, v4 = 0, 0

                    m = max(m, v1 + v2 + v3 + v4)

    return m

if __name__ == "__main__":
    N, W = map(int, input().split(" "))
    WVs = [tuple(map(int, input().split(" "))) for _ in range(N)]
    print(solve(N, W, WVs))
Buggy python submission (verdict: Time Limit Exceeded):
indexes = []


def dfs(Ds, s, e, v=None):
    if e - s == 1:
        if v == Ds[s]:
            indexes.append((s, e))
        return Ds[s]
    else:
        center = (s + e) // 2
        left = dfs(Ds, s, center, v=v)
        right = dfs(Ds, center, e, v=v)

        left_m = - (10 ** 9)
        li = -1
        for i in range(s, center):
            su = sum(Ds[i:center])
            if left_m != max(left_m, su):
                left_m = max(left_m, su)
                li = i

        right_m = -(10 ** 9)
        ri = -1
        for i in range(center + 1, e + 1):
            su = sum(Ds[center:i])
            if right_m != max(right_m, su):
                right_m = max(right_m, su)
                ri = i

        if left_m + right_m == v:
            indexes.append((li, ri))

        m = max(left, right, left_m + right_m)
        return m

def solve(N, T, As):
    Ds = [As[i + 1] - As[i] for i in range(N - 1)]
    max_v = dfs(Ds, 0, N - 1)
    dfs(Ds, 0, N - 1, v=max_v)
    return len(indexes)

if __name__ == "__main__":
    N, T = map(int, input().split(" "))
    As = list(map(int, input().split(" ")))
    print(solve(N, T, As))


Fixed submission:
indexes = []


def dfs(Ds, s, e, v=None):
    if e - s == 1:
        if v == Ds[s]:
            indexes.append((s, e))
        return Ds[s]
    else:
        center = (s + e) // 2
        left = dfs(Ds, s, center, v=v)
        right = dfs(Ds, center, e, v=v)

        left_m = - (10 ** 9)
        li = -1
        su = 0
        for i in range(center-1, s-1, -1):
            su += Ds[i]
            if left_m != max(left_m, su):
                left_m = max(left_m, su)
                li = i

        right_m = -(10 ** 9)
        ri = -1
        su = 0
        for i in range(center, e):
            su += Ds[i]
            if right_m != max(right_m, su):
                right_m = max(right_m, su)
                ri = i

        if left_m + right_m == v:
            indexes.append((li, ri))

        m = max(left, right, left_m + right_m)
        return m


def solve(N, T, As):
    Ds = [As[i + 1] - As[i] for i in range(N - 1)]
    max_v = dfs(Ds, 0, N - 1)
    dfs(Ds, 0, N - 1, v=max_v)
    return len(indexes)


if __name__ == "__main__":
    N, T = map(int, input().split(" "))
    As = list(map(int, input().split(" ")))
    print(solve(N, T, As))
Buggy python submission (verdict: Time Limit Exceeded):
def solve(N, TAs):
    T, A = 1, 1
    for t, a in TAs:
        m = (t * A) % a
        y = 0
        while True:
            if (m + (y * t)) % a == 0 and (t * A + t * y) // a >= T:
                break
            y += 1
        x = (t * A + t * y) // a - T

        T += x
        A += y
    return T + A

#        T + x : A + y = t : a
#       <=> t * A + y * t = a * T + x * a
#       <=> x =  (t * A + y * t) / a -  T => 整数
# 　　　<=> y =  (a * T + x * a) / t -  A => 整数
# 以下二つが両方とも整数
# (a * T + x * a) / t
# (t * A + y * t) / a
#  t - (a * T mod t) = (x * a) mod t

if __name__ == "__main__":
    N = int(input())
    TAs = [(tuple)(map(int, input().split(" "))) for l in range(N)]
    print(solve(N, TAs))


Fixed submission:
def solve(N, TAs):
    T, A = 1, 1
    for t, a in TAs:
        m = (t * A) % a
        y = max(0, (T * a - t * A) // t)
        while True:
            if (m + (y * t)) % a == 0:
                break
            y += 1
        x = (t * A + t * y) // a - T

        T += x
        A += y
    return T + A


#        T + x : A + y = t : a
#       <=> t * A + y * t = a * T + x * a
#       <=> x =  (t * A + y * t) / a -  T => 整数
# 　　　<=> y =  (a * T + x * a) / t -  A => 整数
# 以下二つが両方とも整数
# (a * T + x * a) / t
# (t * A + y * t) / a
#  t - (a * T mod t) = (x * a) mod t

if __name__ == "__main__":
    N = int(input())
    TAs = [(tuple)(map(int, input().split(" "))) for l in range(N)]
    print(solve(N, TAs))
Buggy python submission (verdict: Runtime Error):
import itertools
import numpy as np
import fractions
from functools import reduce

N = int(input())
A = np.array(input().split()).astype(int)

def gcd(numbers):
    return reduce(fractions.gcd, numbers)
rt = 1
for i in range(N):
    ind = np.ones(N, dtype=bool)
    ind[i]=False
    A_tmp = A[ind]
    f = gcd(A_tmp)
    if rt < f:
        rt = f
print(rt)


Fixed submission:
A, B, T = map(int, input().split())
print((T//A)*B)
Buggy python submission (verdict: Time Limit Exceeded):
N_M = [int(x.strip()) for x in input().split()]
price_maxnum_list = [[int(i) for i in input().split()] for i in range(0, N_M [0])]
price_list = [i[0] for i in price_maxnum_list]
maxnum_list = [i[1] for i in price_maxnum_list]
if len(set(price_list)) ==1:
    print(price_list[0]*N_M[1])
else:
    total = 0
    nokori = N_M[1]
    while nokori > 0:
        ind = price_list.index(min(price_list))
        total += min(price_list) * min(maxnum_list[ind], nokori)
        nokori -= min(maxnum_list[ind], nokori)
        price_list.pop(ind)
        maxnum_list.pop(ind)
    print(total)

Fixed submission:
N_M = [int(x.strip()) for x in input().split()]
price_l = [[int(i) for i in input().split()] for i in range(0, N_M[0])]
price_l.sort(key=lambda x: x[0])
total = 0
remain = N_M[1]
while remain > 0:
    if len(price_l)<1:
        break
    price_n = price_l.pop(0)
    total += price_n[0] * min(price_n[1], remain)
    remain -= min(price_n[1], remain)
print(total)
Buggy python submission (verdict: Runtime Error):
A_B_C = [int(x.strip()) for x in input().split()]
print(A_B_C = [int(x.strip()) for x in input().split()])

Fixed submission:
A_B_C = [int(x.strip()) for x in input().split()]
print(min(int(A_B_C[1]/A_B_C[0]), A_B_C[2]))
Buggy python submission (verdict: Runtime Error):
A,B,K=map(int,input().split())
 l = []
for i in reversed(range(0, min(A, B)+1)):
    if (A%i==0)&(B%i==0):
        l.append(i)
    if len(l)==K:
        break        
print(l[-1])

Fixed submission:
A,B,K=map(int,input().split())
l = []
for i in reversed(range(0, min(A, B)+1)):
    if (A%i==0)&(B%i==0):
        l.append(i)
    if len(l)==K:
        break        
print(l[-1])
Buggy python submission (verdict: Time Limit Exceeded):
S=input()
count = 0
while S.find('01')!=-1:
    S_list=list(S)
    i_pop = S.find('01')
    S_list.pop(i_pop)
    S_list.pop(i_pop)
    S = ''.join(S_list)
    count +=2
while S.find('10')!=-1:
    S_list=list(S)
    i_pop = S.find('10')
    S_list.pop(i_pop)
    S_list.pop(i_pop)
    S = ''.join(S_list)
    count +=2
print(count)

Fixed submission:
S = input()
n_zero = 0
n_one = 0
for i in S:
    if i == '0':
        n_zero += 1
    else:
        n_one += 1
print(min(n_one, n_zero)*2)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
N, M = map(int,input().split())
target_list = np.array([int(i) for i in input().split()])
if N>M:
    print(0)
else:
    target_list = np.sort(target_list)
    diff_list = target_list[1:] - target_list[:-1]
    for i in range(0, N-1):
        diff_list = np.delete(diff_list, np.argmax(diff_list))
    print(np.sum(diff_list))

Fixed submission:
import numpy as np
N, M = map(int,input().split())
target_list = np.array([int(i) for i in input().split()])
if N > M:
    print(0)
else:
    target_list = np.sort(target_list)
    diff_list = target_list[1:] - target_list[:-1]
    diff_list = np.sort(diff_list)
    if N > 1:
        diff_list = diff_list[0:-(N-1)]
    print(np.sum(diff_list))
Buggy python submission (verdict: Runtime Error):
target_list = []
for a, b, c in zip(A, B, C):
    if a==b and b==c:
        target_list.append(3)
    elif a==b or a==c:
        target_list.append(2)
    else:
        target_list.append(1)
print(N*3 - sum(target_list))

Fixed submission:
N = int(input())
A = input()
B = input()
C = input()
target_list = []
for a, b, c in zip(A, B, C):
    if a==b and b==c and c==a:
        target_list.append(3)
    elif a==b or b==c or c==a: 
        target_list.append(2)
    else:
        target_list.append(1)
print(N*3 - sum(target_list))