Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import sys
from functools import lru_cache


fin = sys.stdin.readline
num_matches_required = {n: nmatches for n, nmatches 
    in zip(range(1, 10), (2, 5, 5, 4, 5, 6, 3, 7, 6))}

N, M = map(int, fin().split())
nums = sorted(map(int, fin().split()), reverse=True)

@lru_cache(None)
def rec(i):
    if i < 0: 
        return float('-inf')
    elif i == 0: 
        return 0
    else:
        return max(
            rec(i - num_matches_required[num]) for num in nums
        ) + 1


num_digits = rec(N)
cur_num_matches = N
result = []
while cur_num_matches:
    for num in nums:
        if rec(cur_num_matches - num_matches_required[num]) == num_digits - len(result) - 1:
            result.append(str(num))
            cur_num_matches -= num_matches_required[num]
            break

print("".join(result))


Fixed submission:
import sys
from functools import lru_cache


sys.setrecursionlimit(200000)
fin = sys.stdin.readline
num_matches_required = {n: nmatches for n, nmatches 
    in zip(range(1, 10), (2, 5, 5, 4, 5, 6, 3, 7, 6))}

N, M = map(int, fin().split())
nums = sorted(map(int, fin().split()), reverse=True)

@lru_cache(None)
def rec(i):
    if i < 0: 
        return float('-inf')
    elif i == 0: 
        return 0
    else:
        return max(
            rec(i - num_matches_required[num]) for num in nums
        ) + 1


num_digits = rec(N)
cur_num_matches = N
result = []
while cur_num_matches:
    for num in nums:
        if rec(cur_num_matches - num_matches_required[num]) == num_digits - len(result) - 1:
            result.append(str(num))
            cur_num_matches -= num_matches_required[num]
            break

print("".join(result))
Buggy python submission (verdict: Runtime Error):
import sys
fin = sys.stdin.readline


N, M = [int(elem) for elem in fin().split()]
adj = [[] for _ in range(N)]

for _ in range(N + M - 1):
    u, v = [int(elem) - 1 for elem in fin().split()]
    adj[u].append(v)

inv_adj = [[] for _ in range(N)]
for u, neighbors in enumerate(adj):
    for v in neighbors:
        inv_adj[v].append(u)

topo = []
visited = [False] * N

def dfs_visit(node):
    for neighbor in adj[node]:
        if visited[neighbor]:
            continue
        visited[neighbor] = True
        dfs_visit(neighbor)
    topo.append(node)
    return

for node in range(N):
    if not visited[node]:
        visited[node] = True
        dfs_visit(node)

topo = topo[::-1]

parent = [-1] * N
order = dict()
order[topo[0]] = 0
for number, node in enumerate(topo[1:], start=1):
    neighbors = inv_adj[node]
    correct_parent = -1
    for neighbor in neighbors:
        if neighbor in order and order[neighbor] > correct_parent:
            correct_parent = order[neighbor]
    parent[node] = correct_parent
    order[node] = number

order_to_number = {v: k + 1 for k, v in order.items()}
order_to_number[-1] = 0

for i in range(N):
    print(order_to_number[parent[i]])

Fixed submission:
import sys
fin = sys.stdin.readline
sys.setrecursionlimit(500000)

N, M = [int(elem) for elem in fin().split()]
adj = [[] for _ in range(N)]

for _ in range(N + M - 1):
    u, v = [int(elem) - 1 for elem in fin().split()]
    adj[u].append(v)

inv_adj = [[] for _ in range(N)]
for u, neighbors in enumerate(adj):
    for v in neighbors:
        inv_adj[v].append(u)

topo = []
visited = [False] * N

def dfs_visit(node):
    for neighbor in adj[node]:
        if visited[neighbor]:
            continue
        visited[neighbor] = True
        dfs_visit(neighbor)
    topo.append(node)
    return

for node in range(N):
    if not visited[node]:
        visited[node] = True
        dfs_visit(node)

topo = topo[::-1]

parent = [-1] * N
order = dict()
order[topo[0]] = 0
for number, node in enumerate(topo[1:], start=1):
    neighbors = inv_adj[node]
    correct_parent = -1
    for neighbor in neighbors:
        if neighbor in order and order[neighbor] > correct_parent:
            correct_parent = order[neighbor]
    parent[node] = correct_parent
    order[node] = number

order_to_number = {v: k + 1 for k, v in order.items()}
order_to_number[-1] = 0

for i in range(N):
    print(order_to_number[parent[i]])
Buggy python submission (verdict: Runtime Error):
import sys
fin = sys.stdin.readline


N, M = [int(elem) for elem in fin().split()]
adj = [[] for _ in range(N)]
for _ in range(M):
    x, y = [int(elem) - 1 for elem in fin().split()]
    adj[x].append(y)

visited = [False] * N
topo_order = []
# topological sort by DFS
def dfs_visit(node):
    for neighbor in adj[node]:
        if not visited[neighbor]:
            dfs_visit(neighbor)
    topo_order.append(node)


for node in range(N):
    dfs_visit(node)
topo_order = topo_order[::-1]

dp = [0] * N
for node in topo_order[:-1]:
    for neighbor in adj[node]:
        dp[neighbor] = max(dp[neighbor], dp[node] + 1)

print(max(dp))


Fixed submission:
import sys
sys.setrecursionlimit(300000)
fin = sys.stdin.readline


N, M = [int(elem) for elem in fin().split()]
adj = [[] for _ in range(N)]
for _ in range(M):
    x, y = [int(elem) - 1 for elem in fin().split()]
    adj[x].append(y)

visited = [False] * N
topo_order = []
# topological sort by DFS
def dfs_visit(node):
    visited[node] = True
    for neighbor in adj[node]:
        if not visited[neighbor]:
            dfs_visit(neighbor)
    topo_order.append(node)


for node in range(N):
    dfs_visit(node)
topo_order = topo_order[::-1]

dp = [0] * N
for node in topo_order[:-1]:
    for neighbor in adj[node]:
        dp[neighbor] = max(dp[neighbor], dp[node] + 1)

print(max(dp))
Buggy python submission (verdict: Time Limit Exceeded):
from math import sqrt, floor
from itertools import combinations
N = int(input())

ans_root = sqrt(1 + 8 * N)
if (1 + 8 * N) - floor(ans_root) ** 2 > 1e-6:
    print("No")
    exit(0)

k = floor((1 + ans_root) // 2)
transposed_flags = [[False] * k for _ in range(N)]
for i, (flag1, flag2) in enumerate(combinations(range(k), 2)):
    transposed_flags[i][flag1] = True
    transposed_flags[i][flag2] = True

print("Yes")
print(k)
for flags in zip(*transposed_flags):
    number_contained = [str(i + 1) for i, flag in enumerate(flags) if flag]
    print(len(number_contained), " ".join(number_contained))


Fixed submission:
from math import sqrt, floor
from itertools import combinations
from collections import defaultdict
N = int(input())

ans_root = sqrt(1 + 8 * N)
if (1 + 8 * N) - floor(ans_root) ** 2 > 1e-6:
    print("No")
    exit(0)

k = floor((1 + ans_root) // 2)
result = defaultdict(list)
for i, (flag1, flag2) in enumerate(combinations(range(k), 2), start=1):
    result[flag1].append(str(i))
    result[flag2].append(str(i))

print("Yes")
print(k)
for value in result.values():
    print(len(value), " ".join(value))
Buggy python submission (verdict: Runtime Error):
import sys
fin = sys.stdin.readline


def factorial(n, mod):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1, mod) % mod


MOD = 10**9 + 7
N = int(fin())
A_list = [int(elem) for elem in fin().split()]

fac_N = factorial(N, MOD)
inv_nums = [fac_N * pow(i, MOD - 2, MOD) % MOD for i in range(1, N + 1)]
cuml_inv_nums = [inv_nums[0]]
for inv_num in inv_nums[1:]:
    cuml_inv_nums.append((cuml_inv_nums[-1] + inv_num) % MOD)

ans = 0
for i, A in enumerate(A_list):
    ans += A * (cuml_inv_nums[i] + cuml_inv_nums[N - 1 - i] - cuml_inv_nums[0]) % MOD
    ans %= MOD

print(ans)


Fixed submission:
import sys
fin = sys.stdin.readline
sys.setrecursionlimit(200000)

def factorial(n, mod):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1, mod) % mod


MOD = 10**9 + 7
N = int(fin())
A_list = [int(elem) for elem in fin().split()]

fac_N = factorial(N, MOD)
inv_nums = [fac_N * pow(i, MOD - 2, MOD) % MOD for i in range(1, N + 1)]
cuml_inv_nums = [inv_nums[0]]
for inv_num in inv_nums[1:]:
    cuml_inv_nums.append((cuml_inv_nums[-1] + inv_num) % MOD)

ans = 0
for i, A in enumerate(A_list):
    ans += A * (cuml_inv_nums[i] + cuml_inv_nums[N - 1 - i] - cuml_inv_nums[0]) % MOD
    ans %= MOD

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
S = input()
T = input()

S_indices_dict = defaultdict(set)
T_indices_dict = defaultdict(set)

for i, char in enumerate(S):
    S_indices_dict[char].add(i)
for i, char in enumerate(T):
    T_indices_dict[char].add(i)

indices_set = set(range(len(S)))
for char in S:
    indices = S_indices_dict[char]
    char_set = set()
    for i in indices:
        char_set.add(T[i])
        if len(char_set) != 1:
            print("No")
            exit(0)
for char in T:
    indices = T_indices_dict[char]
    char_set = set()
    for i in indices:
        char_set.add(S[i])
    if len(char_set) != 1:
        print("No")
        exit(0)
print("Yes")


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


S = fin()[:-1]
T = fin()[:-1]

correspondence = dict()
for char_s, char_t in zip(S, T):
    if char_s not in correspondence:
        correspondence[char_s] = char_t
    else:
        if char_t != correspondence[char_s]:
            print("No")
            exit(0)
if len(set(correspondence.values())) < len(correspondence):
    print("No")
else:
    print("Yes")
Buggy python submission (verdict: Runtime Error):
def num_divisors(n):
  res = 0
  i = 2
  while i * i <= n:
    if n % i == 0:
      res += 1
      res += 1 if i * i != n else 0
    i += 1
  return res


N = input()
res = 0
for n in range(1, N + 1):
  if num_divisors(n) == 8:
    res += 1
print(res)


Fixed submission:
def num_divisors(n):
  res = 0
  i = 1
  while i * i <= n:
    if n % i == 0:
      res += 1
      res += 1 if i * i != n else 0
    i += 1
  return res


N = int(input())
res = 0
for n in range(1, N + 1, 2):
  if num_divisors(n) == 8:
    res += 1
print(res)
Buggy python submission (verdict: Time Limit Exceeded):
from copy import deepcopy

N, M, Q = [int(elem) for elem in input().split(' ')]
lines = [[int(elem) for elem in input().split(' ')] for _ in range(M)]
queries = [[int(elem) for elem in input().split(' ')] for _ in range(Q)]


def cuml_1d(N, lines, queries):
    coords = [[0] * N for _ in range(N)]
    for l, r in lines:
        coords[l - 1][r - 1] += 1

    cuml_coords = deepcopy(coords)
    for l in range(N):
        for r in range(1, N):
            cuml_coords[l][r] = cuml_coords[l][r - 1] + coords[l][r]

    for query in queries:
        p, q = query[0] - 1, query[1] - 1
        num_lines = 0
        for l in range(p, max(q + 1, N)):
            if p == 0:
                num_lines += cuml_coords[l][q]
            else:
                num_lines += cuml_coords[l][q] - cuml_coords[l][p - 1]
        print(num_lines)

cuml_1d(N, lines, queries)


Fixed submission:
from copy import deepcopy

N, M, Q = [int(elem) for elem in input().split(' ')]
lines = [[int(elem) for elem in input().split(' ')] for _ in range(M)]
queries = [[int(elem) for elem in input().split(' ')] for _ in range(Q)]


def cuml_1d(N, lines, queries):
    coords = [[0] * N for _ in range(N)]
    for l, r in lines:
        coords[l - 1][r - 1] += 1

    cuml_coords = deepcopy(coords)
    for l in range(N):
        for r in range(1, N):
            cuml_coords[l][r] = cuml_coords[l][r - 1] + coords[l][r]

    for query in queries:
        p, q = query[0] - 1, query[1] - 1
        num_lines = 0
        for l in range(p, max(q + 1, N)):
            if p == 0:
                num_lines += cuml_coords[l][q]
            else:
                num_lines += cuml_coords[l][q] - cuml_coords[l][p - 1]
        print(num_lines)

cuml_1d(N, lines, queries)
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import permutations
from math import ceil, floor

D, G = [int(elem) for elem in input().split(' ')]
point_info_list = [[int(elem) for elem in input().split()] for _ in range(D)]
assert len(point_info_list) == D
assert len(point_info_list[0]) == 2

min_num = float('inf')
for perm in permutations(range(D)):
    current_point = 0
    current_num = 0
    for point in perm:
        if (G - current_point) - (point + 1) * 100 * point_info_list[point][0] <= 0:
            current_num += ceil((G - current_point) / ((point + 1) * 100))
            break
        elif (G - current_point) - (point + 1) * 100 * point_info_list[point][0] - point_info_list[point][1] <= 0:
            current_num += point_info_list[point][0]
            break
        else:
            current_point += (point + 1) * 100 * point_info_list[point][0] + point_info_list[point][1]
            current_num += point_info_list[point][0]
    min_num = min(current_num, min_num)

print(min_num)


Fixed submission:
from itertools import permutations
from math import ceil, floor

D, G = [int(elem) for elem in input().split(' ')]
point_info_list = [[int(elem) for elem in input().split()] for _ in range(D)]
assert len(point_info_list) == D
assert len(point_info_list[0]) == 2

min_num = float('inf')
for perm in permutations(range(D)):
    current_point = 0
    current_num = 0
    for point in perm:
        if (G - current_point) - (point + 1) * 100 * point_info_list[point][0] <= 0:
            current_num += ceil((G - current_point) / ((point + 1) * 100))
            break
        elif (G - current_point) - (point + 1) * 100 * point_info_list[point][0] - point_info_list[point][1] <= 0:
            current_num += point_info_list[point][0]
            break
        else:
            current_point += (point + 1) * 100 * point_info_list[point][0] + point_info_list[point][1]
            current_num += point_info_list[point][0]
    min_num = min(current_num, min_num)

print(min_num)
Buggy python submission (verdict: Runtime Error):
from itertools import permutations

N, C = [int(elem) for elem in input().split(' ')]
D_matrix = [[int(elem) for elem in input().split(' ')] for _ in range(C)]
assert len(D_matrix) == C
assert len(D_matrix[0]) == C
c_matrix = [[int(elem) for elem in input().split(' ')] for _ in range(N)]
assert len(c_matrix) == N
assert len(c_matrix[0]) == N

# grouping
# O(N^2)
mod_list = [[] for _ in range(3)]
for i in range(N):
    for j in range(N):
        mod_list[(i + j) % 3].append((i, j))

# O(N^2)
mod_color_list = [[0] * C for _ in range(3)]
for k, mod in enumerate(mod_list):
    for i, j in mod:
        mod_color_list[k][c_matrix[i][j] - 1] += 1

# O(C^3 * N^2) -> O(C^4)
min_cost = float('inf')
for colors in permutations(range(C), 3):
    total_cost = 0
    for color, mod_color in zip(colors, mod_color_list):
        total_cost += sum([D_matrix[X][color] * mod_color[X] for X in range(C)])
    min_cost = min(min_cost, total_cost)

print(min_cost)


Fixed submission:
N = int(input())

if N < 1000:
    print("ABC")
else:
    print("ABD")
Buggy python submission (verdict: Runtime Error):
def brute_force(s, K):
    substring_set = set()

    # brute-force
    for start in range(len(s)):
        # 5まででよかった...
        for length in range(1, 6):
            substring = s[start:start+length]
            substring_set.add(substring)

    substring_list = sorted(list(substring_set))
    print(substring_list)
    print(substring_list[K - 1])

brute_force(s, K)

Fixed submission:
s = input()
K = int(input())


def brute_force(s, K):
    substring_set = set()

    # brute-force
    for start in range(len(s)):
        # 5まででよかった...
        for length in range(1, 6):
            substring = s[start:start+length]
            substring_set.add(substring)

    substring_list = sorted(list(substring_set))
    print(substring_list[K - 1])

brute_force(s, K)

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


def brute_force(s, K):
    substring_set = set()

    # brute-force
    for start in range(len(s)):
        # 5まででよかった...
        for length in range(len(s) - start + 1):
            if length == 0:
                substring = s[start]
            else:
                substring = s[start:start+length]
            substring_set.add(substring)
            if length == 4:
                break

    substring_list = sorted(list(substring_set))
    print(substring_list[K - 1])

brute_force(s, K)

Fixed submission:
s = input()
K = int(input())


def brute_force(s, K):
    substring_set = set()

    # brute-force
    for start in range(len(s)):
        # 5まででよかった...
        for length in range(1, 6):
            substring = s[start:start+length]
            substring_set.add(substring)

    substring_list = sorted(list(substring_set))
    print(substring_list[K - 1])

brute_force(s, K)
Buggy python submission (verdict: Runtime Error):
N = int(input())

# O(num^(1/2))
def is_prime_num(num):
    num_sqrted = floor(sqrt(num))
    for i in range(2, num_sqrted + 1):
        if num % i == 0:
            return False
    else:
        return True

a_set = set()
while len(a_set) < N:
    for i in range(11, 55555, 10):
        if i in a_set:
            continue
        elif not is_prime_num(i):
            continue
        else:
            a_set.add(i)
            break

print(' '.join(map(str, a_set)))

Fixed submission:
from math import sqrt, floor, ceil
from itertools import combinations


N = int(input())

# O(num^(1/2))
def is_prime_num(num):
    num_sqrted = floor(sqrt(num))
    for i in range(2, num_sqrted + 1):
        if num % i == 0:
            return False
    else:
        return True

a_set = set()
while len(a_set) < N:
    for i in range(11, 55555, 10):
        if i in a_set:
            continue
        elif not is_prime_num(i):
            continue
        else:
            a_set.add(i)
            break

print(' '.join(map(str, a_set)))

Buggy python submission (verdict: Runtime Error):
a_set = set()
while len(a_set) < N:
    for i in range(11, 55555, 10):
        if i in a_set:
            continue
        elif not is_prime_num(i):
            continue
        else:
            a_set.add(i)
            break

print(' '.join(map(str, a_set)))

Fixed submission:
from math import sqrt, floor, ceil
from itertools import combinations


N = int(input())

# O(num^(1/2))
def is_prime_num(num):
    num_sqrted = floor(sqrt(num))
    for i in range(2, num_sqrted + 1):
        if num % i == 0:
            return False
    else:
        return True

a_set = set()
while len(a_set) < N:
    for i in range(11, 55555, 10):
        if i in a_set:
            continue
        elif not is_prime_num(i):
            continue
        else:
            a_set.add(i)
            break

print(' '.join(map(str, a_set)))
Buggy python submission (verdict: Runtime Error):
import sys


fin = sys.stdin.readline
n = int(fin())
a_list = sorted(int(elem) for elem in fin().split())

num_elems = a_list[-1]
num_choices = -1
max_diff = float('-inf')
for a in a_list[:-1]:
    diff = min(num_elems - a, a)
    if diff > max_diff:
        num_choices = a
        max_diff = diff

print(num_elems, num_choices)


Fixed submission:
A, B, X = [int(elem) for elem in input().split()]

if X < A:
    print("NO")
elif X > A + B:
    print("NO")
else:
    print("YES")
Buggy python submission (verdict: Runtime Error):
A, B, C = map(int, input())
print("Yes" if A + B >= C else "No")


Fixed submission:
A, B, C = map(int, input().split())
print("Yes" if A + B >= C else "No")

Buggy python submission (verdict: Runtime Error):
A, B, C = map(input(), int)
print("Yes" if A + B >= C else "No")

Fixed submission:
A, B, C = map(int, input().split())
print("Yes" if A + B >= C else "No")
Buggy python submission (verdict: Runtime Error):
X, Y = input().split()
if X = Y:
  res = "="
elif X < Y:
  res = "<"
else:
  res = ">"
print(res)


Fixed submission:
X, Y = input().split()
if X == Y:
  res = "="
elif X < Y:
  res = "<"
else:
  res = ">"
print(res)
Buggy python submission (verdict: Time Limit Exceeded):
# time complexity: O(N^3 + R!)
# space complexity: O(N^2)

import sys
fin = sys.stdin.readline
from itertools import permutations


def warshall_floyd_int(adj, w):
    num_vertices = len(adj)
    dp = [[float('inf')] * num_vertices for _ in range(num_vertices)]
    for u in range(num_vertices):
        dp[u][u] = 0
        for v in adj[u]:
            dp[u][v] = w[u][v]

    for k in range(num_vertices):
        for i in range(num_vertices):
            for j in range(num_vertices):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
    return dp


N, M, R = [int(elem) for elem in fin().split()]
r_list = [int(elem) - 1 for elem in fin().split()]
assert len(r_list) == R

adj = [[] for _ in range(N)]
w = [[None] * N for _ in range(N)]

for _ in range(M):
    A, B, C = [int(elem) for elem in fin().split()]
    A -= 1
    B -= 1
    adj[A].append(B)
    adj[B].append(A)
    w[A][B] = C
    w[B][A] = C

# calculate the shortest distance between any pair of vertices
shortest_distances = warshall_floyd_int(adj, w)

# choose the best route by examining all possible routes
# this is possible because R <= 8
min_distance = float('inf')
for permutation in permutations(r_list):
    distance = 0
    for i, city in enumerate(permutation[:-1]):
        next_city = permutation[i + 1]
        distance += shortest_distances[city][next_city]
    min_distance = min(min_distance, distance)
print(min_distance)


Fixed submission:
# time complexity: O(N^3 + R!)
# space complexity: O(N^2)

import sys
fin = sys.stdin.readline
from itertools import permutations


def warshall_floyd_int(adj, w):
    num_vertices = len(adj)
    dp = [[float('inf')] * num_vertices for _ in range(num_vertices)]
    for u in range(num_vertices):
        dp[u][u] = 0
        for v in adj[u]:
            dp[u][v] = w[u][v]

    for k in range(num_vertices):
        for i in range(num_vertices):
            for j in range(num_vertices):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
    return dp


N, M, R = [int(elem) for elem in fin().split()]
r_list = [int(elem) - 1 for elem in fin().split()]
assert len(r_list) == R

adj = [[] for _ in range(N)]
w = [[None] * N for _ in range(N)]

for _ in range(M):
    A, B, C = [int(elem) for elem in fin().split()]
    A -= 1
    B -= 1
    adj[A].append(B)
    adj[B].append(A)
    w[A][B] = C
    w[B][A] = C

# calculate the shortest distance between any pair of vertices
shortest_distances = warshall_floyd_int(adj, w)

# choose the best route by examining all possible routes
# this is possible because R <= 8
min_distance = float('inf')
for permutation in permutations(r_list):
    distance = 0
    for i, city in enumerate(permutation[:-1]):
        next_city = permutation[i + 1]
        distance += shortest_distances[city][next_city]
    min_distance = min(min_distance, distance)
print(min_distance)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
a_list = [int(input()) for _ in range(N)]

button_history = [1]
while True:
    next_button = a_list[button_history[-1] - 1]
    if next_button == 2:
        print(len(button_history))
        break
    elif next_button in button_history:
        print(-1)
        break
    else:
        button_history.append(next_button)


Fixed submission:
N = int(input())
a_list = [int(input()) for _ in range(N)]

button_history = [1]
current_button = 1
num_manipulation = -1

for i in range(1, N + 1):
    current_button = a_list[current_button - 1]
    if current_button == 2:
        num_manipulation = i
        break

print(num_manipulation)