Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import math
from functools import lru_cache

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


@lru_cache(maxsize=None)
def solve(x, y):
    return math.gcd(x, y)


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

    ans = 0
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            for k in range(1, N + 1):
                x = [i, j, k]
                x.sort()
                xx = solve(x[0], x[1])
                if xx > x[2]:
                    ans += solve(x[2], xx)
                else:
                    ans += solve(xx, x[2])

    print(ans)

if __name__ == '__main__':
    main()


Fixed submission:
import sys
import math
from functools import lru_cache

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


@lru_cache(maxsize=None)
def solve(x, y):
    return math.gcd(x, y)


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

    ans = 0
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            x = math.gcd(i, j)
            for k in range(1, N + 1):
                ans += math.gcd(x, k)

    print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import math
from functools import lru_cache

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline

@lru_cache(maxsize=None)
def solve(x, y, z):
    x2 = math.gcd(x, y)
    return math.gcd(x2, z)

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

    ans = 0
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            for k in range(1, N + 1):
                x = [i, j, k]
                x.sort()
                ans += solve(x[0], x[1], x[2])

    print(ans)



if __name__ == '__main__':
    main()


Fixed submission:
import sys
import math
from functools import lru_cache

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


@lru_cache(maxsize=None)
def solve(x, y):
    return math.gcd(x, y)


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

    ans = 0
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            x = math.gcd(i, j)
            for k in range(1, N + 1):
                ans += math.gcd(x, k)

    print(ans)


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

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N, X, Y = [int(x) for x in input().split()]

    ans = [0] * N
    for i in range(1, N + 1):
        s = collections.deque()
        s.append([i, 0])
        v = set()
        v.add(i)
        while s:
            c = s.popleft()
            ans[c[1]] += 1

            if c[0] == X:
                if Y not in v:
                    s.append([Y, c[1] + 1])
                    v.add(Y)
            if c[0] == Y:
                if X not in v:
                    s.append([X, c[1] + 1])
                    v.add(X)

            if c[0] != 1:
                if c[0] - 1 not in v:
                    s.append([c[0] - 1, c[1] + 1])
                    v.add(c[0] - 1)

            if c[0] != N:
                if c[0] + 1 not in v:
                    s.append([c[0] + 1, c[1] + 1])
                    v.add(c[0] + 1)

    for a in ans[1:]:
        print(a // 2)


if __name__ == '__main__':
    main()


Fixed submission:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N, X, Y = [int(x) for x in input().split()]

    ans = [0] * N
    for i in range(1, N + 1):
        s = collections.deque()
        s.append([i, 0])
        v = set()
        v.add(i)
        while s:
            c = s.popleft()
            ans[c[1]] += 1

            if c[0] == X:
                if Y not in v:
                    s.append([Y, c[1] + 1])
                    v.add(Y)
            if c[0] == Y:
                if X not in v:
                    s.append([X, c[1] + 1])
                    v.add(X)

            if c[0] != 1:
                if c[0] - 1 not in v:
                    s.append([c[0] - 1, c[1] + 1])
                    v.add(c[0] - 1)

            if c[0] != N:
                if c[0] + 1 not in v:
                    s.append([c[0] + 1, c[1] + 1])
                    v.add(c[0] + 1)

    for a in ans[1:]:
        print(a // 2)


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

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    X, Y, A, B, C = [int(x) for x in input().split()]
    P = [int(x) for x in input().split()]
    Q = [int(x) for x in input().split()]
    R = [int(x) for x in input().split()]

    P.sort(reverse=True)
    Q.sort(reverse=True)
    R.sort(reverse=True)

    xcnt = 0
    ycnt = 0
    rcnt = 0
    ans = 0
    while rcnt < C:
        r = R[rcnt]
        p = float("inf")
        if X - 1 - xcnt >= 0:
            p = P[X - 1 - xcnt]
        q = float("inf")
        if Y - 1 - ycnt >= 0:
            q = Q[Y - 1 - ycnt]
        if p >= r and q >= r:
            break

        if (r - p) > 0 and r - p > r - q:
            xcnt += 1
            rcnt += 1
            ans += r
        elif (r - q) > 0 and r - q > r - p:
            ycnt += 1
            rcnt += 1
            ans += r
    ans += sum(P[:X - xcnt])
    ans += sum(Q[:Y - ycnt])

    print(ans)


if __name__ == '__main__':
    main()



Fixed submission:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    X, Y, A, B, C = [int(x) for x in input().split()]
    P = [int(x) for x in input().split()]
    Q = [int(x) for x in input().split()]
    R = [int(x) for x in input().split()]

    P.sort(reverse=True)
    Q.sort(reverse=True)
    R.sort(reverse=True)

    xcnt = 0
    ycnt = 0
    rcnt = 0
    ans = 0

    for r in R:
        p = float("inf")
        if X - 1 - xcnt >= 0:
            p = P[X - 1 - xcnt]
        q = float("inf")
        if Y - 1 - ycnt >= 0:
            q = Q[Y - 1 - ycnt]
        if p >= r and q >= r:
            break

        if (r - p) > 0 and r - p > r - q:
            xcnt += 1
            rcnt += 1
            ans += r
        else:
            ycnt += 1
            rcnt += 1
            ans += r

    ans += sum(P[:X - xcnt])
    ans += sum(Q[:Y - ycnt])

    print(ans)


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

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    S = input().strip()
    Q = int(input())

    rev = 0
    for i in range(Q):
        A = [x for x in input().split()]
        if len(A) == 1:
            rev = (rev + 1) % 2
        else:
            f = int(A[1])
            c = A[2]
            if f == 1:
                if rev == 0:
                    S = c + S
                else:
                    S = S + c
            else:
                if rev == 0:
                    S = S + c
                else:
                    S = c + S

    if rev == 0:
        print(S)
    else:
        print(S[::-1])


if __name__ == '__main__':
    main()


Fixed submission:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    S = input().strip()
    Q = int(input())

    rev = 0
    sdeq = collections.deque()
    for s in S:
        sdeq.append(ord(s) - ord('a'))

    for i in range(Q):
        A = [x for x in input().split()]
        if len(A) == 1:
            rev = (rev + 1) % 2
        else:
            f = int(A[1])
            c = A[2]
            if f == 1:
                if rev == 0:
                    sdeq.appendleft(ord(c) - ord('a'))
                else:
                    sdeq.append(ord(c) - ord('a'))
            else:
                if rev == 0:
                    sdeq.append(ord(c) - ord('a'))
                else:
                    sdeq.appendleft(ord(c) - ord('a'))

    if rev == 0:
        for i in list(sdeq):
            print(chr(i + ord('a')), end="")
    else:
        for i in list(sdeq)[::-1]:
            print(chr(i + ord('a')), end="")
    print()



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

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N, P = [int(x) for x in input().split()]
    S = input().strip()

    if P == 2 or P == 5:
        ans = 0
        for i, s in enumerate(S[::-1]):
            if int(s) % P == 0:
                ans += N - i
        print(ans)
        return

    M = [0] * N
    for i, s in enumerate(S[::-1]):
        M[i] = (int(s) * (10 ** i)) % P

    MA = []
    MA.append(M[0])
    c = collections.Counter()
    ans = 0
    c[0] += 1
    ans += c[MA[0]]
    c[M[0]] += 1
    for i in range(1, N):
        MA.append((MA[i - 1] + M[i]) % P)
        ans += c[MA[i]]
        c[MA[i]] += 1

    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
import sys
import itertools
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N, P = [int(x) for x in input().split()]
    S = input().strip()

    if P == 2 or P == 5:
        ans = 0
        for i, s in enumerate(S[::-1]):
            if int(s) % P == 0:
                ans += N - i
        print(ans)
        return

    M = [0] * N
    for i, s in enumerate(S[::-1]):
        M[i] = (int(s) * pow(10, i, P)) % P

    MA = []
    MA.append(M[0])
    c = collections.Counter()
    ans = 0
    c[0] += 1
    ans += c[MA[0]]
    c[M[0]] += 1
    for i in range(1, N):
        MA.append((MA[i - 1] + M[i]) % P)
        ans += c[MA[i]]
        c[MA[i]] += 1

    print(ans)


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

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N, M = [int(x) for x in input().split()]
    SC = [[int(x) for x in input().split()] for _ in range(N)]

    f = False
    for i in range(1000):
        if len(str(i)) != N:
            continue

        x = str(i)
        for s, c in SC:
            if int(x[s - 1]) != c:
                break
        else:
            f = True

        if f:
            print(i)
            return
    else:
        print(-1)


if __name__ == '__main__':
    main()



Fixed submission:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N, M = [int(x) for x in input().split()]
    SC = [[int(x) for x in input().split()] for _ in range(M)]

    f = False
    for i in range(1000):
        if len(str(i)) != N:
            continue

        x = str(i)
        for s, c in SC:
            if int(x[s - 1]) != c:
                break
        else:
            f = True

        if f:
            print(i)
            return
    else:
        print(-1)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
#####segfunc######
def segfunc(x, y):
    return x | y


def init(init_val):
    # set_val
    for i in range(n):
        seg[i + num - 1] = set(init_val[i])
        # built
    for i in range(num - 2, -1, -1):
        seg[i] = segfunc(seg[2 * i + 1], seg[2 * i + 2])


def update(k, x):
    k += num - 1
    seg[k] = set(x)
    while k:
        k = (k - 1) // 2
        seg[k] = segfunc(seg[k * 2 + 1], seg[k * 2 + 2])


def query(p, q):
    if q <= p:
        return ide_ele
    p += num - 1
    q += num - 2
    res = ide_ele
    while q - p > 1:
        if p & 1 == 0:
            res = segfunc(res, seg[p])
        if q & 1 == 1:
            res = segfunc(res, seg[q])
            q -= 1
        p = p // 2
        q = (q - 1) // 2
    if p == q:
        res = segfunc(res, seg[p])
    else:
        res = segfunc(segfunc(res, seg[p]), seg[q])
    return res


#####単位元######
ide_ele = set()

n = int(input())
S = input().strip()
Q = int(input())

num = 2 ** (n - 1).bit_length()
seg = [set()] * 2 * num

init(S)


for _ in range(Q):
    a, b, c = [x for x in input().split()]
    if a == "1":
        update(int(b) - 1, c)
    else:
        print(len(query(int(b) - 1, int(c))))


Fixed submission:
#####segfunc######
def segfunc(x, y):
    return x | y


def init(init_val):
    # set_val
    for i in range(n):
        seg[i + num - 1] = set(init_val[i])
        # built
    for i in range(num - 2, -1, -1):
        seg[i] = segfunc(seg[2 * i + 1], seg[2 * i + 2])


def update(k, x):
    k += num - 1
    seg[k] = set(x)
    while k:
        k = (k - 1) // 2
        seg[k] = segfunc(seg[k * 2 + 1], seg[k * 2 + 2])


def query(p, q):
    if q <= p:
        return ide_ele
    p += num - 1
    q += num - 2
    res = ide_ele
    while q - p > 1:
        if p & 1 == 0:
            res = segfunc(res, seg[p])
        if q & 1 == 1:
            res = segfunc(res, seg[q])
            q -= 1
        p = p // 2
        q = (q - 1) // 2
    if p == q:
        res = segfunc(res, seg[p])
    else:
        res = segfunc(segfunc(res, seg[p]), seg[q])
    return res


#####単位元######
ide_ele = set()

n = int(input())
S = input().strip()
Q = int(input())

num = 2 ** (n - 1).bit_length()
seg = [set()] * 2 * num

init(S)


for _ in range(Q):
    a, b, c = [x for x in input().split()]
    if a == "1":
        update(int(b) - 1, c)
    else:
        print(len(query(int(b) - 1, int(c))))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from functools import lru_cache

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def modInverse(a, p):
    return pow(a, p - 2, p)


@lru_cache(maxsize=None)
def modBinomial(n, k, p):
    numerator = 1
    for i in range(k):
        numerator = (numerator * (n - i)) % p

    denominator = 1
    for i in range(1, k + 1):
        denominator = (denominator * i) % p

    return (numerator * modInverse(denominator, p)) % p


def main():
    N, K = [int(x) for x in input().split()]
    MOD = 10 ** 9 + 7

    a = min(N - 1, K)

    ans = 1
    for i in range(1, a + 1):
        ans += (modBinomial(N, i, MOD) * modBinomial(N - 1,  N - i - 1, MOD)) % MOD

    print(ans % MOD)


if __name__ == '__main__':
    main()


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline

fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

def cmb(n, r, p):
    global fact, factinv
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n - r] % p


def main():
    N, K = [int(x) for x in input().split()]
    MOD = 10 ** 9 + 7

    a = min(N - 1, K)

    global fact, factinv, inv
    for i in range(2, N + 1):
        fact.append((fact[-1] * i) % MOD)
        inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
        factinv.append((factinv[-1] * inv[-1]) % MOD)

    ans = 1
    for i in range(1, a + 1):
        ans += cmb(N, i, MOD) * cmb(N - 1, N - i - 1, MOD) % MOD

    print(ans % MOD)


if __name__ == '__main__':
    main()

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

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def modInverse(a, p):
    return pow(a, p - 2, p)


@lru_cache(maxsize=None)
def modBinomial(n, k, p):
    numerator = 1
    for i in range(k):
        numerator = (numerator * (n - i)) % p

    denominator = 1
    for i in range(1, k + 1):
        denominator = (denominator * i) % p

    return (numerator * modInverse(denominator, p)) % p


def main():
    N, K = [int(x) for x in input().split()]
    MOD = 10 ** 9 + 7

    a = min(N - 1, K)

    ans = 1
    for i in range(1, a + 1):
        ans += modBinomial(N, i, MOD) * modBinomial(N - 1,  N - i - 1, MOD)

    print(ans % MOD)


if __name__ == '__main__':
    main()


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline

fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

def cmb(n, r, p):
    global fact, factinv
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n - r] % p


def main():
    N, K = [int(x) for x in input().split()]
    MOD = 10 ** 9 + 7

    a = min(N - 1, K)

    global fact, factinv, inv
    for i in range(2, N + 1):
        fact.append((fact[-1] * i) % MOD)
        inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
        factinv.append((factinv[-1] * inv[-1]) % MOD)

    ans = 1
    for i in range(1, a + 1):
        ans += cmb(N, i, MOD) * cmb(N - 1, N - i - 1, MOD) % MOD

    print(ans % MOD)


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

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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

    nstr = str(N)

    nl = len(str(N))

    dp = [[[0 for _ in range(nl + 1)] for _ in range(2)] for _ in range(nl + 1)]
    dp[0][0][0] = 1

    for i in range(nl):
        max_digit = int(nstr[i])
        for smaller in range(2):
            for j in range(nl):
                range_digit = 9
                # range_digit = 9 if smaller else max_digit
                if not smaller:
                    range_digit = max_digit
                for x in range(range_digit + 1):
                    if x != 0:
                        if smaller == 1:
                            dp[i + 1][smaller][j + 1] += dp[i][smaller][j]
                        else:
                            if x < max_digit:
                                dp[i + 1][1][j + 1] += dp[i][smaller][j]
                            else:
                                dp[i + 1][0][j + 1] += dp[i][smaller][j]
                    else:
                        if smaller == 1:
                            dp[i + 1][smaller][j] += dp[i][smaller][j]
                        else:
                            if x < max_digit:
                                dp[i + 1][1][j] += dp[i][smaller][j]
                            else:
                                dp[i + 1][0][j] += dp[i][smaller][j]

    ans = 0
    print(dp[nl][1][K])


if __name__ == '__main__':
    main()


Fixed submission:
import sys
from functools import lru_cache

input = sys.stdin.readline

sys.setrecursionlimit(10 ** 8)


@lru_cache(maxsize=None)
def solve(n, k):
    if n < 10:
        if k == 1:
            return n
        elif k == 0:
            return 1
        else:
            return 0

    q, r = divmod(n, 10)

    return solve(q, k) + solve(q, k - 1) * r + solve(q - 1, k - 1) * (9 - r)


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

    print(solve(N, K))


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

input = sys.stdin.readline


def main():
    H, N = [int(x) for x in input().split()]
    AB = []
    for _ in range(N):
        a, b = [int(x) for x in input().split()]
        AB.append([a, b])

    dp = [0] * (H + 1)

    for i in range(1, H + 1):
        mi = float("inf")
        for a, b in AB:
            mi = min(mi, dp[max(i - a, 0)] + b)
        dp[i] = mi

    print(dp[H])



if __name__ == '__main__':
    main()


Fixed submission:
import sys
from operator import itemgetter

input = sys.stdin.readline


def main():
    H, N = [int(x) for x in input().split()]
    AB = []
    for _ in range(N):
        a, b = [int(x) for x in input().split()]
        AB.append([a, b])

    dp = [0] * (H + 1)

    for i in range(1, H + 1):
        mi = float("inf")
        for a, b in AB:
            mi = min(mi, dp[max(i - a, 0)] + b)
        dp[i] = mi

    print(dp[H])



if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
from collections import deque


def main():
    H, W = [int(x) for x in input().split()]
    A = [["" for i in range(W)] for j in range(H)]

    for j in range(H):
        S = input().strip()
        for i, s in enumerate(list(S)):
            A[j][i] = s


    ma = 0

    dj = [1, 0, -1, 0]
    di = [0, 1, 0, -1]

    for sj in range(H):
        for si in range(W):
            for gj in range(H):
                for gi in range(W):
                    d = [[-1] * W for i in range(H)]
                    q = deque([])
                    q.append((sj, si))
                    d[sj][si] = 0

                    while q:
                        p = q.popleft()
                        if p[0] == gj and p[1] == gi:
                            break
                        for i in range(4):
                            nj = p[0] + dj[i]
                            ni = p[1] + di[i]

                            if 0 <= nj < H and 0 <= ni < W and A[nj][ni] != "#" and d[nj][ni] == -1:
                                q.append((nj, ni))
                                d[nj][ni] = d[p[0]][p[1]] + 1

                    ma = max(ma, d[gj][gi])



    print(ma)





    


if __name__ == '__main__':
    main()



Fixed submission:
import sys
input = sys.stdin.readline
from collections import deque


def main():
    H, W = [int(x) for x in input().split()]
    A = [["" for i in range(W)] for j in range(H)]

    for j in range(H):
        S = input().strip()
        for i, s in enumerate(list(S)):
            A[j][i] = s

    ma = 0

    dj = [1, 0, -1, 0]
    di = [0, 1, 0, -1]

    for sj in range(H):
        for si in range(W):
            if A[sj][si] == "#":
                continue
            d = [[-1 for i in range(W)] for j in range(H)]
            q = deque([])
            q.append((sj, si))
            d[sj][si] = 0

            while q:
                p = q.popleft()
                for i in range(4):
                    nj = p[0] + dj[i]
                    ni = p[1] + di[i]

                    if 0 <= nj < H and 0 <= ni < W and A[nj][ni] != "#" and d[nj][ni] == -1:
                        q.append((nj, ni))
                        d[nj][ni] = d[p[0]][p[1]] + 1

            for gj in range(H):
                for gi in range(W):
                    ma = max(ma, d[gj][gi])

    print(ma)





    


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


def main():
    MOD = 10 ** 9 + 7
    N = int(input())
    A = [int(x) for x in input().split()]

    x = [0] * 61
    for i in range(N):
        for j in range(61):
            if A[i] >> j & 1:
                x[j] += 1
    ans = sum(A) * (N - 1)
    for i, v in enumerate(x):
        if v == 0 or v == 1:
            continue
        else:
            z = (2 ** i) * (v * (v - 1))
            ans = ans - z

    print(ans % MOD)







if __name__ == '__main__':
    main()



Fixed submission:
import sys
input = sys.stdin.readline


def main():
    MOD = 10 ** 9 + 7
    N = int(input())
    A = [int(x) for x in input().split()]

    x = [0] * 61
    for i in range(N):
        for j in range(61):
            if A[i] >> j & 1:
                x[j] += 1
    ans = sum(A) * (N - 1)
    for i, v in enumerate(x):
        if v == 0 or v == 1:
            continue
        else:
            z = (2 ** i) * (v * (v - 1))
            ans = ans - z

    print(ans % MOD)







if __name__ == '__main__':
    main()