Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
def main():
    N, M = [int(x) for x in input().split()]
    d = dict()
    for _ in range(M):
        s, c = [int(x) for x in input().split()]
        if s in d and d[s] != c or (N!=1 and s==1 and c==0):
            print(-1)
            return
        d[s] = c
    nums = [0] * N
    for s, c in d.items():
        nums[s-1] = c
    for i in range(min(d.keys())-1):
        nums[i] = 1
        break
    ans = "".join(map(str, nums))
    print(ans)


if __name__ == '__main__':
    main()

Fixed submission:
def main():
    N, M = [int(x) for x in input().split()]
    d = dict()
    for _ in range(M):
        s, c = [int(x) for x in input().split()]
        s -= 1
        if s in d and d[s] != c:
            print(-1)
            return
        d[s] = c

    def is_ok(n) -> bool:
        t = str(n)
        if len(t) != N:
            return False
        for s, c in d.items():
            if t[s] != str(c):
                return False
        return True

    for i in range(10**N):
        if is_ok(i):
            print(i)
            return
    print(-1)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
import numpy as np


def main():
    N, M = [int(x) for x in input().split()]
    d = dict()
    for _ in range(M):
        s, c = [int(x) for x in input().split()]
        if s in d and d[s] != c or (s==1 and c==0):
            print(-1)
            return
        d[s] = c
    nums = [0] * N
    for s, c in d.items():
        nums[s-1] = c
    for i in range(min(d.keys())-1):
        nums[i] = 1
    ans = "".join(map(str, nums))
    print(ans)


if __name__ == '__main__':
    main()

Fixed submission:
def main():
    N, M = [int(x) for x in input().split()]
    d = dict()
    for _ in range(M):
        s, c = [int(x) for x in input().split()]
        s -= 1
        if s in d and d[s] != c:
            print(-1)
            return
        d[s] = c

    def is_ok(n) -> bool:
        t = str(n)
        if len(t) != N:
            return False
        for s, c in d.items():
            if t[s] != str(c):
                return False
        return True

    for i in range(10**N):
        if is_ok(i):
            print(i)
            return
    print(-1)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):

def main():
    H, N = [int(x) for x in input().split()]
    magic = [list(map(int, input().split())) for _ in range(N)]
    # print(magic)
    max_a = max(a for a, _ in magic)
    dp = [10**18 for _ in range(H + max_a)]
    dp[0] = 0

    for i in range(1, H+max_a):
        dp[i] = min([dp[i-a] + b for a, b in magic if i-a>=0], default=dp[i])

    ans = min(dp[H:H+max_a])
    print(ans)


if __name__ == '__main__':
    main()

Fixed submission:
def main():
    H, N = [int(x) for x in input().split()]
    magic = [list(map(int, input().split())) for _ in range(N)]
    # print(magic)
    max_a = max(a for a, _ in magic)
    dp = [10**18 for _ in range(H + max_a)]
    dp[0] = 0

    for i in range(1, H+max_a):
        dp[i] = min(dp[i-a] + b for a, b in magic)

    ans = min(dp[H:H+max_a])
    print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):

def main():
    H, N = [int(x) for x in input().split()]
    magic = [list(map(int, input().split())) for _ in range(N)]
    # print(magic)
    max_a = max(a for a, _ in magic)
    dp = [float("inf") for _ in range(H + max_a)]
    dp[0] = 0

    for i in range(1, H+max_a):
        dp[i] = min(dp[i-a] + b for a, b in magic)

    ans = min(dp[H:H+max_a])
    print(ans)


if __name__ == '__main__':
    main()

Fixed submission:
def main():
    H, N = [int(x) for x in input().split()]
    magic = [list(map(int, input().split())) for _ in range(N)]
    # print(magic)
    max_a = max(a for a, _ in magic)
    dp = [10**18 for _ in range(H + max_a)]
    dp[0] = 0

    for i in range(1, H+max_a):
        dp[i] = min(dp[i-a] + b for a, b in magic)

    ans = min(dp[H:H+max_a])
    print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    H, N = [int(x) for x in input().split()]
    magic = [list(map(int, input().split())) for _ in range(N)]
    # print(magic)
    max_a = max(a for a, _ in magic)
    dp = [float("inf") for _ in range(H + max_a)]
    dp[0] = 0

    for i in range(1, H+max_a):
        dp[i] = min([dp[i-a] + b for a, b in magic if i-a >= 0], default=dp[i])

    ans = min(dp[H:H+max_a])
    print(ans)


if __name__ == '__main__':
    main()

Fixed submission:
def main():
    H, N = [int(x) for x in input().split()]
    magic = [list(map(int, input().split())) for _ in range(N)]
    # print(magic)
    max_a = max(a for a, _ in magic)
    dp = [10**18 for _ in range(H + max_a)]
    dp[0] = 0

    for i in range(1, H+max_a):
        dp[i] = min(dp[i-a] + b for a, b in magic)

    ans = min(dp[H:H+max_a])
    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
import numpy as np
def lcm(a):
    from fractions import gcd
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x


def main():
    N,M=[int(x) for x in input().split()]
    a = [int(x) for x in input().split()]
    b = [x//2 for x in a]

    # l = np.lcm.reduce(b)
    l = lcm(b)
    for x in b:
        if l // x % 2 == 0:
            print(0)
            return

    ans = (M//lcm+1)//2
    print(ans)


if __name__ == '__main__':
    main()

Fixed submission:
import fractions
from functools import reduce


def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(numbers):
    return reduce(lcm_base, numbers, 1)


def main():
    N,M=[int(x) for x in input().split()]
    a = [int(x) for x in input().split()]
    b = [x//2 for x in a]

    # l = np.lcm.reduce(b)
    l = lcm(b)
    for x in b:
        if l // x % 2 == 0:
            print(0)
            return

    ans = (M//l+1)//2
    print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
import numpy as np


def main():
    N,M=[int(x) for x in input().split()]
    a = [int(x) for x in input().split()]
    b = [x//2 for x in a]

    lcm = np.lcm.reduce(b)
    for x in b:
        if lcm // x % 2 == 0:
            print(0)
            return

    ans = (M//lcm+1)//2
    print(ans)


if __name__ == '__main__':
    main()

Fixed submission:
import fractions
from functools import reduce


def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(numbers):
    return reduce(lcm_base, numbers, 1)


def main():
    N,M=[int(x) for x in input().split()]
    a = [int(x) for x in input().split()]
    b = [x//2 for x in a]

    # l = np.lcm.reduce(b)
    l = lcm(b)
    for x in b:
        if l // x % 2 == 0:
            print(0)
            return

    ans = (M//l+1)//2
    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    from itertools import permutations
    import math
    import numpy as np
    tot = 0

    N = int(input())
    locs = np.array([
        [int(x) for x in input().split()]
        for _ in range(N)
    ])

    for order in permutations(range(N)):
        d = 0
        for i in range(N-1):
            i0 = order[i]
            i1 = order[i+1]
            d += np.linalg.norm(locs[i0]-locs[i1])
        tot += d
    print(tot/math.factorial(N))


if __name__ == '__main__':
    main()

Fixed submission:
def main():
    from itertools import permutations
    import math
    import numpy as np
    tot = 0

    N = int(input())
    locs = np.array([
        [int(x) for x in input().split()]
        for _ in range(N)
    ], dtype=float)

    for order in permutations(range(N)):
        order = list(order)
        loc0 = locs[order[:-1]]
        loc1 = locs[order[1:]]
        delta = loc1 - loc0
        tot += np.sum(np.linalg.norm(delta, axis=1))
    print(tot/math.factorial(N))


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def prime_decomp(n):
    i=2
    res = []
    while n>1:
        if n%i==0:
            res.append(i)
            while n%i==0:
                n //= i
        i+=1
    return res


def main():
    from fractions import gcd
    A, B = [int(x) for x in input().split()]

    g = gcd(A, B)
    d = prime_decomp(g)
    print(len(d)+1)


if __name__ == '__main__':
    main()

Fixed submission:
def prime_factors(n: int) -> list:
    tmp = n
    i = 2
    res = []
    while i*i <= n:
        if tmp%i==0:
            res.append(i)
            while tmp%i==0:
                tmp //= i
        i += 1
    # add remaining factor
    if tmp > 1:
        res.append(tmp)
    return res


def main():
    from fractions import gcd
    A, B = [int(x) for x in input().split()]

    g = gcd(A, B)
    factors = prime_factors(g)
    print(len(factors)+1)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
import numpy as np

def f(X, C, D):
    return X - X//C - X//D + X//np.lcm(C,D)


def main():
    A, B, C, D = map(int, input().split())

    ans = f(B, C, D) - f(A-1, C, D)
    print(ans)


if __name__ == '__main__':
    main()

Fixed submission:
def gcd(x, y):
    while y != 0:
        x, y = y, x % y
    return x


def lcm(x, y):
    return x*y//gcd(x,y)


def f(X, C, D):
    return X - X//C - X//D + X//lcm(C,D)


def main():
    A, B, C, D = map(int, input().split())

    ans = f(B, C, D) - f(A-1, C, D)
    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
class UnionFindTree:
    """Tested https://atc001.contest.atcoder.jp/tasks/unionfind_a
    """

    def __init__(self, size: int):
        self.size = size

        # all are root at first
        self._par = [i for i in range(size)]

    def find(self, x: int) -> int:
        if self._par[x] == x:  # root
            return x
        else:
            self._par[x] = self.find(self._par[x])  # path compression
            return self._par[x]

    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)

    def union(self, x: int, y: int):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            self._par[x] = y


def main():
    N, M = map(int, input().split())

    tree = UnionFindTree(N)
    for _ in range(M):
        x, y, z = map(int, input().split())
        tree.union(x-1, y-1)

    for i in range(N):
        tree.find(i)
    s = set(tree._par)
    print(len(s))


if __name__ == '__main__':
    main()

Fixed submission:
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]


def main():
    N, M = map(int, input().split())

    uf = UnionFind(N)
    for _ in range(M):
        x, y, z = map(int, input().split())
        uf.union(x-1, y-1)

    for i in range(N):
        uf.find(i)
    # print(uf.par)
    s = set(uf.par)
    print(len(s))


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
import math

[N,X] = [int(x) for x in input().split()]
xs = [int(x) for x in input().split()]

xs.append(X)
xs = sorted(xs)

d = [y-x for x,y in zip(xs[:-1], xs[1:])]

ans = d[0]
for i in range(1, len(d)):
    ans = math.gcd(ans, d[i])
print(ans)


Fixed submission:
def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)


[N,X] = [int(x) for x in input().split()]
xs = [int(x) for x in input().split()]

xs.append(X)
xs = sorted(xs)

d = [y-x for x,y in zip(xs[:-1], xs[1:])]

ans = d[0]
for i in range(1, len(d)):
    ans = gcd(ans, d[i])
print(ans)
Buggy python submission (verdict: Runtime Error):
def solve():
    N = int(input())
    a = [int(x) for x in input().split()]

    import collections
    count = collections.Counter(a)

    valid = {k:v for k, v in count.items() if v >= 2}

    # print(valid)

    m = sorted(valid.keys(), reverse=True)
    a, b = m[0], m[1]

    return a*b


def main():
    print(solve())


if __name__ == '__main__':
    main()

Fixed submission:
def solve():
    N = int(input())
    a = [int(x) for x in input().split()]

    import collections
    count = collections.Counter(a)

    valid = {k: v for k, v in count.items() if v >= 2}

    # print(valid)

    m = sorted(valid.items(), reverse=True)

    if len(valid) == 0:
        return 0
    elif m[0][1] >= 4:
        return m[0][0] ** 2
    elif len(valid) >= 2:
        return m[0][0] * m[1][0]
    else:
        return 0


def main():
    print(solve())


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
X,K,D = map(int, input().split())

X = abs(X)

if X >= K*D:
    print(X - K*D)
else:
    if K%2 == 1:
        X -= D
        k -= 1
    
    x1 = X%(2*D)
    print(min(x1, (2*D-x1)))



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

X = abs(X)

if X >= K*D:
    print(X - K*D)
else:
    if K%2 == 1:
        X -= D
    
    x1 = X%(2*D)
    print(min(x1, (2*D-x1)))
Buggy python submission (verdict: Time Limit Exceeded):

def g(n):
    c = 0
    while n > 0:
        p = 0
        n2 = n
        while n2 > 0:
            if n2%2 == 1:
                p += 1

            n2 //= 2

        n %= p
        c += 1

    return c


def h(b, m):
    x = 1
    for _ in range(b):
        x = x*2%m

    return x


def f(N, X):
    b = sum(1 if x == '1' else 0 for x in X)

    Xplus = 0
    Xminus = 0

    for x in X:
        Xplus = (Xplus*2 + (1 if x == '1' else 0))%(b+1)
        
        if b > 1:
            Xminus = (Xminus*2 + (1 if x == '1' else 0))%(b-1)

    for i in range(N):
        if X[i] == '0':
            X2 = (Xplus + h(N-i-1, b+1))%(b+1)
            print(g(X2) + 1)
        elif b > 1:
            X2 = (Xminus - h(N-i-1, b-1))%(b-1)
            print(g(X2) + 1)
        else:
            print(0)


N = int(input())
X = input()
f(N, X)



Fixed submission:
def g(n):
    c = 0
    while n > 0:
        p = 0
        n2 = n
        while n2 > 0:
            if n2%2 == 1:
                p += 1

            n2 //= 2

        n %= p
        c += 1

    return c


def modPow(a, b, mod):
    x = 1
    
    while b > 0:
        if b & 1:
            x = (x*a)%mod

        a = (a**2)%mod
        b //= 2

    return x


# def h(b, m):
#     x = 1
#     for _ in range(b):
#         x = x*2%m

#     return x


def f(N, X):
    b = sum(1 if x == '1' else 0 for x in X)

    Xplus = 0
    Xminus = 0

    for x in X:
        Xplus = (Xplus*2 + (1 if x == '1' else 0))%(b+1)
        
        if b > 1:
            Xminus = (Xminus*2 + (1 if x == '1' else 0))%(b-1)

    for i in range(N):
        if X[i] == '0':
#            X2 = (Xplus + h(N-i-1, b+1))%(b+1)
            X2 = (Xplus + modPow(2, N-i-1, b+1))%(b+1)
            print(g(X2) + 1)
        elif b > 1:
#            X2 = (Xminus - h(N-i-1, b-1))%(b-1)
            X2 = (Xminus - modPow(2, N-i-1, b-1))%(b-1)
            print(g(X2) + 1)
        else:
            print(0)


N = int(input())
X = input()
f(N, X)
Buggy python submission (verdict: Runtime Error):
#  --*-coding:utf-8-*--


import math

a, b, c = map(int, input().split())

g = math.gcd(math.gcd(a,b), c)
a //= g
b //= g
c //= g

if math.sqrt(a) + math.sqrt(b)  < math.sqrt(c):
    print('Yes')
else:
    print('No')




Fixed submission:
#  --*-coding:utf-8-*--


import math

a, b, c = map(int, input().split())

if c < a + b:
    print('No')
elif 4*a*b < (c - a - b)**2:
    print('Yes')
else:
    print('No')
Buggy python submission (verdict: Runtime Error):
MAX = 10**8+1
N, M = map(int, input().split())

X = [MAX]*(2**N)
X[0] = 0

for i in range(M):
    a, b = map(int, input().split())
    k = sum(1<<(c-1) for c in map(int, input().split()))

    for j, x in enumerate(X):
        if X[j|k] > x + a:
            X[j|k] = x + a

print(X[-1] if X[-1] < MAX else -1)


Fixed submission:
#  --*-coding:utf-8-*--

def main():
    N = int(input())

    print('{:.10f}'.format(((N+1)//2)/N))


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
#  --*-coding:utf-8-*--


MOD = 998244353

def main():
    N = int(input())
    S = input()

    r,g,b = 0, 0, 0
    rg, rb, gb = 0, 0, 0
    empty=N

    x = 1
    for c in S:
        if c == 'R':
            if gb > 0:
                x = x*gb%MOD
                gb -= 1
            elif g > 0:
                x = x*g%MOD
                g -= 1
                rg += 1
            elif b > 0:
                x = x*b%MOD
                b -= 1
                rb += 1
            else:
                x = x*empty%MOD
                empty -= 1
                r += 1
        elif c == 'G':
            if rb > 0:
                x = x*rb%MOD
                rb -= 1
            elif r > 0:
                x = x*r%MOD
                r -= 1
                rg += 1
            elif b > 0:
                x = x*b%MOD
                b -= 1
                ggb += 1
            else:
                x = x*empty%MOD
                empty -= 1
                g+= 1
        else:
            if rg > 0:
                x = x*rg%MOD
                rg -= 1
            elif r > 0:
                x = x*r%MOD
                r -= 1
                rb += 1
            elif g > 0:
                x = x*g%MOD
                b -= 1
                gb += 1
            else:
                x = x*empty%MOD
                empty -= 1
                b += 1

    print(x)
                

if __name__ == '__main__':
    main()


Fixed submission:
#  --*-coding:utf-8-*--


MOD = 998244353

def main():
    N = int(input())
    S = input()

    r,g,b = 0, 0, 0
    rg, rb, gb = 0, 0, 0
    empty=N

    x = 1
    for c in S:
        if c == 'R':
            if gb > 0:
                x = x*gb%MOD
                gb -= 1
            elif g > 0:
                x = x*g%MOD
                g -= 1
                rg += 1
            elif b > 0:
                x = x*b%MOD
                b -= 1
                rb += 1
            else:
                x = x*empty%MOD
                empty -= 1
                r += 1
        elif c == 'G':
            if rb > 0:
                x = x*rb%MOD
                rb -= 1
            elif r > 0:
                x = x*r%MOD
                r -= 1
                rg += 1
            elif b > 0:
                x = x*b%MOD
                b -= 1
                gb += 1
            else:
                x = x*empty%MOD
                empty -= 1
                g+= 1
        else:
            if rg > 0:
                x = x*rg%MOD
                rg -= 1
            elif r > 0:
                x = x*r%MOD
                r -= 1
                rb += 1
            elif g > 0:
                x = x*g%MOD
                g -= 1
                gb += 1
            else:
                x = x*empty%MOD
                empty -= 1
                b += 1

    print(x)
                

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
#  --*-coding:utf-8-*--


import math

def f(a, b, c):
    return b//c - (a-1)//c


def main():
    A,B,C,D = map(int, input().split())
    
    x = B - A + 1 - f(A,B,C) - f(A, B, D) + f(A, B, C*D//math.gcd(C, D))
    print(x)





if __name__ == '__main__':
    main()


Fixed submission:
#  --*-coding:utf-8-*--


def gcd(n, m):
    while(m > 0):
        n,m = m, n%m
    
    return n


def f(a, b, c):
    return b//c - (a-1)//c


def main():
    A,B,C,D = map(int, input().split())
    
    x = B - A + 1 - f(A,B,C) - f(A, B, D) + f(A, B, C*D//gcd(C, D))
    print(x)





if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
#  --*-coding:utf-8-*--



def main():
    N = int(input())
    A = list(map(int, input().split()))

    M = 2*10**5
    X = [0]*(M+1)

    for a in A:
        X[a] += 1

    c = 0

    for i in range(17, -1, -1):
        r1 = 1<<i
        r2 = r1*2

        c2 = X[r1]//2
        c += c2
        X[r1] -= c2*2        

        for j in range(r1+1, min(r2-1, M)+1):
            j2 = r2-j

            c2 = min(X[j], X[j2])
            c += c2
            
            X[j] -= c2
            X[j2] -= c2

    print(c)



if __name__ == '__main__':
    main()


Fixed submission:
#  --*-coding:utf-8-*--



def main():
    N = int(input())
    A = list(map(int, input().split()))

    M = int(10**9)
    bitOfM = M.bit_length()

    X = {}
    Y = [set() for _ in range(bitOfM+1)]

    for a in A:
        if not a in X:
            X[a] = 1
            Y[a.bit_length()].add(a)
        else:
            X[a] += 1

    c = 0

    for i in range(bitOfM, 0, -1):
        P = 1<<(i-1)
        
        if P in X:
            c += X[P]//2

        for a in Y[i]:
            if a == P:
                continue

            a2 = 2*P - a
            if a2 in X:
                c2 = min(X[a], X[a2])
                c += c2
                X[a2] -= c2


    print(c)



if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
#  --*-coding:utf-8-*--

def f(str):
    s = {}
    s[0] = 0
    pat = 0

    bits = [2**i for i in range(26)]
    lenOfStr = len(str)

    for c in str:
        pat ^= bits[ord(c)-97]
        s[pat] = min(
            min(s.get(pat^bit, lenOfStr) + 1 for bit in bits),
            s.get(pat, lenOfStr))

    if pat == 0:
        return 1

    return s[pat]
            
str = input()
print(f(str))



Fixed submission:
#  --*-coding:utf-8-*--

def f(s):
    return 'Yes' if (s.find('AC') != -1) else 'No'

def test():
    assert f('BACD') == 'Yes'
    assert f('ABCD') == 'No'
    assert f('CABD') == 'No'
    assert f('ACACA') == 'Yes'
    assert f('XX') == 'No'


def main():
    print(f(input()))


if __name__ == '__main__':
    main()