Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
def main():
    target = int(input())
    cost = [101, 102, 103, 104, 105]
    answer = False
    for i in range(32):
        choice = bin(i)[2:].zfill(5)
        result = 0
        for j in range(5):
            result += cost[j] * int(choice[j])
        if (result % 100) % (target % 100) == 0 and result <= target:
            answer = True
            break
    print(1 if answer else 0)


if __name__ == '__main__':
    main()



Fixed submission:
def main():
    target = int(input())
    answer = False
    for i in range(1, 1001):
        if i * 100 <= target <= i * 105:
            answer = True
            break
    print(1 if answer else 0)


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


def main():
    vertex = int(input())
    tree = [[] for _ in range(vertex + 1)]
    color = [0] * (vertex + 1)
    for i in range(1, vertex):
        a, b = map(int, input().split())
        tree[a].append((b, i))
        tree[b].append((a, i))
    max_deg = 0
    root = 0
    for i in range(1, vertex):
        if max_deg < len(tree[i]):
            root = i
            max_deg = len(tree[i])
    queue = deque([root])
    while not queue == deque():
        color_list = [i for i in range(1, max_deg + 1)]
        now = queue.pop()
        for i, n in enumerate(tree[now]):
            if color[n[0]] == 0:
                color[n[0]] = color_list[0]
                queue.append(n[1])
                color_list.pop(0)
            else:
                color_list.remove(color[n[0]])
    print(max_deg)
    for c in color[2:]:
        print(c)


if __name__ == '__main__':
    main()



Fixed submission:
from collections import deque


def main():
    vertex = int(input())
    tree = [[] for _ in range(vertex + 1)]
    color = [0] * (vertex + 1)
    parent = [0] * (vertex + 1)
    order = []
    ab = []
    for i in range(vertex - 1):
        a, b = map(int, input().split())
        tree[a].append(b)
        tree[b].append(a)
        ab.append([a, b])
    queue = deque([1])

    # 木の親を決める
    while queue:
        now = queue.popleft()
        order.append(now)
        for t in tree[now]:
            if not t == parent[now]:
                parent[t] = now
                queue.append(t)

    # 色番号を割り当てる
    for ord in order:
        ng = color[ord]
        color_num = 1
        for t in tree[ord]:
            if not t == parent[ord]:
                if color_num == ng:
                    color_num += 1
                color[t] = color_num
                color_num += 1

    print(max(color))
    for a, b in ab:
        if a == parent[b]:
            print(color[b])
        else:
            print(color[a])


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
def triangle(a, b, c):
    return (a < b + c) and (b < a + c) and (c < a + b)


def main():
    N = int(input())
    ll = input().split(" ")
    ll.sort()
    ll.reverse()
    L = []
    M = []
    tmp = ''
    for l in ll:
        if tmp != l:
            L.append(int(l))
            tmp = l
        else:
            M.append(int(l))
    result = 0
    # 3辺相異なるとき
    for i in range(len(L)):
        for j in range(i + 1, len(L)):
            a = L[i]
            b = L[j]
            for k in range(j + 1, len(L)):
                c = L[k]
                if triangle(a, b, c):
                    result += 1

    # 二等辺(正三角形含む)
    tmp = False
    for i in range(len(M)):
        a = M[i]
        for j in range(i + 1, len(M)):
            b = j[i]
            if a == b and tmp:
                tmp = True
                result += 1
            elif a == b and not tmp:
                continue
            elif triangle(a, a, b):
                tmp = False
                result += 1
            else:
                continue

    print(result)


if __name__ == '__main__':
    main()

Fixed submission:
from bisect import bisect_left


def main():
    N = int(input())
    L = list(map(int, input().split(" ")))
    L.sort()
    result = 0
    for i in range(N):
        for j in range(i + 1, N):
            k = bisect_left(L, L[i] + L[j])
            result += k - j - 1
    print(result)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N = int(input())
    a = input().split(" ")
    L = []
    for i in range(N):
        L.append("")
    for i in range(N):
        L[int(a[i]) - 1] = str(i + 1)
    ans = ""
    for l in L:
        ans = ans + l + " "
    print(ans[:-1])


if __name__ == '__main__':
    main()

Fixed submission:
def main():
    N = int(input())
    A = map(int, input().split(" "))
    list = [""] * (N + 1)
    for i, a in enumerate(A, 1):
        list[a] = str(i)
    print(" ".join(list[1:]))


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N = int(input())
    a = input().split(" ")
    dict = {}
    for i in range(N):
        dict[int(a[i])] = str(i + 1)
    ans = ""
    for j in range(N):
        ans = ans + dict[j + 1] + " "
    print(ans)


if __name__ == '__main__':
    main()

Fixed submission:
def main():
    N = int(input())
    A = map(int, input().split(" "))
    list = [""] * (N + 1)
    for i, a in enumerate(A, 1):
        list[a] = str(i)
    print(" ".join(list[1:]))


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N = int(input())
    a = input().split(" ")
    list = []
    for i in range(N):
        list.append([int(a[i]), i + 1])
    list.sort()
    ans = ""
    for i in list:
        ans = ans + str(i[1]) + " "
    print(ans[:len(ans) - 1])


if __name__ == '__main__':
    main()

Fixed submission:
def main():
    N = int(input())
    A = map(int, input().split(" "))
    list = [""] * (N + 1)
    for i, a in enumerate(A, 1):
        list[a] = str(i)
    print(" ".join(list[1:]))


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N = int(input())
    a = input().split(" ")
    dict = {}
    for i in range(N):
        dict[int(a[i])] = str(i + 1)
    dict_sorted = sorted(dict.items(), key=lambda x:x[0])
    ans = ""
    for i in dict_sorted:
        ans = ans + i[1] + " "
    print(ans[:len(ans) - 1])


if __name__ == '__main__':
    main()

Fixed submission:
def main():
    N = int(input())
    A = map(int, input().split(" "))
    list = [""] * (N + 1)
    for i, a in enumerate(A, 1):
        list[a] = str(i)
    print(" ".join(list[1:]))


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N = int(input())
    a = input().split(" ")
    dict = {}
    for i in range(N):
        dict[int(a[i])] = str(i + 1)
    dict_sorted = sorted(dict.items(), key=lambda x:x[0])
    ans = ""
    for i in dict_sorted:
        ans = ans + i[1] + " "
    print(ans[:len(ans) - 1])


if __name__ == '__main__':
    main()

Fixed submission:
def main():
    N = int(input())
    A = map(int, input().split(" "))
    list = [""] * (N + 1)
    for i, a in enumerate(A, 1):
        list[a] = str(i)
    print(" ".join(list[1:]))


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


def main():
    A, B = map(int, input().split(" "))
    g = gcd(A, B)
    answer = [1]
    while not g % 2:
        g //= 2
        answer.append(2)
    i = 3
    while i * i <= g:
        if not g % i:
            g //= i
            answer.append(i)
        else:
            i += 2
    if not g == 1:
        answer.append(g)
    print(len(set(answer)))


if __name__ == '__main__':
    main()



Fixed submission:
from fractions import gcd


def main():
    A, B = map(int, input().split(" "))
    g = gcd(A, B)
    answer = [1]
    while not g % 2:
        g //= 2
        answer.append(2)
    i = 3
    while i * i <= g:
        if not g % i:
            g //= i
            answer.append(i)
        else:
            i += 2
    if not g == 1:
        answer.append(g)
    print(len(set(answer)))


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, M = map(int, input().split(" "))
    A = list(map(int, input().split(" ")))
    while M > 0:
        A.sort()
        if A[-1] == 0:
            break
        A[-1] //= 2
        M -= 1
    print(sum(A))


if __name__ == '__main__':
    main()

Fixed submission:
from heapq import heapify, heappop, heappush


def negative(str):
    return -1 * int(str)


def main():
    N, M = map(int, input().split(" "))
    A = list(map(negative, input().split(" ")))
    heapify(A)
    while M > 0:
        x = heappop(A)
        heappush(A, -1 * (-1 * x // 2))
        M -= 1
    print(sum(A) * -1)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, M = map(int, input().split(" "))
    A = list(map(int, input().split(" ")))
    while M > 0:
        A.sort()
        A[-1] //= 2
        M -= 1
    print(sum(A))


if __name__ == '__main__':
    main()

Fixed submission:
from heapq import heapify, heappop, heappush


def negative(str):
    return -1 * int(str)


def main():
    N, M = map(int, input().split(" "))
    A = list(map(negative, input().split(" ")))
    heapify(A)
    while M > 0:
        x = heappop(A)
        heappush(A, -1 * (-1 * x // 2))
        M -= 1
    print(sum(A) * -1)


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


def main():
    N = int(input())
    v = list(map(int, input().split(" ")))
    while len(v) > 1:
        v.sort()
        w = []
        if len(v) % 2 == 1:
            w.append(v[-1])
            N -= 1
        for i in range(floor(N / 2)):
            w.append((v[i * 2] + v[i * 2 + 1]) / 2)
        v = w
    print(v[0])


if __name__ == '__main__':
    main()

Fixed submission:
def main():
    N = int(input())
    v = list(map(int, input().split(" ")))
    while len(v) > 1:
        v.sort(reverse=True)
        a = v[-1]
        b = v[-2]
        v = v[:-2]
        v.append((a + b) / 2)
    print(v[0])


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


def main():
    s = input()
    t = input()
    s_all = {s: 0 for s in ascii_lowercase}
    for ss in s:
        s_all[ss] += 1
    ans = 0
    if any(s_all[tt] == 0 for tt in t):
        ans = -1
    else:
        s_ind = -1
        rest = 0
        for i in range(len(t)):
            while True:
                s_ind += 1
                if s_ind == len(s):
                    s_ind = 0
                    ans += 1
                if s[s_ind] == t[i]:
                    rest = s_ind + 1
                    break
        ans *= len(s)
        ans += rest
    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
from string import ascii_lowercase
from bisect import bisect_right, bisect_left


def main():
    s = input()
    t = input()
    len_s = len(s)
    s_all = {s: [] for s in ascii_lowercase}
    for i in range(len_s):
        s_all[s[i]].append(i + 1)
    ans = 0
    if any(s_all[tt] == [] for tt in t):
        ans = -1
    else:
        s_ind = 1
        for ss in ascii_lowercase:
            s_all[ss].sort()
        for i in range(len(t)):
            next_ind = bisect_left(s_all[t[i]], s_ind)
            if next_ind == len(s_all[t[i]]):
                ans += len_s - s_ind + 1
                ans += s_all[t[i]][0]
                s_ind = s_all[t[i]][0] + 1
            else:
                ans += s_all[t[i]][next_ind] - s_ind + 1
                s_ind = s_all[t[i]][next_ind] + 1
    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    list = []
    N = int(input())
    for i in range(0, N):
        ss = input()
        s = "".join(sorted(ss))
        list.append(s)
    result = 0
    for j in range(0, N):
        for k in range(j + 1, N):
            if list[j] == list[k]:
                result += 1
    print(result)


if __name__ == '__main__':
    main()

Fixed submission:
def main():
    N = int(input())
    dict = {}
    result = 0
    for i in range(N):
        s = "".join(sorted(input()))
        if s in dict:
            result += dict[s]
            dict[s] = dict[s] + 1
        else:
            dict[s] = 1
    print(result)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
from heapq import heappop, heapify, heappush


def main():
    n, m = map(int, input().split())
    work = [[] for _ in range(10 ** 4 + 1)]
    for _ in range(n):
        a, b = map(int, input().split())
        work[a].append(b)
    ans = 0
    q = []
    heapify(q)
    for i in range(1, m + 1):
        for w in work[i]:
            heappush(q, -w)
        if len(q) == 0:
            continue
        ans += heappop(q)
    ans *= -1
    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
from heapq import heappop, heapify, heappush


def main():
    n, m = map(int, input().split())
    work = [[] for _ in range(10 ** 5 + 1)]
    for _ in range(n):
        a, b = map(int, input().split())
        work[a].append(b)
    ans = 0
    q = []
    heapify(q)
    for i in range(1, m + 1):
        for w in work[i]:
            heappush(q, -w)
        if len(q) == 0:
            continue
        ans += heappop(q)
    ans *= -1
    print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
from heapq import heappop, heapify, heappush


def main():
    n, m = map(int, input().split())
    work = [[] for _ in range(10 ** 4 + 1)]
    for _ in range(n):
        a, b = map(int, input().split())
        work[a].append(b)
    ans = 0
    q = []
    heapify(q)
    for i in range(1, m + 1):
        for w in work[i]:
            heappush(q, -w)
        if len(q) == 0:
            continue
        print(q)
        ans += heappop(q)
    ans *= -1
    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
from heapq import heappop, heapify, heappush


def main():
    n, m = map(int, input().split())
    work = [[] for _ in range(10 ** 5 + 1)]
    for _ in range(n):
        a, b = map(int, input().split())
        work[a].append(b)
    ans = 0
    q = []
    heapify(q)
    for i in range(1, m + 1):
        for w in work[i]:
            heappush(q, -w)
        if len(q) == 0:
            continue
        ans += heappop(q)
    ans *= -1
    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    s = input()
    n = len(s)
    mod = 10 ** 9 + 7
    dp = [[0 for _ in range(13)] for _ in range(n + 1)]
    dp[0][0] = 1
    for i in range(1, n + 1):
        if s[i - 1] == "?":
            for now in range(10):
                for before in range(13):
                    ind = (now + 10 * before) % 13
                    dp[i][ind] += dp[i - 1][before]
                    dp[i][ind] %= mod
        else:
            for before in range(13):
                ind = (int(s[i - 1]) + 10 * before) % 13
                dp[i][ind] += dp[i - 1][before]
                dp[i][ind] %= mod
    print(dp[n][5])


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    s = input()
    n = len(s)
    mod = 10 ** 9 + 7
    dp = [[0 for _ in range(13)] for _ in range(n + 1)]
    dp[0][0] = 1
    for i in range(1, n + 1):
        if s[i - 1] == "?":
            for now in range(10):
                for before in range(13):
                    ind = (now + 10 * before) % 13
                    dp[i][ind] += dp[i - 1][before]
                    dp[i][ind] %= mod
        else:
            for before in range(13):
                ind = (int(s[i - 1]) + 10 * before) % 13
                dp[i][ind] += dp[i - 1][before]
                dp[i][ind] %= mod
    print(dp[n][5])


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N = int(input())
    A = []
    for i in range(N):
        A.append(int(input()))
    for j in range(N):
        a = A[j]
        A[j] = -1
        print(max(A))
        A[j] = a


if __name__ == '__main__':
    main()

Fixed submission:
def main():
    N = int(input())
    maximum = 0
    next_maximum = 0
    A = []
    for _ in range(N):
        a = int(input())
        A.append(a)
        if a > maximum:
            maximum = a
        elif a > next_maximum:
            next_maximum = a
    for b in A:
        if b == maximum:
            print(next_maximum)
        else:
            print(maximum)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n, m = map(int, input().split())
    a = sorted(list(map(int, input().split())))
    change = []
    for _ in range(m):
        b, c = map(int, input().split())
        for _ in range(b):
            change.append(c)
    change.sort(reverse=True)
    answer = 0
    for i in range(n):
        if i < len(change):
            answer += max(a[i], change[i])
        else:
            answer += a[i]
    print(answer)


if __name__ == '__main__':
    main()



Fixed submission:
def main():
    n, m = map(int, input().split())
    a = sorted(list(map(int, input().split())))
    change = []
    change_n = 0
    for _ in range(m):
        b, c = map(int, input().split())
        change.append((b, c))
        change_n += b
    change.sort(key=lambda x: x[1], reverse=True)
    answer = 0
    added = 0
    index = 0
    for i in range(n):
        if i < change_n:
            if added + change[index][0] == i:
                added = i
                index += 1
            answer += max(a[i], change[index][1])
        else:
            answer += a[i]
    print(answer)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, M = map(int, input().split(" "))
    A = list(map(int, input().split(" ")))
    for i in range(M):
        A.sort()
        b, c = map(int, input().split(" "))
        for j in range(b):
            if A[j] < c:
                A[j] = c
    print(sum(A))


if __name__ == '__main__':
    main()

Fixed submission:
def main():
    n, m = map(int, input().split())
    a = sorted(list(map(int, input().split())))
    change = []
    change_n = 0
    for _ in range(m):
        b, c = map(int, input().split())
        change.append((b, c))
        change_n += b
    change.sort(key=lambda x: x[1], reverse=True)
    answer = 0
    added = 0
    index = 0
    for i in range(n):
        if i < change_n:
            if added + change[index][0] == i:
                added = i
                index += 1
            answer += max(a[i], change[index][1])
        else:
            answer += a[i]
    print(answer)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    red_box, green_box, blue_box, target = map(int, input().split())
    answer = 0
    for i in range(target // red_box + 1):
        for j in range(target // green_box + 1):
            now_balls = red_box * i + green_box * j
            if (target - now_balls) % blue_box == 0 and target >= now_balls:
                answer += 1
    print(answer)


if __name__ == '__main__':
    main()



Fixed submission:
def main():
    red_box, green_box, blue_box, target = map(int, input().split())
    answer = 0
    for i in range(target // red_box + 1):
        for j in range(target // green_box + 1):
            now_balls = red_box * i + green_box * j
            if (target - now_balls) % blue_box == 0 and target >= now_balls:
                answer += 1
            elif target < now_balls:
                break
    print(answer)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
def main():
    N, Q = map(int, input().split(" "))
    S = input()
    result = [0] * (N + 1)
    for i in range(1, Q + 1):
        if S[i-1:i+1] == "AC":
            result[i] = result[i - 1] + 1
        else:
            result[i] = result[i - 1]
    for _ in range(Q):
        l, r = map(int, input().split(" "))
        print(result[l] - result[r - 1])


if __name__ == '__main__':
    main()

Fixed submission:
def main():
    N, Q = map(int, input().split(" "))
    S = input()
    result = [0] * (N + 1)
    for i in range(1, N + 1):
        if S[i-1:i+1] == "AC":
            result[i] = result[i - 1] + 1
        else:
            result[i] = result[i - 1]
    for _ in range(Q):
        l, r = map(int, input().split(" "))
        print(result[r - 1] - result[l - 1])


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, Q = map(int, input().split(" "))
    S = input()
    for _ in range(Q):
        l, r = map(int, input().split(" "))
        print(S[l-1:r].count("AC"))


if __name__ == '__main__':
    main()

Fixed submission:
def main():
    N, Q = map(int, input().split(" "))
    S = input()
    result = [0] * (N + 1)
    for i in range(1, N + 1):
        if S[i-1:i+1] == "AC":
            result[i] = result[i - 1] + 1
        else:
            result[i] = result[i - 1]
    for _ in range(Q):
        l, r = map(int, input().split(" "))
        print(result[r - 1] - result[l - 1])


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, Q = map(int, input().split(" "))
    S = input()
    for _ in range(Q):
        l, r = map(int, input().split(" "))
        print(S[l-1:r].count("AC"))


if __name__ == '__main__':
    main()

Fixed submission:
def main():
    N, Q = map(int, input().split(" "))
    S = input()
    result = [0] * (N + 1)
    for i in range(1, N + 1):
        if S[i-1:i+1] == "AC":
            result[i] = result[i - 1] + 1
        else:
            result[i] = result[i - 1]
    for _ in range(Q):
        l, r = map(int, input().split(" "))
        print(result[r - 1] - result[l - 1])


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    S = input()
    lengh_S = len(S)
    while True:
        if "01" in S or "10" in S:
            S = S.replace("01", "").replace("10", "")
        else:
            break
    print(lengh_S - len(S))


if __name__ == '__main__':
    main()

Fixed submission:
def main():
    S = input()
    print(min(S.count("0"), S.count("1")) * 2)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    S = input()
    lengh_S = len(S)
    while True:
        if "01" in S or "10" in S:
            S = S.replace("01", "").replace("10", "")
        else:
            break
    print(lengh_S - len(S))


if __name__ == '__main__':
    main()

Fixed submission:
def main():
    S = input()
    print(min(S.count("0"), S.count("1")) * 2)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
# 解説読んでやり方理解した
from math import gcd
from functools import reduce


def get_gcd(numbers):
    return reduce(gcd, numbers)


def main():
    N = int(input())
    monsters = list(map(int, input().split(" ")))
    print(get_gcd(monsters))


if __name__ == '__main__':
    main()

Fixed submission:
# 解説読んでやり方理解した
from fractions import gcd
from functools import reduce


def get_gcd(numbers):
    return reduce(gcd, numbers)


def main():
    N = int(input())
    monsters = list(map(int, input().split(" ")))
    print(get_gcd(monsters))


if __name__ == '__main__':
    main()