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

input = sys.stdin.readline


def main():
    n = int(input())
    s = str(input())

    res = 0
    for i in range(1000):
        t = str(i).zfill(3)
        pos = 0
        for j in s:
            if t[pos] == j:
                pos += 1
            if pos == 3:
                res += 1
                break
    print(res)


if __name__ == '__main__':
    main()


Fixed submission:
n = int(input())
s = input()
ans = 0
for i in range(1000):
    t = str(i).zfill(3)
    ti = 0
    for j in range(n):
        if s[j] == t[ti]:
            ti += 1
            if ti == 3:
                break
    if ti == 3:
        ans += 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = str(input())

res = 0
for i in range(1000):
    t = str(i).zfill(3)
    pos = 0
    for j in s:
        if t[pos] == j:
            pos += 1
        if pos == 3:
            res += 1
            break

print(res)


Fixed submission:
n = int(input())
s = input()
ans = 0
for i in range(1000):
    t = str(i).zfill(3)
    ti = 0
    for j in range(n):
        if s[j] == t[ti]:
            ti += 1
            if ti == 3:
                break
    if ti == 3:
        ans += 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = input()
ans = 0
for i in range(1000):
    t = str(i).zfill(3)
    ti = 0
    for j in range(n):
        if s[j] == t[ti]:
            ti += 1
            if ti == 3:
                break
    if ti == 3:
        ans += 1
print(ans)


Fixed submission:
n = int(input())
s = input()
ans = 0
for i in range(1000):
    t = str(i).zfill(3)
    ti = 0
    for j in range(n):
        if s[j] == t[ti]:
            ti += 1
            if ti == 3:
                break
    if ti == 3:
        ans += 1
print(ans)

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

n = int(input())
s = input()
c = list(itertools.combinations(s,3))
l = len(set(c))
print(l)


Fixed submission:
n = int(input())
s = input()
ans = 0
for i in range(1000):
    t = str(i).zfill(3)
    ti = 0
    for j in range(n):
        if s[j] == t[ti]:
            ti += 1
            if ti == 3:
                break
    if ti == 3:
        ans += 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, t = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(n)]
    AB.sort()

    res = 0
    dp = [[0] * (t + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        a, b = AB[i - 1]
        for j in range(1, t + 1):
            if j - a >= 0:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - a] + b)
            else:
                dp[i][j] = dp[i - 1][j]
        for k in range(i, n):
            _, b = AB[k]
            res = max(res, dp[i][j - 1] + b)
    print(res)


if __name__ == '__main__':
    resolve()


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, t = map(int, input().split())
    AB = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x: x[0])

    res = 0
    dp = [[0] * (t + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        a, b = AB[i - 1]
        for j in range(1, t + 1):
            if j - a >= 0:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - a] + b)
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j])
        now = dp[i - 1][t - 1] + b
        res = max(res, now)

    print(res)


if __name__ == '__main__':
    resolve()

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

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, t = map(int, input().split())
    AB = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x: x[0])

    res = 0
    dp = [[0] * (t + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        a, b = AB[i - 1]
        for j in range(1, t + 1):
            if j - a >= 0:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - a] + b)
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j])
        now = dp[i - 1][t - 1] + b
        res = max(res, now)

    print(res)


if __name__ == '__main__':
    resolve()


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, t = map(int, input().split())
    AB = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x: x[0])

    res = 0
    dp = [[0] * (t + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        a, b = AB[i - 1]
        for j in range(1, t + 1):
            if j - a >= 0:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - a] + b)
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j])
        now = dp[i - 1][t - 1] + b
        res = max(res, now)

    print(res)


if __name__ == '__main__':
    resolve()
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
divisors = []
for i in range(1, int(pow(n, 0.5)) + 1):
    if n % i == 0:
        divisors.append([i, n // i])
    divisors = sorted(divisors, key= lambda x:x[1])
res = 0
for i in divisors[0]:
    res += i - 1

print(res)

Fixed submission:
import math

n = int(input())
divisors = []
for i in range(1, int(n**0.5) +1):
    if n % i == 0:
        divisors.append(i)
        if i != n // i:
            divisors.append(n//i)

ans = math.pow(10, 12)
tmp = 0
for i in divisors:
    j = n / i
    tmp = i + j -2
    if tmp < ans:
        ans = tmp

print(int(ans))

Buggy python submission (verdict: Runtime Error):
n = int(input())
divisors = []
for i in range(1, int(pow(n, 0.5)) + 1):
    if n % i == 0:
        if i != n // i:
            divisors.append([i, n // i])
        else:
            divisors.append([i])
divisors = sorted(divisors, key= lambda x:x[1])
res = divisors[0][0] - 1 + divisors[0][1] - 1
print(res)

Fixed submission:
import math

n = int(input())
divisors = []
for i in range(1, int(n**0.5) +1):
    if n % i == 0:
        divisors.append(i)
        if i != n // i:
            divisors.append(n//i)

ans = math.pow(10, 12)
tmp = 0
for i in divisors:
    j = n / i
    tmp = i + j -2
    if tmp < ans:
        ans = tmp

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

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    def meguru_bisect(is_ok, left, right):
        """
        :param is_ok: 定義して下さい
        :param left: 取りうる最小の値-1
        :param right: 取りうる最大の値+1
        :return: is_okを満たす最小(もしくは最大)の値
        """
        while abs(left - right) > 1:
            mid = (left + right) // 2
            if is_ok(mid):
                right = mid
            else:
                left = mid
        return right

    def is_ok(x):
        total = 0
        for i in range(n):
            total += max(0, A[i] - x // F[i])
        return total <= k

    n, k = map(int, input().split())
    A = sorted(list(map(int, input().split())))
    F = sorted(list(map(int, input().split())), reverse=True)

    left = -1
    right = 10 ** 12 + 1
    res = meguru_bisect(is_ok, left, right)
    print(res)


if __name__ == '__main__':
    resolve()


Fixed submission:
import numpy as np

n, k = map(int, input().split())
a = np.array(input().split(), np.int64)
f = np.array(input().split(), np.int64)
a.sort()
f.sort()
a = a[::-1]
left = -1
right = np.max(a * f)
while left + 1 < right:
    mid = (left + right) // 2
    if np.sum(np.maximum(a - mid // f, 0)) <= k:
        right = mid
    else:
        left = mid

print(right)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
l_list = list(int(i) for i in input().split())
list.sort(l_list, reverse=True)
count = 0
for i in range(n):
    a = l_list[i]
    for j in range(i+1, n):
        b = l_list[j]
        for k in range(j+1, n):
            c = l_list[k]
            if a < b + c and b < c + a and c < a + b:
                count += 1
            else:
                break
print(count)

Fixed submission:
import bisect

n = int(input())
l = list(int(i) for i in input().split())
list.sort(l)
count = 0

for i in range(n):
    a = l[i]
    for j in range(i+1, n):
        b = l[j]
        ab = a + b
        index_c = bisect.bisect_left(l, ab)
        count += index_c - j -1

print(count)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
l_list = list(int(i) for i in input().split())
list.sort(l_list, reverse=True)
count = 0
for i in range(n):
    a = l_list[i]
    for j in range(i+1, n):
        b = l_list[j]
        for k in range(j+1, n):
            c = l_list[k]
            if a < b + c and b < c + a and c < a + b:
                count += 1
            else:
                break
print(count)


Fixed submission:
import bisect

n = int(input())
l = list(int(i) for i in input().split())
list.sort(l)
count = 0

for i in range(n):
    a = l[i]
    for j in range(i+1, n):
        b = l[j]
        ab = a + b
        index_c = bisect.bisect_left(l, ab)
        count += index_c - j -1

print(count)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
l_list = list(int(i) for i in input().split())
list.sort(l_list, reverse=True)
count = 0
for i in range(n):
    a = l_list[i]
    for j in range(i+1, n):
        b = l_list[j]
        for k in range(j+1, n):
            c = l_list[k]
            if a < b+c and b < c+a and c < a+b:
                count += 1
print(count)


Fixed submission:
import bisect

n = int(input())
l = list(int(i) for i in input().split())
list.sort(l)
count = 0

for i in range(n):
    a = l[i]
    for j in range(i+1, n):
        b = l[j]
        ab = a + b
        index_c = bisect.bisect_left(l, ab)
        count += index_c - j -1

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

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    def dfs(start, v, p, tot_d):
        for d, u in edge[v]:
            if u == p:
                continue
            if tot_d + d > l:
                dp[start][u] = min(dp[start][u], dp[start][v] + 1)
                tot_d = d
            else:
                dp[start][u] = min(dp[start][u], dp[start][v])
                tot_d += d
            dfs(start, u, v, tot_d)

    n, m, l = map(int, input().split())
    edge = [[] for _ in range(n)]
    for _ in range(m):
        a, b, c = map(int, input().split())
        if c > l:
            continue
        edge[a - 1].append([c, b - 1])
        edge[b - 1].append([c, a - 1])

    # dp[i][j]:iからスタートしてjに行くまでに補給する最小回数
    dp = [[f_inf] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 0
        dfs(i, i, - 1, 0)

    q = int(input())
    for _ in range(q):
        s, t = map(int, input().split())
        dp[s - 1][t - 1] = min(dp[s - 1][t - 1], dp[t - 1][s - 1])
        if dp[s - 1][t - 1] == f_inf:
            print(-1)
        else:
            print(dp[s - 1][t - 1])
            

if __name__ == '__main__':
    resolve()


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m, l = map(int, input().split())
    cost = [[f_inf] * n for _ in range(n)]
    for i in range(n):
        cost[i][i] = 0
    for _ in range(m):
        a, b, c = map(int, input().split())
        cost[a - 1][b - 1] = c
        cost[b - 1][a - 1] = c

    for k in range(n):
        for i in range(n):
            for j in range(n):
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])

    res = [[f_inf] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if cost[i][j] <= l:
                res[i][j] = 1

    for k in range(n):
        for i in range(n):
            for j in range(n):
                res[i][j] = min(res[i][j], res[i][k] + res[k][j])

    q = int(input())
    for _ in range(q):
        s, t = map(int, input().split())
        print(-1 if res[s - 1][t - 1] == f_inf else res[s - 1][t - 1] - 1)


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

a, b = map(int, input().split())
g = math.gcd(a, b)
g_2 = int(math.sqrt(g))
cnt = 1

for i in range(2, g_2+1):
    if g % i == 0:
        while g % i == 0:
            g //= i
        cnt += 1
if g > 1:
    cnt += 1

print(cnt)

Fixed submission:
import math

def gcd(n, m):
    while m != 0:
        n, m = m, n % m
    return n

a, b = map(int, input().split())
g = gcd(a, b)
g_2 = int(math.sqrt(g))
cnt = 1

for i in range(2, g_2+1):
    if g % i == 0:
        while g % i == 0:
            g //= i
        cnt += 1
if g > 1:
    cnt += 1

print(cnt)

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

a, b = map(int, input().split())
x = math.gcd(a, b)
k = []
for i in range(1, x+1):
    if x % i == 0:
        k.append(i)
cnt = 0
for n in k:
    if n == 1:
        cnt += 1
    elif n == 2:
        cnt += 1
    else:
        flg = ""
        for p in range(2, n):
            if n % p == 0:
                flg = "composite"
                break
            else:
                flg = "prime"
        if flg == "prime":
            cnt += 1
print(cnt)


Fixed submission:
import math

def gcd(n, m):
    while m != 0:
        n, m = m, n % m
    return n

a, b = map(int, input().split())
g = gcd(a, b)
g_2 = int(math.sqrt(g))
cnt = 1

for i in range(2, g_2+1):
    if g % i == 0:
        while g % i == 0:
            g //= i
        cnt += 1
if g > 1:
    cnt += 1

print(cnt)

Buggy python submission (verdict: Time Limit Exceeded):
a, b = map(int, input().split())
k = []
for i in range(1, min(a, b)+1):
    if a % i == 0 and b % i == 0:
        k.append(i)
cnt = 0
for n in k:
    if n == 1:
        cnt += 1
    elif n == 2:
        cnt += 1
    else:
        flg = ""
        for p in range(2, n):
            if n % p == 0:
                flg = "composite"
                break
            else:
                flg = "prime"
        if flg == "prime":
            cnt += 1
print(cnt)


Fixed submission:
import math

def gcd(n, m):
    while m != 0:
        n, m = m, n % m
    return n

a, b = map(int, input().split())
g = gcd(a, b)
g_2 = int(math.sqrt(g))
cnt = 1

for i in range(2, g_2+1):
    if g % i == 0:
        while g % i == 0:
            g //= i
        cnt += 1
if g > 1:
    cnt += 1

print(cnt)
Buggy python submission (verdict: Runtime Error):
H,W,A,B = map(int,input().split())
matrix = [[0 for i in range(H)] for j in range(W)]

if A ==  B == 1:
    for i in range(W):
        matrix[i][i] = 1
elif A == B:
    for i in range(H):
        for j in range(W):
            if (i + j) % 2 == 0:
                matrix[i][j] = 1
elif H == 1 and B == 0:
    for i in range(W):
        if i % 2 != 0:
            matrix[0][i] = 1
elif W == 1 and A == 0:
    for i in range(H):
        if i % 2 != 0:
            matrix[i][0] = 1
else:
    print("No")
    exit()

for i in range(W):
        print(''.join(map(str,matrix[i])))

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

for i in range(H):
    if i < B:
        print("1"*A + "0"*(W-A))
    else:
        print("0"*A + "1"*(W-A))
Buggy python submission (verdict: Time Limit Exceeded):
N,K,Q = map(int,input().split())
A = [input() for i in range(Q)]
score = []
for i in range(N):
    score.append(K)

for i in A:
    for j in range(N):
        if int(i) != j+1:
            score[j] -= 1
        else:
            pass

for i in range(N):
    if score[i] <= 0:
        print("No")
    else:
        print("Yes")

Fixed submission:
N,K,Q = map(int,input().split())
A = [int(input()) for i in range(Q)]
score = []
for i in range(N):
    score.append(K-Q)

for i in A:
    score[i-1] += 1

for i in range(N):
    if score[i] <= 0:
        print("No")
    else:
        print("Yes")
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
m = 0

for i in range(n):
	if i == n:
		pass
	else:
		m += i

print(m)

Fixed submission:
n = int(input())
ans = 0

if n == 2:
    ans = 1
elif n % 2 != 0:
    ans = n * (n // 2)
else:
    ans = n * (n // 2 - 1) + n // 2

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    A = []
    for _ in range(n):
        t = deque(list((map(lambda x: int(x) - 1, input().split()))))
        A.append(t)

    res = 0
    emp = [1] * n
    while True:
        check = [0] * n
        for i in range(n):
            if A[i] and not check[i]:
                idx = A[i][0]
                if not check[idx] and A[idx][0] == i:
                    A[i].popleft()
                    A[idx].popleft()
                    check[i] = check[idx] = 1
            if not A[i]:
                emp[i] = 0
        res += 1
        if sum(emp) == 0:
            break
        if sum(check) == 0:
            print(-1)
            exit()
    print(res)





if __name__ == '__main__':
    resolve()


Fixed submission:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    A = []
    for _ in range(n):
        t = deque(list((map(lambda x: int(x) - 1, input().split()))))
        A.append(t)

    que = deque(list(range(n)))
    res = 0
    emp = [False] * n
    while que:
        next_que = deque([])
        check = set()
        while que:
            i = que.popleft()
            if A[i]:
                idx = A[i][0]
                if i not in check and idx not in check and A[idx][0] == i:
                    A[i].popleft()
                    A[idx].popleft()
                    next_que.append(i)
                    next_que.append(idx)
                    check.add(i)
                    check.add(idx)
            else:
                emp[i] = True
        que = next_que
        if que:
            res += 1
    else:
        print(res if all(emp) else -1)


if __name__ == '__main__':
    resolve()
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
import heapq

flg = False
n, m = map(int, input().split())
jobs = [[] for i in range(m)]
for i in range(n):
    a, b = map(int, input().split())
    if a > m and flg == False:
        jobs[m - a].append(b)
    else:
        flg = True
        jobs[m - a].append(b)

if flg == False:
    print(0)
    exit(0)

q = []
heapq.heapify(q)
ans = 0
for i in reversed(range(m)):
    for b in jobs[i]:
        heapq.heappush(q, -b)
    if len(q) != 0:
        ans += heapq.heappop(q) * -1

print(ans)


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

n, m = map(int, input().split())
jobs = [[] for i in range(m)]
for i in range(n):
    a, b = map(int, input().split())
    if a > m:
        pass
    else:
        jobs[m - a].append(b)

if len(jobs) == 0:
    print(0)
    exit(0)

q = []
heapq.heapify(q)
ans = 0
for i in reversed(range(m)):
    for b in jobs[i]:
        heapq.heappush(q, -b)
    if len(q) != 0:
        ans += heapq.heappop(q) * -1

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

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    s = input()
    L = len(s)
    dp = [[0] * 13 for _ in range(L + 1)]
    dp[0][0] = 1

    for i in range(L):
        for j in range(13):
            if s[i] == "?":
                for k in range(10):
                    dp[i + 1][(j * 10 + k) % 13] += dp[i][j] % mod
            else:
                k = int(s[i])
                dp[i + 1][(j * 10 + k) % 13] += dp[i][j] % mod

    print(dp[-1][5] % mod)


if __name__ == '__main__':
    resolve()


Fixed submission:
s = input()
L = len(s)
MOD = 10 ** 9 + 7
dp = [[0 for _ in range(13)] for _ in range(L + 1)]
dp[0][0] = 1

for i in range(1, L + 1):
    if s[i - 1] == "?":
        for j in range(10):
            for k in range(13):
                dp[i][(k * 10 + j) % 13] += dp[i - 1][k] % MOD
    else:
        for k in range(13):
            dp[i][(k * 10 + int(s[i - 1])) % 13] += dp[i - 1][k] % MOD

print(dp[-1][5] % MOD)

Buggy python submission (verdict: Time Limit Exceeded):
s=input()
l=len(s)
mod=10**9+7
dp=[[0 for j in range(13)] for i in range(l+1)]
dp[0][0]=1
for i in range(1,l+1):
  if s[i-1]=='?':
    for j in range(10):
      for k in range(13):
        dp[i][(k*10+j)%13]+=dp[i-1][k]%mod
  else:
    for k in range(13):
      dp[i][(k*10+int(s[i-1]))%13]+=dp[i-1][k]%mod
print(dp[-1][5]%mod)

Fixed submission:
s = input()
L = len(s)
MOD = 10 ** 9 + 7
dp = [[0 for _ in range(13)] for _ in range(L + 1)]
dp[0][0] = 1

for i in range(1, L + 1):
    if s[i - 1] == "?":
        for j in range(10):
            for k in range(13):
                dp[i][(k * 10 + j) % 13] += dp[i - 1][k] % MOD
    else:
        for k in range(13):
            dp[i][(k * 10 + int(s[i - 1])) % 13] += dp[i - 1][k] % MOD

print(dp[-1][5] % MOD)

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
l = len(s)
MOD = 10 ** 9 + 7
dp = [[0 for _ in range(13)] for _ in range(l+1)]
dp[0][0] = 1

for i in range(1, l + 1):
    if s[i-1] =="?":
        for j in range(10):
            for k in range(13):
                dp[i][(k * 10 + j) % 13] += dp[i - 1][k] % MOD
    else:
        for k in range(13):
            dp[i][(k * 10 + int(s[i - 1])) % 13] += dp[i - 1][k] % MOD

print(dp[-1][5] % MOD)


Fixed submission:
s = input()
L = len(s)
MOD = 10 ** 9 + 7
dp = [[0 for _ in range(13)] for _ in range(L + 1)]
dp[0][0] = 1

for i in range(1, L + 1):
    if s[i - 1] == "?":
        for j in range(10):
            for k in range(13):
                dp[i][(k * 10 + j) % 13] += dp[i - 1][k] % MOD
    else:
        for k in range(13):
            dp[i][(k * 10 + int(s[i - 1])) % 13] += dp[i - 1][k] % MOD

print(dp[-1][5] % MOD)