Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import sys

def main():
    input = sys.stdin.readline
    S = str(input().strip())

    if len(S) % 2 == 1:
        mid = (len(S) - 1) // 2
        for i in range(mid):
            if S[mid] != S[mid + i] or S[mid] != S[mid -i]:
                ans = mid + i
                break
    else:
        midr = len(S) // 2
        midl = midr - 1
        for i in range(midr):
            if S[midr] != S[midr + i] or S[midr] != S[midl - i]:
                ans = midr + i
                break

    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
import sys

def main():
    input = sys.stdin.readline
    S = str(input().strip())
    L = len(S)

    i = 0
    if L % 2 == 1:
        mid = (L - 1) // 2
        m = S[mid]
        while i <= mid and S[mid-i] == S[mid+i] == m:
            i += 1

        print(mid + i)
    else:
        mid =  (L - 1) // 2
        m0 = S[mid]
        m1 = S[mid+1]
        while i <= mid and S[mid-i] == S[mid+i+1] == m0 == m1:
            i += 1

        print(mid + i + 1)


if __name__ == '__main__':
    main()

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

def main():
    input = sys.stdin.readline
    S = str(input().strip())

    z = []
    o = []
    i = 0
    while i < len(S):
        j = i + 1
        while j < len(S) and S[i] == S[j]:
            j += 1
        if S[i] == '0':
            z.append(j-i)
        else:
            o.append(j-i)

        i = j

    z = sorted(z, key=lambda x: -x)
    o = sorted(o, key=lambda x: -x)

    if z[0] > o[0]:
        if len(z) > 2 and z[0] == z[1]:
            print(z[0] + 1)
        else:
            print(z[0])
    elif o[0] > z[0]:
        if len(o) > 2 and o[0] == o[1]:
            print(o[0] + 1)
        else:
            print(o[0])
    else:
        if len(z) > 2 and z[0] == z[1]:
            print(z[0] + 1)
        elif len(o) > 2 and o[0] == o[1]:
            print(o[0] + 1)
        else:
            print(o[0])


if __name__ == '__main__':
    main()


Fixed submission:
import sys

def main():
    input = sys.stdin.readline
    S = str(input().strip())
    L = len(S)

    i = 0
    if L % 2 == 1:
        mid = (L - 1) // 2
        m = S[mid]
        while i <= mid and S[mid-i] == S[mid+i] == m:
            i += 1

        print(mid + i)
    else:
        mid =  (L - 1) // 2
        m0 = S[mid]
        m1 = S[mid+1]
        while i <= mid and S[mid-i] == S[mid+i+1] == m0 == m1:
            i += 1

        print(mid + i + 1)


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

def f(pos, S, goal):
    F = 0
    while len(S) > 0 and S[0] == 'F':
        F += 1
        _ = S.pop(0)

    num_F = sum([c == 'F' for c in S])

    next_pos = set()
    for p in pos:
        x = p[0]
        y = p[1]
        if p[2] == 0:  # Forward to +x
            x += F
        elif p[2] == 1:  # Forward to +y
            y += F
        elif p[2] == 2:  # Forward to -x
            x -= F
        else:              # direct == 3, Foward to -y
            y -= F

        dist = abs(goal[0] - x) + abs(goal[1] - y)
        if num_F < dist:
            continue

        direct1 = (p[2] + 1) % 4
        direct2 = (p[2] + 3) % 4

        np1 = (x, y, direct1)
        np2 = (x, y, direct2)

        next_pos.add(np1)
        next_pos.add(np2)

    if len(next_pos) == 0:
        return False

    if len(S) == 0:
        ans = False
        for p in next_pos:
            if p[0] == goal[0] and p[1] == goal[1]:
                ans = True
                break
        return ans

    _ = S.pop(0)  # Remove 'T' at S[0]
    return f(next_pos, S, goal)


def main():
    input = sys.stdin.readline
    S = [str(c) for c in input().strip()]
    goal = list(map(int, input().split()))

    init = (0, 0, 0)
    pos = set()
    pos.add(init)

    if f(pos, S, goal):
        print('Yes')
    else:
        print('No')


if __name__ == '__main__':
    main()


Fixed submission:
import sys

def main():
    input = sys.stdin.readline
    S = [str(c) for c in input().strip()]
    X, Y = map(int, input().split())
    F = []
    while len(S) > 0:
        f = 0
        while len(S) > 0 and S[0] == 'F':
            f += 1
            S.pop(0)
        F.append(f)
        if len(S) > 0:
            S.pop(0)

    Fx = []
    Fy = []
    for i in range(1, len(F)):
        if i % 2 == 0:
            Fx.append(F[i])
        else:
            Fy.append(F[i])

    dpx = [[F[0]]] + [0] * len(Fx)
    for i in range(len(Fx)):
        nx = set()
        for a in dpx[i]:
            nx.add(a + Fx[i])
            nx.add(a - Fx[i])
        dpx[i+1] = nx

    dpy = [[0]] + [0] * len(Fy)
    for i in range(len(Fy)):
        ny = set()
        for a in dpy[i]:
            ny.add(a + Fy[i])
            ny.add(a - Fy[i])
        dpy[i+1] = ny


    if X in dpx[-1] and Y in dpy[-1]:
        print('Yes')
    else:
        print('No')


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

def lucas(n):
    if n == 0:
        return 2
    elif n == 1:
        return 1
    else:
        return lucas(n-2) + lucas(n-1)

def main():
    input = sys.stdin.readline
    N = int(input())
    print(lucas(N))


if __name__ == '__main__':
    main()


Fixed submission:
import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    if N == 0:
        print(2)
        return 0
    if N == 1:
        print(1)
        return 0

    lucas = [0] * (N+1)
    lucas[0] = 2
    lucas[1] = 1
    for i in range(2, N+1):
        lucas[i] = lucas[i-2] + lucas[i-1]

    print(lucas[N])


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

def main():
    input = sys.stdin.readline
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N)]

    INF = float('INF')
    for i in range(N):
        A[i][i] = INF

    ans = 0
    for i in range(N):
        for j in range(i):
            #bipas = min(map(sum, zip(A[i], A[j])))
            bipas = 10**10
            for k in range(N):
                bipas = min(bipas, A[i][k] + A[j][k])

            if A[i][j] > bipas:
                ans = -1
                break
            elif A[i][j] < bipas:
                ans += A[i][j]

    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
import sys
import numpy as np

def main():
    input = sys.stdin.readline
    N = int(input())
    A = np.array([list(map(int, input().split())) for i in range(N)])
    #A = [list(map(int, input().split())) for _ in range(N)]
    #A = np.array(A)

    INF = 10**10
    for i in range(N):
        A[i][i] = INF

    ans = 0
    for i in range(N):
        for j in range(i):
            #bipas = min(map(sum, zip(A[i], A[j])))
            bipas = np.min(A[i] + A[j])

            if A[i][j] > bipas:
                print(-1)
                return 0
            elif A[i][j] < bipas:
                ans += A[i][j]

    print(ans)


if __name__ == '__main__':
    main()

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

def main():
    input = sys.stdin.readline
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N)]

    INF = float('INF')
    for i in range(N):
        A[i][i] = INF

    ans = 0
    for i in range(N):
        for j in range(i):
            bipas = 10**9 + 1
            for k in range(N):
                bipas = min(bipas, A[i][k] + A[k][j])

            if A[i][j] > bipas:
                ans = -1
                break
            elif A[i][j] < bipas:
                ans += A[i][j]

    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
import sys
import numpy as np

def main():
    input = sys.stdin.readline
    N = int(input())
    A = np.array([list(map(int, input().split())) for i in range(N)])
    #A = [list(map(int, input().split())) for _ in range(N)]
    #A = np.array(A)

    INF = 10**10
    for i in range(N):
        A[i][i] = INF

    ans = 0
    for i in range(N):
        for j in range(i):
            #bipas = min(map(sum, zip(A[i], A[j])))
            bipas = np.min(A[i] + A[j])

            if A[i][j] > bipas:
                print(-1)
                return 0
            elif A[i][j] < bipas:
                ans += A[i][j]

    print(ans)


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

def main():
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))
    A = sorted(A, key=lambda x: -x)

    B = []
    C = []
    for a in A:
        if a in B:
            C.append(a)
            B.remove(a)
            if len(C) >= 2:
                break
        else:
            B.append(a)

    if len(C) < 2:
        return 0
    else:
        return C[0] * C[1]


if __name__ == '__main__':
    print(main())


Fixed submission:
import sys
from collections import defaultdict

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

    d = defaultdict(lambda: 0)
    B = []
    for a in A:
        d[a] += 1

        if d[a] % 2 == 0:
            B.append(a)


    B = sorted(B, key=lambda x: -x)
    if len(B) < 2:
        return 0
    else:
        return B[0] * B[1]


if __name__ == '__main__':
    print(main())

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

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

    B = []
    C = []
    for a in A:
        if a in B:
            C.append(a)
            B.remove(a)
        else:
            B.append(a)

    C = sorted(C, key=lambda x: -x)
    if len(C) < 2:
        return 0
    else:
        return C[0] * C[1]


if __name__ == '__main__':
    print(main())


Fixed submission:
import sys
from collections import defaultdict

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

    d = defaultdict(lambda: 0)
    B = []
    for a in A:
        d[a] += 1

        if d[a] % 2 == 0:
            B.append(a)


    B = sorted(B, key=lambda x: -x)
    if len(B) < 2:
        return 0
    else:
        return B[0] * B[1]


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

def lcm(a, b):
    return (a * b) // gcd(a, b)


def main():
    input = sys.stdin.readline
    N = int(input())
    T = [int(input()) for _ in range(N)]
    T = sorted(T)

    t = T[0]
    for i in range(N):
        if T[i] % t == 0:
            t = T[i]
        else:
            t = lcm(t, T[i])

    return t


if __name__ == '__main__':
    print(main())


Fixed submission:
import sys

def gcd(a, b):
    """Euclidean Algorithm"""
    while b != 0:
        a, b = b, a % b
    return a

def lcm(a, b):
    return (a * b) // gcd(a, b)


def main():
    input = sys.stdin.readline
    N = int(input())
    T = [int(input()) for _ in range(N)]
    T = sorted(T)

    t = T[0]
    for i in range(N):
        if T[i] % t == 0:
            t = T[i]
        else:
            t = lcm(t, T[i])

    return t


if __name__ == '__main__':
    print(main())
Buggy python submission (verdict: Runtime Error):
import sys
from collections import deque

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = [[] for _ in range(N+1)]
    for _ in range(M):
        a, b = map(int, input().split())
        A[a].append(b)
        A[b].append(a)

    q = deque()
    q.append(*A[1])

    while len(q) > 0:
        a = q.popleft()
        if N in A[a]:
            return 'POSSIBLE'

    return 'IMPOSSIBLE'





if __name__ == '__main__':
    print(main())


Fixed submission:
import sys
from collections import deque

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = [[] for _ in range(N+1)]
    for _ in range(M):
        a, b = map(int, input().split())
        A[a].append(b)
        A[b].append(a)

    q = deque()
    for a in A[1]:
        q.append(a)

    while len(q) > 0:
        a = q.popleft()
        if N in A[a]:
            return 'POSSIBLE'

    return 'IMPOSSIBLE'





if __name__ == '__main__':
    print(main())
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from itertools import product
import numpy as np

def main():
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))
    A = np.array(A)

    total = sum(A)
    ans = float('inf')
    for pos in product(range(2), repeat=N):
        if len(set(pos)) == 1:
            continue

        x = np.array(pos)
        X = np.sum(A * x)
        Y = total - X
        ans = min(ans, abs(X - Y))

    return ans


if __name__ == '__main__':
    print(main())


Fixed submission:
import sys
from itertools import accumulate

def main():
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))
    B = list(accumulate(A))

    total = sum(A)
    ans = float('inf')
    for b in B[:N-1]:
        ans = min(ans, abs((total - b) - b))

    return ans



if __name__ == '__main__':
    print(main())
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import numpy as np

def is_enough(H, A, B, T):
    H = H - (B * T)
    H = H[(H > 0)]

    cnt = 0
    diff = A - B
    for h in H:
        cnt += (h + diff - 1) // diff
        if cnt > T:
            return False

    return True


def main():
    input = sys.stdin.readline
    N, A, B = map(int, input().split())
    H = np.array([int(input()) for _ in range(N)])

    R = (H.max() + B - 1) // B
    L = (H.min() + A - 1) // A
    while R != L:
        c = (R + L) // 2
        if is_enough(H,  A, B, c):
            R = c
        else:
            L = c + 1

    return L


if __name__ == '__main__':
    print(main())


Fixed submission:
import sys

def is_enough(H, A, B, T):
    cnt = 0
    diff = A - B
    base = B * T
    for h in H:
        if h <= base:
            continue

        cnt += (h - base + diff - 1) // diff
        if cnt > T:
            return False

    return True


def main():
    input = sys.stdin.readline
    N, A, B = map(int, input().split())
    H = [int(input()) for _ in range(N)]

    R = (max(H) + B - 1) // B
    L = (min(H) + A - 1) // A
    while R != L:
        c = (R + L) // 2
        if is_enough(H,  A, B, c):
            R = c
        else:
            L = c + 1

    return L


if __name__ == '__main__':
    print(main())

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import numpy as np

def is_enough(H, A, B, T):
    H = H - (B * T)
    H = H[(H > 0)]

    cnt = 0
    diff = A - B
    for h in H:
        cnt += (h + diff - 1) // diff
        if cnt > T:
            return False

    return True


def main():
    input = sys.stdin.readline
    N, A, B = map(int, input().split())
    H = np.array([int(input()) for _ in range(N)])

    R = (H.max() + B - 1) // B
    L = 0
    while R - L > 1:
        c = (R + L) // 2
        if is_enough(H,  A, B, c):
            R = c
        else:
            L = c

    return R


if __name__ == '__main__':
    print(main())


Fixed submission:
import sys

def is_enough(H, A, B, T):
    cnt = 0
    diff = A - B
    base = B * T
    for h in H:
        if h <= base:
            continue

        cnt += (h - base + diff - 1) // diff
        if cnt > T:
            return False

    return True


def main():
    input = sys.stdin.readline
    N, A, B = map(int, input().split())
    H = [int(input()) for _ in range(N)]

    R = (max(H) + B - 1) // B
    L = (min(H) + A - 1) // A
    while R != L:
        c = (R + L) // 2
        if is_enough(H,  A, B, c):
            R = c
        else:
            L = c + 1

    return L


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

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

    if N >= M // 2:
        ans = M // 2
        S -= M // 2

        ans += S // 2

        return ans

    else:
        ans = N
        M -= 2 * N

        ans += M // 4

        return ans


if __name__ == '__main__':
    print(main())


Fixed submission:
import sys

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

    if N >= M // 2:
        ans = M // 2
        #N -= M // 2

        #ans += N // 2

        return ans

    else:
        ans = N
        M -= 2 * N

        ans += M // 4

        return ans


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

def check(S):
    even = set()
    odd = set()
    for i in range(len(S)):
        if i % 2 == 0:
            odd.add(S[i])
        else:
            even.add(S[i])

    return len(even) == len(odd) == 1


def can_checkmate(S):
    chrs = set(S)
    if len(chrs) != 3:
        return False

    for c in chrs:
        S_ = S.remove(c)
        if check(S_):
            return True

    return False


def main():
    input = sys.stdin.readline
    S = [c for c in input().strip()]

    if check(S):
        return 'Second'

    if S[0] == S[-1]:
        if len(S) % 2 == 0 or can_checkmate(S):
            return 'First'
        else:
            return 'Second'
    else:
        if len(S) % 2 == 1 or can_checkmate(S):
            return 'First'
        else:
            return 'Second'


if __name__ == '__main__':
    print(main())


Fixed submission:
import sys

def check(S):
    even = set()
    odd = set()
    for i in range(len(S)):
        if i % 2 == 0:
            odd.add(S[i])
        else:
            even.add(S[i])

    return len(even) == len(odd) == 1


def can_checkmate(S):
    chrs = set(S)
    if len(chrs) != 3:
        return False

    for c in chrs:
        S_ = S
        S_.remove(c)
        if check(S_):
            return True

    return False


def main():
    input = sys.stdin.readline
    S = [c for c in input().strip()]

    if check(S):
        return 'Second'

    if S[0] == S[-1]:
        if len(S) % 2 == 0 or can_checkmate(S):
            return 'First'

        else:
            return 'Second'
    else:
        if len(S) % 2 == 1:
            return 'First'

        else:
            return 'Second'


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

def main():
    input = sys.stdin.readline
    n = int(input())
    s = int(input())

    return ans


if __name__ == '__main__':
    print(main())


Fixed submission:
import sys
from collections import defaultdict

def main():
    input = sys.stdin.readline
    N, A = map(int, input().split())
    X = [int(c) - A for c in input().split()]
    d = defaultdict(lambda: 0)

    for x in X:
        d_ = defaultdict(lambda: 0)
        for key in d.keys():
            d_[key + x] += d[key]

        for key in d_.keys():
            d[key] += d_[key]

        d[x] += 1

    return d[0]


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

def f(b, n):
    if b > n:
        return n

    return f(b, n//b) + n % b


def main():
    input = sys.stdin.readline
    n = int(input())
    s = int(input())

    if s == n:
        return n+1

    for i in range(2, int(n**0.5)):
        if f(i, n) == s:
            return i


    for p in range(1, int(n**0.5)):
        b = (n - s) // p + 1
        if f(b, n) == s:
            return b

    return -1


if __name__ == '__main__':
    print(main())


Fixed submission:
import sys

def f(b, n):
    if b < 2:
        return -1    

    if b > n:
        return n

    return f(b, n//b) + n % b


def main():
    input = sys.stdin.readline
    n = int(input())
    s = int(input())

    if s > n:
        return -1

    if s == n:
        return n+1

    for i in range(2, int(n**0.5)):
        if f(i, n) == s:
            return i

    for p in range(int(n**0.5) + 1, 0, -1):
        if (n - s) % p != 0:
            continue

        b = (n - s) // p + 1
        if f(b, n) == s:
            return b

    return -1


if __name__ == '__main__':
    print(main())

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

def f(b, n):
    if b > n:
        return n

    return f(b, n//b) + n % b


def main():
    input = sys.stdin.readline
    n = int(input())
    s = int(input())

    if s == n:
        return n+1

    for i in range(2, int(n**0.5)):
        if f(i, n) == s:
            return i

    b = (n - s) // p + 1
    if f(b, n) == s:
        return b
    else:
        return -1


if __name__ == '__main__':
    print(main())


Fixed submission:
import sys

def f(b, n):
    if b < 2:
        return -1    

    if b > n:
        return n

    return f(b, n//b) + n % b


def main():
    input = sys.stdin.readline
    n = int(input())
    s = int(input())

    if s > n:
        return -1

    if s == n:
        return n+1

    for i in range(2, int(n**0.5)):
        if f(i, n) == s:
            return i

    for p in range(int(n**0.5) + 1, 0, -1):
        if (n - s) % p != 0:
            continue

        b = (n - s) // p + 1
        if f(b, n) == s:
            return b

    return -1


if __name__ == '__main__':
    print(main())
Buggy python submission (verdict: Runtime Error):
import sys
from itertools import product

def main():
    input = sys.stdin.readline
    N, K = map(str, input().split())
    D = list(map(str, input().split()))

    nums = set([str(i) for i in range(10)])
    safe = sorted(list(nums - set(D)))

    digit = len(str(N))
    safe_num = list(product(safe, repeat=digit))
    ans = 10**5
    for n in safe_num:
        m = int(''.join(n))
        l = int(safe[0] + ''.join(n))
        s = int(safe[1] + ''.join(n))
        if m >= int(N):
            ans = min(ans, m)

        if l >= int(N):
            ans = min(ans, l)

        if s >= int(N):
            ans = min(ans, s)

    return ans


if __name__ == '__main__':
    print(main())


Fixed submission:
import sys
from itertools import product

def main():
    input = sys.stdin.readline
    N, K = map(str, input().split())
    D = list(map(str, input().split()))

    nums = set([str(i) for i in range(10)])
    safe = sorted(list(nums - set(D)))
    min_safe = safe[0]
    if min_safe == '0':
        min_safe = safe[1]

    digit = len(str(N))
    safe_num = list(product(safe, repeat=digit))
    ans = 10**5
    for n in safe_num:
        m = int(''.join(n))
        l = int(min_safe + ''.join(n))
        if m >= int(N):
            ans = min(ans, m)

        if l >= int(N):
            ans = min(ans, l)


    return ans


if __name__ == '__main__':
    print(main())

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

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    D = list(map(int, input().split()))
    safe = list(set(range(10)) - set(D))
    safe = sorted(safe)

    n = [c for c in str(N)]
    for i in range(len(n)):
        if int(n[i]) in safe:
            continue
        
        for s in safe:
            if s > int(n[i]):
                n[i] = str(s)
                replaced = i
                break
        break

    for i in range(replaced+1, len(n)):
        n[i] = str(safe[0])

    return ''.join(n)


if __name__ == '__main__':
    print(main())


Fixed submission:
import sys
from itertools import product

def main():
    input = sys.stdin.readline
    N, K = map(str, input().split())
    D = list(map(str, input().split()))

    nums = set([str(i) for i in range(10)])
    safe = sorted(list(nums - set(D)))
    min_safe = safe[0]
    if min_safe == '0':
        min_safe = safe[1]

    digit = len(str(N))
    safe_num = list(product(safe, repeat=digit))
    ans = 10**5
    for n in safe_num:
        m = int(''.join(n))
        l = int(min_safe + ''.join(n))
        if m >= int(N):
            ans = min(ans, m)

        if l >= int(N):
            ans = min(ans, l)


    return ans


if __name__ == '__main__':
    print(main())