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


def is_prime(q):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q & 1 == 0: return False
    return pow(2, q - 1, q) == 1


def main(n):
    if is_prime(n):
        return n - 1
    else:
        sqrt = int(math.sqrt(n))
        for i in range(sqrt, n + 1):
            div, mod = divmod(n, i)
            if mod == 0:
                return i + div - 2


if __name__ == '__main__':
    N = int(input())
    print(main(N))


Fixed submission:
import math


def is_prime(q):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q & 1 == 0: return False
    return pow(2, q - 1, q) == 1


def main(n):
    if is_prime(n):
        return n - 1
    else:
        sqrt = int(math.sqrt(n))
        for i in range(sqrt, 1, -1):
            div, mod = divmod(n, i)
            if mod == 0:
                return i + div - 2


if __name__ == '__main__':
    N = int(input())
    print(main(N))
Buggy python submission (verdict: Runtime Error):
A, B = map(int, input())

print(max(0, A - 2 * B))

Fixed submission:
A, B = map(int, input().split(' '))

print(max(0, A - 2 * B))
Buggy python submission (verdict: Time Limit Exceeded):
import bisect

N = int(input())
L = sorted(map(int, input().split(' ')))

ans = 0
for i in range(len(L)):
    for j in range(i + 1, len(L)):
        a = L[i]
        b = L[j]
        ans += bisect.bisect_right(L[j + 1:], a + b - 1)

print(ans)


Fixed submission:
import bisect

N = int(input())
L = sorted(map(int, input().split(' ')))

ans = 0
for i in range(len(L)):
    for j in range(i + 1, len(L)):
        a = L[i]
        b = L[j]
        ans += max(0, bisect.bisect_right(L, a + b - 1) - (j + 1))

print(ans)

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

N = int(input())
L = sorted(map(int, input().split(' ')))

ans = set()
for i in range(len(L)):
    for j in range(i + 1, len(L)):
        a = L[i]
        b = L[j]
        left = b - a
        right = a + b
        for k in range(bisect.bisect_right(L, left), bisect.bisect_left(L, right)):
            if k != i and k != j:
                ans.add(tuple(sorted([a, b, L[k]])))

print(len(ans))


Fixed submission:
import bisect

N = int(input())
L = sorted(map(int, input().split(' ')))

ans = 0
for i in range(len(L)):
    for j in range(i + 1, len(L)):
        a = L[i]
        b = L[j]
        ans += max(0, bisect.bisect_right(L, a + b - 1) - (j + 1))

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


@lru_cache(maxsize=None)
def get_dividers(n):
    """
    正の整数 n の約数を取得する
    """

    dividers = {i for i in range(1, int(n ** 0.5) + 1) if n % i == 0}
    return dividers | {n // d for d in dividers}


A, B = map(int, input().split(' '))

a_dividers = get_dividers(A)
b_dividers = get_dividers(B)
common_dividers = a_dividers & b_dividers
ans = []

for cd in sorted(common_dividers):
    dividers = get_dividers(cd) - {1}
    for d in ans:
        if d & dividers:
            break
    else:
        ans.append(dividers)

print(len(ans))


Fixed submission:
from functools import lru_cache


@lru_cache(maxsize=None)
def get_dividers(n):
    """
    正の整数 n の約数を取得する
    """

    dividers = {i for i in range(1, int(n ** 0.5) + 1) if n % i == 0}
    return dividers | {n // d for d in dividers}


A, B = map(int, input().split(' '))

a_dividers = get_dividers(A)
b_dividers = get_dividers(B)
common_dividers = a_dividers & b_dividers
ans = []

for cd in sorted(common_dividers):
    dividers = get_dividers(cd) - {1}
    for d in ans:
        if d & dividers:
            break
    else:
        ans.append(dividers)

print(len(ans))
Buggy python submission (verdict: Time Limit Exceeded):
N, Q = map(int, input().split(' '))
S = input()
queries = tuple(tuple(map(int, input().split(' '))) for _ in range(Q))

ac_indexes = set()
for i in range(N - 1):
    if S[i:i + 2] == 'AC':
        ac_indexes.add(i + 1)

for left, right in queries:
    count = 0
    for i in range(left, right):
        count += int(i in ac_indexes)
    print(count)



Fixed submission:
N, Q = map(int, input().split(' '))
S = input()
queries = tuple(tuple(map(int, input().split(' '))) for _ in range(Q))

cumsum = [0] * (N + 1)
for i in range(N):
    cumsum[i + 1] = cumsum[i]
    if S[i:i + 2] == 'AC':
        cumsum[i + 1] += 1

for left, right in queries:
    print(cumsum[right - 1] - cumsum[left - 1])
Buggy python submission (verdict: Runtime Error):
A, B, C = map(int, input().split(' '))
ymd = tuple(map(int, input().split('/')))

if ymd <= (2019, 4, 30):
    print('Heisei')
else:
    print('TBD')


Fixed submission:
ymd = tuple(map(int, input().split('/')))

if ymd <= (2019, 4, 30):
    print('Heisei')
else:
    print('TBD')
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

N = int(input())

values = np.array([list(map(int, input().split(' '))) for _ in range(N)])
dp = np.zeros(shape=(N, 3), dtype=int)

dp[0] = values[0]

for i in range(1, N):
    dp[i][0] = np.max(values[i][0] + dp[i - 1][1:3])
    dp[i][1] = np.max(values[i][1] + dp[i - 1][0::2])
    dp[i][2] = np.max(values[i][2] + dp[i - 1][:2])

print(np.max(dp[N - 1]))


Fixed submission:
def main(n, choices):
    results = [[0, 0, 0] for _ in range(n)]
    results[0] = choices[0]
    for i in range(1, n):
        results[i][0] = choices[i][0] + max(results[i - 1][1], results[i - 1][2])
        results[i][1] = choices[i][1] + max(results[i - 1][0], results[i - 1][2])
        results[i][2] = choices[i][2] + max(results[i - 1][0], results[i - 1][1])
    return max(results[-1])


if __name__ == '__main__':
    N = int(input())
    C = []
    for _ in range(N):
        C.append(list(map(int, input().split())))
    print(main(N, C))
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np


def main(n, w, items):
    dp = np.zeros((n + 1, w + 1), dtype=int)
    for i in range(1, n + 1):
        weight, value = items[i - 1]
        for j in range(weight):
            dp[i][j] = dp[i - 1][j]
        for j in range(weight, w + 1):
            added = dp[i - 1][j - weight] + value
            not_added = dp[i - 1][j]
            dp[i][j] = max(added, not_added)
    return dp[n][w]


if __name__ == '__main__':
    N, W = map(int, input().split())
    I = []
    for _ in range(N):
        I.append(tuple(map(int, input().split())))
    print(main(N, W, I))


Fixed submission:
import numpy as np


def main(n, w, items):
    dp = np.zeros((n + 1, w + 1), dtype=int)
    for i in range(1, n + 1):
        weight, value = items[i - 1]
        dp[i][:weight] = dp[i - 1][:weight]
        dp[i][weight:] = np.maximum(dp[i - 1][weight:], dp[i - 1][:w - weight + 1] + value)
    return dp[n][w]


if __name__ == '__main__':
    N, W = map(int, input().split())
    I = []
    for _ in range(N):
        I.append(tuple(map(int, input().split())))
    print(main(N, W, I))
Buggy python submission (verdict: Runtime Error):
import numpy as np


def main(n, w, items):
    dp = np.zeros((n + 1, w + 1), dtype=int)
    for i in range(1, n + 1):
        weight, value = items[i - 1]
        dp[i][:weight] = dp[i - 1][:weight]
        dp[i][weight:] = np.maximum(dp[i - 1][weight:], dp[i - 1][:w - weight + 1] + value)
    return dp[n][w]


if __name__ == '__main__':
    N, W = map(int, input().split())
    I = []
    for _ in range(N):
        I.append(tuple(map(int, input().split())))
    print(main(N, W, I))


Fixed submission:
import numpy as np


def main(n, w, items):
    MAX_VALUE = 100100
    dp = np.ones((n + 1, MAX_VALUE), dtype=int)
    dp = dp * (1 << 30)
    dp[0][0] = 0
    for i in range(0, n):
        weight, value = items[i]
        dp[i + 1][:value] = np.minimum(dp[i][:value], dp[i + 1][:value])
        dp[i + 1][value:] = np.minimum(dp[i][value:], dp[i][:MAX_VALUE - value] + weight)

    result = 0
    for v in range(MAX_VALUE):
        if dp[-1][v] <= w:
            result = v
    return result


if __name__ == '__main__':
    N, W = map(int, input().split())
    I = []
    for _ in range(N):
        I.append(tuple(map(int, input().split())))
    print(main(N, W, I))
Buggy python submission (verdict: Runtime Error):
K = int(input())

odd = [0 for i in range(1, K + 1) if i % 2 == 1]
even = [0 for i in range(1, K + 1) if i % 2 == 0]

print(len(odd) * len(event))


Fixed submission:
K = int(input())

odd = [0 for i in range(1, K + 1) if i % 2 == 1]
even = [0 for i in range(1, K + 1) if i % 2 == 0]

print(len(odd) * len(even))
Buggy python submission (verdict: Runtime Error):
S = list(input())

if S[0] != 'A':
    print('WC')
elif 'C' not in S[2:-1]:
    print('WC')
else:
    S.remove('A')
    S.remove('C')
    for c in S:
        if c.is_upper():
            print('WC')
    else:
        print('AC')


Fixed submission:
S = list(input())

if S[0] != 'A':
    print('WA')
elif S[2:-1].count('C') != 1:
    print('WA')
else:
    S = list(S[1:])
    S.remove('C')
    S = ''.join(S)
    if S.islower():
        print('AC')
    else:
        print('WA')
Buggy python submission (verdict: Time Limit Exceeded):
import math
from itertools import permutations

D, G = map(int, input().split(' '))
questions = [tuple(map(int, input().split(' '))) for _ in range(D)]

min_answer = 1000

for question_ids in permutations(range(D)):
    score = G
    answer = 0
    for question_id in question_ids:
        n, bonus = questions[question_id]
        point = 100 * (question_id + 1)
        n_ans = min(n, math.ceil(score / point))
        answer += n_ans
        score -= n_ans * point
        if n_ans == n:
            score -= bonus
        if score <= 0:
            min_answer = min(min_answer, answer)
            break

print(min_answer)


Fixed submission:
from itertools import product

D, G = map(int, input().split(' '))
questions = [tuple(map(int, input().split(' '))) for _ in range(D)]
questions = [(100 * index, n, bonus) for index, (n, bonus) in enumerate(questions, start=1)]

min_answer = 1000

for bits in product((True, False), repeat=D):
    not_complete = []
    score = G
    answered = 0
    for index, bit in enumerate(bits):
        if not bit:
            not_complete.append(index)
            continue

        point, n, bonus = questions[index]
        score -= point * n + bonus
        answered += n

    if not_complete:
        index = max(not_complete)
        point, n, _ = questions[index]
        while score > 0 and n > 1:
            score -= point
            n -= 1
            answered += 1

    if score <= 0:
        min_answer = min(min_answer, answered)

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

N = int(input())
A = np.array(list(map(int, input().split(' '))))
B = np.arange(1, N + 1)

C = A - B
mean = int(np.mean(C))

print(min(np.sum(np.abs(C - mean))), np.sum(np.abs(C + mean)))


Fixed submission:
from functools import lru_cache
import numpy as np

N = int(input())
A = np.array(list(map(int, input().split(' '))))
i = np.arange(1, N + 1)

left = -(10 ** 10)
right = (10 ** 10)


@lru_cache(maxsize=None)
def cost(b):
    return np.sum(np.abs(A - (i + b)))


while True:
    mid = (left + right) // 2
    c_left = cost(left)
    c_right = cost(right)
    if left == mid or right == mid:
        print(min(c_left, c_right))
        break
    elif c_left < c_right:
        right = mid
    else:
        left = mid
Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(10 ** 9)

S = input()
K = int(input())

chars = sorted(set(S))
checked = set()


def dfs(s):
    for c in chars:
        next_s = s + c
        if next_s not in checked and next_s in S:
            checked.add(next_s)
            if len(checked) == K:
                print(next_s)
                return
            elif len(next_s) <= len(S):
                dfs(next_s)


dfs('')


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 9)

S = input()
K = int(input())

chars = sorted(set(S))
checked = set()


def dfs(s):
    for c in chars:
        if len(checked) >= K:
            return
        next_s = s + c
        if next_s not in checked and next_s in S:
            checked.add(next_s)
            if len(checked) == K:
                print(next_s)
                return
            elif len(next_s) <= len(S):
                dfs(next_s)


dfs('')

Buggy python submission (verdict: Runtime Error):
S = input()
K = int(input())

chars = sorted(set(S))
checked = set()


def dfs(s):
    for c in chars:
        next_s = s + c
        if next_s not in checked and next_s in S:
            checked.add(next_s)
            if len(checked) == K:
                print(next_s)
                return
            elif len(next_s) <= len(S):
                dfs(next_s)


dfs('')


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 9)

S = input()
K = int(input())

chars = sorted(set(S))
checked = set()


def dfs(s):
    for c in chars:
        if len(checked) >= K:
            return
        next_s = s + c
        if next_s not in checked and next_s in S:
            checked.add(next_s)
            if len(checked) == K:
                print(next_s)
                return
            elif len(next_s) <= len(S):
                dfs(next_s)


dfs('')
Buggy python submission (verdict: Runtime Error):
def cost(p1, p2):
    return abs(p1 - p2)


input()
points = (0, *map(int, input().split(' ')), 0)

base_cost = sum([cost(p, pre_p) for pre_p, p in zip(points, points[1:])])

for pre_p, p, next_p in zip(points, points[1:], points[2:]):
    diff = cost(pre_p, next_p) - cost(pre_p, p) - cost(p, next_p)
    print(base_cost + diff)


Fixed submission:
from itertools import chain


def cost(p1, p2):
    return abs(p1 - p2)


input()
points = tuple(chain.from_iterable(([0], tuple(map(int, input().split(' '))), [0])))

base_cost = sum([cost(p, pre_p) for pre_p, p in zip(points, points[1:])])

for pre_p, p, next_p in zip(points, points[1:], points[2:]):
    diff = cost(pre_p, next_p) - cost(pre_p, p) - cost(p, next_p)
    print(base_cost + diff)
Buggy python submission (verdict: Time Limit Exceeded):
from functools import lru_cache


@lru_cache(maxsize=None)
def is_prime(n):
    """
    nが素数かどうか判定する
    """
    if n < 2:
        return False
    elif n == 2:
        return True
    elif n % 2 == 0:
        return False
    else:
        i = 3
        while i ** 2 <= n:
            if n % i == 0:
                return False
            i += 2
        return True


Q = int(input())
for _ in range(Q):
    left, right = map(int, input().split(' '))
    if left % 2 == 0:
        left += 1
    print(len([n for n in range(left, right + 1, 2) if is_prime(n) and is_prime((n + 1) // 2)]))


Fixed submission:
from functools import lru_cache


@lru_cache(maxsize=None)
def is_prime(n):
    """
    nが素数かどうか判定する
    """
    if n < 2:
        return False
    elif n == 2:
        return True
    elif n % 2 == 0:
        return False
    else:
        i = 3
        while i ** 2 <= n:
            if n % i == 0:
                return False
            i += 2
        return True


size = 10 ** 5 + 1
memo = [0] * size
for n in range(3, size):
    memo[n] = memo[n - 1]
    if n % 2 == 1 and is_prime(n) and is_prime((n + 1) // 2):
        memo[n] += 1

Q = int(input())
for _ in range(Q):
    left, right = map(int, input().split(' '))
    print(memo[right] - memo[left - 1])

Buggy python submission (verdict: Time Limit Exceeded):
def is_prime(n):
    """
    nが素数かどうか判定する
    """
    if n < 2:
        return False
    elif n == 2:
        return True
    elif n % 2 == 0:
        return False
    else:
        i = 3
        while i ** 2 <= n:
            if n % i == 0:
                return False
            i += 2
        return True


Q = int(input())
for _ in range(Q):
    left, right = map(int, input().split(' '))
    if left % 2 == 0:
        left += 1
    print(len([n for n in range(left, right + 1, 2) if is_prime(n) and is_prime((n + 1) // 2)]))


Fixed submission:
from functools import lru_cache


@lru_cache(maxsize=None)
def is_prime(n):
    """
    nが素数かどうか判定する
    """
    if n < 2:
        return False
    elif n == 2:
        return True
    elif n % 2 == 0:
        return False
    else:
        i = 3
        while i ** 2 <= n:
            if n % i == 0:
                return False
            i += 2
        return True


size = 10 ** 5 + 1
memo = [0] * size
for n in range(3, size):
    memo[n] = memo[n - 1]
    if n % 2 == 1 and is_prime(n) and is_prime((n + 1) // 2):
        memo[n] += 1

Q = int(input())
for _ in range(Q):
    left, right = map(int, input().split(' '))
    print(memo[right] - memo[left - 1])
Buggy python submission (verdict: Runtime Error):
def check_a(numbers):
    if numbers.count(5) == 2 and numbers.count(7) == 1:
        return 'YES'
    else:
        return 'NO'


def main():
    numbers = list(map(int, input()))
    print(check_a(numbers=numbers))


if __name__ == '__main__':
    main()


Fixed submission:
def check_a(numbers):
    if numbers.count(5) == 2 and numbers.count(7) == 1:
        return 'YES'
    else:
        return 'NO'


def main():
    numbers = list(map(int, input().split()))
    print(check_a(numbers=numbers))


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
 
inf = 1 << 32
 
def solve():
    N, W = map(int, input().split())
    ws = []
    vs = []
 
    for i in range(N):
        wi, vi = map(int, input().split())
        ws.append(wi)
        vs.append(vi)
 
    dp = [[[-inf]*(3*N + 1) for j in range(N + 1)]
                              for i in range(N + 1)]
 
    dp[0][0][0] = 0
 
    for i in range(N):
        for j in range(N + 1):
            for k in range(3*N + 1):
                dp[i + 1][j][k] = dp[i][j][k]
 
                if j - 1 >= 0 and k - (ws[i] - ws[0]) >= 0:
                    dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j - 1][k - (ws[i] - ws[0])] + vs[i])
 
    ans = 0
 
    for j in range(N + 1):
        for k in range(3*N + 1):
            if ws[0]*j + k <= W:
                ans = max(ans, dp[N][j][k])
 
    print(ans)
 
if __name__ == '__main__':
    solve()

Fixed submission:
import sys

inf = 1 << 32

def solve():
    N, W = map(int, input().split())
    ws = []
    vs = []

    for i in range(N):
        wi, vi = map(int, input().split())
        ws.append(wi)
        vs.append(vi)

    dp = [[[-inf]*(3*N + 1) for j in range(N + 1)]
                              for i in range(N + 1)]

    dp[0][0][0] = 0

    for i in range(N):
        for j in range(N + 1):
            for k in range(3*N + 1):
                dp[i + 1][j][k] = dp[i][j][k]

                if j - 1 >= 0 and k - (ws[i] - ws[0]) >= 0:
                    dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j - 1][k - (ws[i] - ws[0])] + vs[i])

    ans = 0

    for j in range(N + 1):
        for k in range(3*N + 1):
            if ws[0]*j + k <= W:
                ans = max(ans, dp[N][j][k])

    print(ans)

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

def solve():
    def dfs1(u, path, visited):
        for w in Adj[u]:
            if not visited[w]:
                path.append(w)
                visited[w] = True
                dfs1(w, path, visited)
                return

    def dfs2(u, path, visited):
        for w in Adj[u]:
            if not visited[w]:
                path.appendleft(w)
                visited[w] = True
                dfs2(w, path, visited)
                return

    N, M = map(int, sys.stdin.readline().split())
    Adj = [[] for i in range(N)]

    for i in range(M):
        a, b = map(int, sys.stdin.readline().split())
        a, b = a-1, b-1
        Adj[a].append(b)
        Adj[b].append(a)

    if any(len(v) == 1 for v in Adj):
        for i, v in enumerate(Adj):
            if len(v) == 1:
                s = i
                break

        path = [s]
        visited = [False] * N
        visited[s] = True

        dfs1(s, path, visited)

        path = [i + 1 for i in path]

        print(len(path))
        print(*path)
    else:
        s = 0
        path = deque([0])

        visited = [False] * N
        visited[s] = True

        dfs1(s, path, visited)
        dfs2(s, path, visited)

        path = [i + 1 for i in path]

        print(len(path))
        print(*path)

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

if __name__ == '__main__':
    solve()

Fixed submission:
import sys
from collections import deque

sys.setrecursionlimit(10**7)

def solve():
    def dfs1(u, path, visited):
        for w in Adj[u]:
            if not visited[w]:
                path.append(w)
                visited[w] = True
                dfs1(w, path, visited)
                return

    def dfs2(u, path, visited):
        for w in Adj[u]:
            if not visited[w]:
                path.appendleft(w)
                visited[w] = True
                dfs2(w, path, visited)
                return

    N, M = map(int, sys.stdin.readline().split())
    Adj = [[] for i in range(N)]

    for i in range(M):
        a, b = map(int, sys.stdin.readline().split())
        a, b = a-1, b-1
        Adj[a].append(b)
        Adj[b].append(a)

    if any(len(v) == 1 for v in Adj):
        for i, v in enumerate(Adj):
            if len(v) == 1:
                s = i
                break

        path = [s]
        visited = [False] * N
        visited[s] = True

        dfs1(s, path, visited)

        path = [i + 1 for i in path]

        print(len(path))
        print(*path)
    else:
        s = 0
        path = deque([0])

        visited = [False] * N
        visited[s] = True

        dfs1(s, path, visited)
        dfs2(s, path, visited)

        path = [i + 1 for i in path]

        print(len(path))
        print(*path)

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

if __name__ == '__main__':
    solve()