Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):

import itertools
import sys
import math

sys.setrecursionlimit(10**9)

def comb(n, r):
    mod = 10**9 + 7
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * pow(i+1, mod-2, mod) % mod
    return res

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

    # print(comb(10**5,5000,10**9+7))
    nCa = comb(N,a)
    nCb = comb(N,b)

    _, ans = divmod(2**N-1 - nCa - nCb,10**9+7)
    print(ans)

if __name__ == "__main__":
  main()


Fixed submission:

import itertools
import sys
import math

sys.setrecursionlimit(10**9)

def comb(n, r):
    mod = 10**9 + 7
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * pow(i+1, mod-2, mod) % mod
    return res

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

    # print(comb(10**5,5000,10**9+7))
    nCa = comb(N,a)
    nCb = comb(N,b)

    _, ans = divmod(2**N-1 - nCa - nCb,10**9+7)
    print(ans)

if __name__ == "__main__":
  main()

Buggy python submission (verdict: Time Limit Exceeded):

import itertools
import sys
import math
import numpy as np
from collections import deque
from itertools import combinations
from functools import reduce
from functools import lru_cache
sys.setrecursionlimit(10**9)

def comb(n, r):
    mod = 10**9 + 7
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * pow(i+1, mod-2, mod) % mod
    return res

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

    # print(comb(10**5,5000,10**9+7))
    nCa = comb(N,a)
    nCb = comb(N,b)

    _, ans = divmod(2**N-1 - nCa - nCb,10**9+7)
    print(ans)

if __name__ == "__main__":
  main()


Fixed submission:

import itertools
import sys
import math

sys.setrecursionlimit(10**9)

def comb(n, r):
    mod = 10**9 + 7
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * pow(i+1, mod-2, mod) % mod
    return res

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

    # print(comb(10**5,5000,10**9+7))
    nCa = comb(N,a)
    nCb = comb(N,b)

    _, ans = divmod(2**N-1 - nCa - nCb,10**9+7)
    print(ans)

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

import itertools
import sys
import numpy as np
from collections import deque
from itertools import combinations
sys.setrecursionlimit(10**9)


def solve(N,K):
    # print(N,K)
    if N <= 10:
        if K == 0:
            return 1
        elif K == 1:
            return N
        else:
            return 0

    if K < 0 or len(str(N)) < K:
        return 0

    ans = 0
    m, last = divmod(N,10)
    ans += solve(m,K-1) * last + solve(m-1,K-1) * (9 - last) + solve(m,K)

    return ans


def main():
    N,K = map(int,[input(),input()])
    
    print(solve(N,K))

if __name__ == "__main__":
  main()


Fixed submission:
import itertools
import sys
import numpy as np
from collections import deque
from itertools import combinations
from functools import lru_cache
sys.setrecursionlimit(10**9)

@lru_cache(None)
def solve(N,K):
    # print(N,K)
    if N <= 10:
        if K == 0:
            return 1
        elif K == 1:
            return N
        else:
            return 0

    if K < 0 or len(str(N)) < K:
        return 0

    ans = 0
    m, last = divmod(N,10)
    ans += solve(m,K-1) * last + solve(m-1,K-1) * (9 - last) + solve(m,K)

    return ans


def main():
    N,K = map(int,[input(),input()])

    print(solve(N,K))

if __name__ == "__main__":
  main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)

INF = 10**20
def main():
    H,N = map(int,input().split())
    A,B = [],[]
    for _ in range(N):
        a,b = map(int,input().split())
        A.append(a)
        B.append(b)

    tp = 3 * 10**4
    dp = [INF] * tp
    dp[0] = 0
    minim = INF
    for h in range(tp):
        for i in range(N):
            dp_i = min(h-A[i],H)
            dp[h] = min(dp[h],dp[dp_i]+B[i])
            if h >= H:
                minim = min(minim,dp[h])


    print(minim)
    # assert False


if __name__ == "__main__":
  main()

Fixed submission:
import sys
sys.setrecursionlimit(10**9)

INF = 10**20
def main():
    H,N = map(int,input().split())
    A,B = [],[]
    for _ in range(N):
        a,b = map(int,input().split())
        A.append(a)
        B.append(b)

    tp = 3 * 10**4
    dp = [INF] * tp
    dp[0] = 0
    ans = INF
    for h in range(tp):
        minim = INF
        for i in range(N):
            dp_i = h-A[i]
            if dp_i >= 0 and dp[dp_i] != INF:
                minim = min(minim,dp[dp_i]+B[i])
                # print(dp[h-A[i]]+B[i])

        if minim != INF:
            dp[h] = minim
            if h >= H:
                ans = min(ans,dp[h])


    print(ans)


if __name__ == "__main__":
  main()

Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**9)

INF = 10**20
def main():
    H,N = map(int,input().split())
    A,B = [],[]
    for _ in range(N):
        a,b = map(int,input().split())
        A.append(a)
        B.append(b)

    tp = 10**4
    dp = [INF] * tp
    dp[0] = 0
    for h in range(tp):
        minim = INF
        for i in range(N):
            dp_i = h-A[i]
            if dp_i >= 0 and dp[dp_i] != INF:
                minim = min(minim,dp[dp_i]+B[i])
                # print(dp[h-A[i]]+B[i])

        if minim != INF:
            dp[h] = minim
            if h >= H:
                # print(dp[h],h,dp)
                print(dp[h])
                exit()


    assert False


if __name__ == "__main__":
  main()

Fixed submission:
import sys
sys.setrecursionlimit(10**9)

INF = 10**20
def main():
    H,N = map(int,input().split())
    A,B = [],[]
    for _ in range(N):
        a,b = map(int,input().split())
        A.append(a)
        B.append(b)

    tp = 3 * 10**4
    dp = [INF] * tp
    dp[0] = 0
    ans = INF
    for h in range(tp):
        minim = INF
        for i in range(N):
            dp_i = h-A[i]
            if dp_i >= 0 and dp[dp_i] != INF:
                minim = min(minim,dp[dp_i]+B[i])
                # print(dp[h-A[i]]+B[i])

        if minim != INF:
            dp[h] = minim
            if h >= H:
                ans = min(ans,dp[h])


    print(ans)


if __name__ == "__main__":
  main()
Buggy python submission (verdict: Time Limit Exceeded):
import itertools
import sys
import math
import fractions
import numpy as np
from collections import deque
from itertools import combinations
from functools import reduce
from functools import lru_cache
sys.setrecursionlimit(10**9)

def get_lcm(num):
    return reduce(lambda x,y:(x * y) // fractions.gcd(x, y), num, 1)

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

    lcm = get_lcm(A)
    _, ans = divmod(sum(list(map(lambda a: lcm // a ,A))), (10**9+7))

    print(ans)

if __name__ == "__main__":
  main()


Fixed submission:
import itertools
import sys
import math
import fractions
from collections import deque
from itertools import combinations
from functools import reduce
from functools import lru_cache
sys.setrecursionlimit(10**9)

def get_lcm(num):
    return reduce(lambda x,y:(x * y) // fractions.gcd(x, y), num, 1)

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

    lcm = get_lcm(A)
    sum = 0
    for a in A:
      sum += lcm // a
    _, ans = divmod(sum, (10**9+7))

    print(ans)

if __name__ == "__main__":
  main()

Buggy python submission (verdict: Runtime Error):

import itertools
import sys
import math
import numpy as np
from collections import deque
from itertools import combinations
from functools import lru_cache
sys.setrecursionlimit(10**9)

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

    lcm = np.lcm.reduce(A)
    _, ans = divmod(sum(map(lambda a: lcm // a ,A)), (10**9+7))

    print(ans)

if __name__ == "__main__":
  main()


Fixed submission:
import itertools
import sys
import math
import fractions
from collections import deque
from itertools import combinations
from functools import reduce
from functools import lru_cache
sys.setrecursionlimit(10**9)

def get_lcm(num):
    return reduce(lambda x,y:(x * y) // fractions.gcd(x, y), num, 1)

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

    lcm = get_lcm(A)
    sum = 0
    for a in A:
      sum += lcm // a
    _, ans = divmod(sum, (10**9+7))

    print(ans)

if __name__ == "__main__":
  main()
Buggy python submission (verdict: Runtime Error):
import itertools
import sys
import math
import numpy as np
import fractions
from collections import deque
from itertools import combinations
from functools import reduce
from functools import lru_cache
sys.setrecursionlimit(10**9)

def get_lcm(num):
    return reduce(lambda x,y:(x * y) // fractions.gcd(x, y), num, 1)

def main():
    N,M = map(int,input().split())
    half_A = list(map(lambda x:int(x)//2,input().split()))

    lcm = get_lcm(half_A)

    if lcm <= M:
        if reduce(lambda x, y: (lcm // x) % 2 == 1 and (lcm // y) % 2 == 1, half_A):
            print(math.ceil(M/(2*lcm)))
            exit()

    print(0)


if __name__ == "__main__":
  main()


Fixed submission:
import itertools
import sys
import math
import numpy as np
import fractions
from collections import deque
from itertools import combinations
from functools import reduce
from functools import lru_cache
sys.setrecursionlimit(10**9)

def get_lcm(num):
    return reduce(lambda x,y:(x * y) // fractions.gcd(x, y), num, 1)

def main():
    N,M = map(int,input().split())
    half_A = list(map(lambda x:int(x)//2,input().split()))

    lcm = get_lcm(half_A)

    if lcm > M:
        print(0)
        exit()

    for a in half_A:
        if (lcm // a) % 2 == 0:
            print(0)
            exit()

    # print(math.ceil(M/(2*lcm)))
    print((M//lcm + 1) // 2)


if __name__ == "__main__":
  main()
Buggy python submission (verdict: Time Limit Exceeded):
import itertools
import sys
import math
import numpy as np
import fractions
from collections import deque
from itertools import combinations
from functools import reduce
from functools import lru_cache
from bisect import insort
sys.setrecursionlimit(10**9)

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

    ans = 0
    for mask in range(60): # 各桁ごとに、1を持つ数を探す
        one_sum = 0
        for a in A:
            one_sum += (a >> mask) & 1

        ans += one_sum * (N - one_sum) * 2**mask

    print(ans%(10**9+7))

if __name__ == "__main__":
  main()

Fixed submission:
import sys
sys.setrecursionlimit(10**9)

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

    ans = 0
    for mask in range(60): # 各桁ごとに、1を持つ数を探す
        one_sum = 0
        for a in A:
            one_sum += (a >> mask) & 1

        ans += one_sum * (N - one_sum) * 2**mask

    print(ans%(10**9+7))

if __name__ == "__main__":
  main()
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
import os
f = open('/Users/yuigawada/Desktop/競プロ/Atcoder/input.txt', 'r')
sys.stdin = f

import itertools
import numpy as np
import fractions
from itertools import combinations
from functools import reduce
from functools import lru_cache
import math
from collections import deque
import decimal
import bisect
import heapq
from collections import defaultdict
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N=ii()
    print(N**2)




if __name__ == "__main__":
    main()

Fixed submission:
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N=ii()
    print(N**2)




if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
import itertools
import sys
import math
import numpy as np
import fractions
from collections import deque
from itertools import combinations
from functools import reduce
from functools import lru_cache
sys.setrecursionlimit(10**9)

def main():
    A, B= map(int,input().split())
    gcd = math.gcd(A,B)
    root = math.sqrt(gcd)

    ps = []
    ans = 1
    for p in range(2,math.floor(root)+2):
        is_prime = True
        for _p in ps:
            if p % _p == 0:
                is_prime = False
                break
        if is_prime:
            ps.append(p)
            if gcd % p == 0:
                ans += 1


    print(ans)


if __name__ == "__main__":
  main()


Fixed submission:
import fractions
import sys
sys.setrecursionlimit(10**9)


INF=10**20
def prime_factorize(n):
    P = []
    P_set = set()
    while n % 2 == 0:
        P.append(2)
        P_set.add(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            P.append(f)
            P_set.add(f)
            n //= f
        else:
            f += 2
    if n != 1:
        P.append(n)
        P_set.add(n)

    P_count = {p:0 for p in P_set}
    for p in P: P_count[p] += 1

    return P_count


def solve(A: int, B: int):
    gcd = fractions.gcd(A,B)
    P = prime_factorize(gcd).keys()
    print(len(list(P))+1)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    solve(A, B)



if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
import bisect
import sys
sys.setrecursionlimit(10**9)

def main():
    S, T = list(input()),list(input())

    len_of_S = len(S)
    counter = {}
    seen = set()
    for i in range(len_of_S):
        if S[i] in seen:
            counter[S[i]].append(i) # 常に単調増加
        else:
            counter[S[i]] = [i]
            seen.add(S[i])

    len_of_T = len(T)

    if not T[0] in seen:
        print(-1)
        exit()

    counts = counter[T[0]]
    if len(counts) == 0:
        print(-1)
        exit()

    pre = counts[0]
    rep = 1

    for i in range(1,len_of_T):
        counts = counter[T[i]]
        if len(counts) == 0:
            print(-1)
            exit()

        j = bisect.bisect_left(counts,pre)
        mx = len(counts)

        while j < mx and not counts[j] > pre:
            j += 1

        # print(pre,ans)
        if j<mx:
            pre = counts[j]
        else:
            pre = counts[0]
            rep += 1
        # print(pre,ans)

    # print(counter[T[::-1][0]],len_of_S)
    rep -= 1
    ans = rep * len_of_S  + counter[T[::-1][0]][0] + 1
    print(ans)




if __name__ == "__main__":
  main()


Fixed submission:
import bisect
import sys
sys.setrecursionlimit(10**9)

def main():
    S, T = list(input()),list(input())

    len_of_S = len(S)
    counter = {}
    seen = set()
    for i in range(len_of_S):
        if S[i] in seen:
            counter[S[i]].append(i) # 常に単調増加
        else:
            counter[S[i]] = [i]
            seen.add(S[i])

    len_of_T = len(T)

    if not T[0] in seen:
        print(-1)
        exit()

    counts = counter[T[0]]
    if len(counts) == 0:
        print(-1)
        exit()

    pre = counts[0]
    rep = 1

    for i in range(1,len_of_T):
        if not T[i] in seen:
            print(-1)
            exit()

        counts = counter[T[i]]
        if len(counts) == 0:
            print(-1)
            exit()

        j = bisect.bisect_left(counts,pre)
        mx = len(counts)

        while j < mx and not counts[j] > pre:
            j += 1

        # print(pre,rep)
        if j<mx:
            pre = counts[j]
        else:
            pre = counts[0]
            rep += 1
        # print(pre,rep)

    # print(counter[T[::-1][0]],len_of_S)
    rep -= 1
    ans = rep * len_of_S  + pre + 1
    print(ans)




if __name__ == "__main__":
  main()
Buggy python submission (verdict: Runtime Error):
import numpy as np
import sys
sys.setrecursionlimit(10**9)

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

    X = np.zeros((N,N))
    for i in range(N-1):
        for j in range(2):
            X[i][j+i] = 1

    X[N-1][0] = 1
    X[N-1][N-1] = 1

    ans = map(lambda y: int(y)*2, np.dot(np.linalg.pinv(X),A))
    print(*ans)


if __name__ == "__main__":
  main()

Fixed submission:
import sys
sys.setrecursionlimit(10**9)

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

    s = sum(A)
    x1 = s

    for k in range(N//2):
        x1 -= 2 * A[2*k+1]

    X = [x1]
    for i in range(N):
        x = 2 * A[i] - X[i]
        X.append(x)

    print(*X[:-1])


if __name__ == "__main__":
  main()

Buggy python submission (verdict: Runtime Error):
import numpy as np
import sys
sys.setrecursionlimit(10**9)

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

    X = np.zeros((N,N))
    for i in range(N-1):
        for j in range(2):
            X[i][j+i] = 1

    X[N-1][0] = 1
    X[N-1][N-1] = 1

    ans = map(lambda y: int(y)*2, np.dot(np.linalg.inv(X),A))
    print(*ans)

if __name__ == "__main__":
  main()

Fixed submission:
import sys
sys.setrecursionlimit(10**9)

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

    s = sum(A)
    x1 = s

    for k in range(N//2):
        x1 -= 2 * A[2*k+1]

    X = [x1]
    for i in range(N):
        x = 2 * A[i] - X[i]
        X.append(x)

    print(*X[:-1])


if __name__ == "__main__":
  main()
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
from functools import lru_cache
import bisect
import sys
sys.setrecursionlimit(10**9)

def main():
    N = int(input())
    X = []
    for _ in range(N):
        a,b = map(int,input().split())
        bisect.insort(X,(b,a))

    x = 0
    X = deque(X)
    l = len(X)
    for _ in range(l):
        b,a = X.popleft()
        # print(b,a,x)
        if x + a > b:
            print("No")
            exit()

        x += a

    print("Yes")



if __name__ == "__main__":
  main()

Fixed submission:
from collections import deque
import bisect
import sys
sys.setrecursionlimit(10**9)

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

    x = 0
    X.sort(key=lambda x: x[0])
    X = deque(X)
    l = len(X)
    for _ in range(l):
        b,a = X.popleft()
        # print(b,a,x)
        if x + a > b:
            print("No")
            exit()

        x += a

    print("Yes")



if __name__ == "__main__":
  main()

Buggy python submission (verdict: Time Limit Exceeded):
import bisect
import sys
from collections import deque
sys.setrecursionlimit(10**9)

def main():
    N = int(input())
    X = []
    for _ in range(N):
        a,b = map(int,input().split())
        bisect.insort(X,(b,a))

    x = 0
    X = deque(X)
    while len(X) > 0:
        b,a = X.popleft()
        # print(b,a,x)
        if x + a > b:
            print("No")
            exit()

        x += a

    print("Yes")



if __name__ == "__main__":
  main()

Fixed submission:
from collections import deque
import bisect
import sys
sys.setrecursionlimit(10**9)

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

    x = 0
    X.sort(key=lambda x: x[0])
    X = deque(X)
    l = len(X)
    for _ in range(l):
        b,a = X.popleft()
        # print(b,a,x)
        if x + a > b:
            print("No")
            exit()

        x += a

    print("Yes")



if __name__ == "__main__":
  main()

Buggy python submission (verdict: Time Limit Exceeded):
import bisect
import sys
sys.setrecursionlimit(10**9)

def main():
    N = int(input())
    X = []
    for _ in range(N):
        a,b = map(int,input().split())
        bisect.insort(X,(b,a))

    x = 0
    while len(X) > 0:
        b,a = X.pop(0)
        # print(b,a,x)
        if x + a > b:
            print("No")
            exit()

        x += a

    print("Yes")



if __name__ == "__main__":
  main()


Fixed submission:
from collections import deque
import bisect
import sys
sys.setrecursionlimit(10**9)

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

    x = 0
    X.sort(key=lambda x: x[0])
    X = deque(X)
    l = len(X)
    for _ in range(l):
        b,a = X.popleft()
        # print(b,a,x)
        if x + a > b:
            print("No")
            exit()

        x += a

    print("Yes")



if __name__ == "__main__":
  main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N = ii()
    A = list(mi())

    A.sort()
    if A[0] == 1:
        print(1)
        exit()
    
    ini = A[0]
    while len(A) > 1:
        x = A[0]
        B = set([x])
        for a in A:
            b = a%x
            if b > 0:
                B.add(b)

        A = list(B)
        #print(A)

    if len(A) > 0:
        print(A[0])
    else:
        print(ini)
            

            
        



if __name__ == "__main__":
    main()

Fixed submission:
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N = ii()
    A = list(mi())

    A.sort()
    if A[0] == 1:
        print(1)
        exit()
    
    ini = A[0]
    while len(A) > 1:
        x = A[0]
        B = set([x])
        for a in A:
            b = a%x
            if b > 0:
                B.add(b)

        A = list(B)
        A.sort()

    if len(A) > 0:
        print(A[0])
    else:
        print(ini)
            

            
        



if __name__ == "__main__":
    main()