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

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


@lru_cache(maxsize=None)
def solve(n):
    if n == 0:
        return 0
    if n < 0:
        return INF
    d = 0
    ret = INF
    while 6 ** d <= n:
        if n - 6 ** d >= 0:
            ret = min(ret, solve(n - 6 ** d) + 1)
        if n - 9 ** d >= 0:
            ret = min(ret, solve(n - 9 ** d) + 1)
        d += 1
    return ret


n = int(sys.stdin.buffer.readline())
ans = solve(n)
print(ans)


Fixed submission:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

# MOD = 998244353


N = int(sys.stdin.buffer.readline())

s = {0}
ans = 0
while True:
    ns = set()
    for n in s:
        d = 0
        while n + 6 ** d <= N:
            ns.add(n + 6 ** d)
            d += 1
        d = 0
        while n + 9 ** d <= N:
            ns.add(n + 9 ** d)
            d += 1
    ans += 1
    if N in ns:
        break
    s = ns
print(ans)

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

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


@lru_cache(maxsize=None)
def solve(n):
    if n == 0:
        return 0
    if n < 0:
        return INF
    d = 0
    ret = INF
    while 6 ** d <= n:
        if n - 6 ** d >= 0:
            ret = min(ret, solve(n - 6 ** d) + 1)
        if n - 9 ** d >= 0:
            ret = min(ret, solve(n - 9 ** d) + 1)
        d += 1
    return ret


n = int(sys.stdin.buffer.readline())
ans = solve(n)
print(ans)


Fixed submission:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

# MOD = 998244353


N = int(sys.stdin.buffer.readline())

s = {0}
ans = 0
while True:
    ns = set()
    for n in s:
        d = 0
        while n + 6 ** d <= N:
            ns.add(n + 6 ** d)
            d += 1
        d = 0
        while n + 9 ** d <= N:
            ns.add(n + 9 ** d)
            d += 1
    ans += 1
    if N in ns:
        break
    s = ns
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import itertools
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


# 色のパターン 30*29*28 == 24360
# 全部試すだけ

N, C = list(map(int, sys.stdin.buffer.readline().split()))
D = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(C)]
S = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]

D = np.array(D, dtype=int)
S = np.array(S, dtype=int) - 1

md = np.zeros((N, N), dtype=int)
md += np.arange(N, dtype=int)
md += np.arange(N, dtype=int)[:, None]
md %= 3

ans = INF
for colors in itertools.permutations(range(C), r=3):
    # S[md == 0] -> colors[0]
    s = 0
    s += D[S[md == 0], colors[0]].sum()
    s += D[S[md == 1], colors[1]].sum()
    s += D[S[md == 2], colors[2]].sum()
    ans = min(ans, s)
print(ans)


Fixed submission:
import itertools
import sys
import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')

N, C = map(int, input().split())
COSTS = []
for _ in range(C):
    COSTS.append(list(map(int, input().split())))
# (C, C)
COSTS = np.array(COSTS)
COLORS = []
for _ in range(N):
    COLORS.append(list(map(int, input().split())))
# (N, N)
COLORS = np.array(COLORS) - 1

# cs[x, y]: x == (i + j) % 3 で、色が y であるマスの数
cs = np.zeros((3, C))
for i in range(N):
    for j in range(N):
        cs[(i + j) % 3, COLORS[i, j]] += 1

ans = INF
# (i + j) % 3 == N のマスを cN にする場合のコストを全通り計算する
for c0, c1, c2 in itertools.permutations(range(C), r=3):
    ans = min(
        ans,
        np.dot(COSTS[:, c0], cs[0]) +
        np.dot(COSTS[:, c1], cs[1]) +
        np.dot(COSTS[:, c2], cs[2]))
print(int(ans))
Buggy python submission (verdict: Runtime Error):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

S = sys.stdin.readline().rstrip()
K = int(sys.stdin.readline())


def prune(it):
    hist = set()
    ret = []
    for s, l in it:
        if s not in hist:
            hist.add(s)
        if len(hist) > K:
            break
        ret.append((s, l))
    return ret


collections = prune(sorted([(c, L) for L, c in enumerate(S)]))
for size in range(1, len(S)):
    threshold, _ = collections[-1]
    for s, left in collections:
        r = left + size + 1
        if len(s) == size and r <= len(S):
            t = S[left:r]
            if t <= threshold:
                collections.append((t, left))
    collections = prune(sorted(collections))

strings = list(set([s for s, _ in collections]))
strings.sort()
print(strings[K - 1])


Fixed submission:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

S = sys.stdin.readline().rstrip()
K = int(sys.stdin.readline())

s = set()
for k in range(1, K + 1):
    for i in range(len(S)):
        s.add(S[i:i + k])

s = list(sorted(list(s)))
print(s[K - 1])

Buggy python submission (verdict: Runtime Error):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

S = sys.stdin.readline().rstrip()
K = int(sys.stdin.readline())


def prune(it):
    print(list(it))
    hist = set()
    ret = []
    for s, l in it:
        if s not in hist:
            hist.add(s)
        if len(hist) > K:
            break
        ret.append((s, l))
    return ret


collections = prune(sorted([(c, L) for L, c in enumerate(S)]))
for size in range(1, len(S)):
    threshold, _ = collections[-1]
    for s, left in collections:
        r = left + size + 1
        if len(s) == size and r <= len(S):
            t = S[left:r]
            if t <= threshold:
                collections.append((t, left))
    collections = prune(sorted(collections))

strings = list(set([s for s, _ in collections]))
strings.sort()
print(strings[K - 1])


Fixed submission:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

S = sys.stdin.readline().rstrip()
K = int(sys.stdin.readline())

s = set()
for k in range(1, K + 1):
    for i in range(len(S)):
        s.add(S[i:i + k])

s = list(sorted(list(s)))
print(s[K - 1])
Buggy python submission (verdict: Time Limit Exceeded):
import bisect
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
from operator import mul

import numpy as np
import re
import sys

sys.setrecursionlimit(10000)
INF = float('inf')


def comb(n, r):
    """
    scipy.misc.comb または scipy.special.comb と同じ
    組み合わせの数 nCr
    :param int n:
    :param int r:
    :rtype: int
    """
    assert n >= r
    r = min(n - r, r)
    if r == 0:
        return 1
    return reduce(mul, range(n, n - r, -1)) // reduce(mul, range(r, 0, -1))


N = int(input())
A = list(map(int, input().split()))
A.sort()

max_comb = 0
ans = 0, 1
for a in A:
    def test(i):
        global max_comb, ans
        if 0 <= i < N and A[i] < a:
            c = comb(a, A[i])
            if c > max_comb:
                max_comb = c
                ans = a, A[i]

    # a /2 に近いほど大きい
    i = bisect.bisect_left(A, a / 2)
    test(i - 1)
    test(i)
    test(i + 1)
print(*ans)


Fixed submission:
import bisect
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
from operator import mul

import numpy as np
import re
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

N = int(input())
A = list(map(int, input().split()))
A.sort()

# nCr を求める
# r が同じなら、n は大きいほうが nCr は大きい
n = A[-1]
# n が同じなら、r は n / 2 に近いほど大きい
r = bisect.bisect_left(A, n / 2)

if abs(A[r - 1] - n / 2) < abs(A[r] - n / 2):
    r -= 1
while A[r] == n:
    r -= 1
print(n, A[r])
Buggy python submission (verdict: Runtime Error):
import functools

import os

INF = float('inf')


def inp():
    return int(input())


def inpf():
    return float(input())


def inps():
    return input()


def inl():
    return list(map(int, input().split()))


def inlf():
    return list(map(float, input().split()))


def inls():
    return input().split()


def debug(fn):
    if not os.getenv('LOCAL'):
        return fn

    @functools.wraps(fn)
    def wrapper(*args, **kwargs):
        print('DEBUG: {}({}) -> '.format(
            fn.__name__,
            ', '.join(
                list(map(str, args)) +
                ['{}={}'.format(k, str(v)) for k, v in kwargs.items()]
            )
        ), end='')
        ret = fn(*args, **kwargs)
        print(ret)
        return ret

    return wrapper


s = list(input())
if list(s.sort()) == ['a','b','c']:
    print('Yes')
else:
    print('No')


Fixed submission:
import functools

import os

INF = float('inf')


def inp():
    return int(input())


def inpf():
    return float(input())


def inps():
    return input()


def inl():
    return list(map(int, input().split()))


def inlf():
    return list(map(float, input().split()))


def inls():
    return input().split()


def debug(fn):
    if not os.getenv('LOCAL'):
        return fn

    @functools.wraps(fn)
    def wrapper(*args, **kwargs):
        print('DEBUG: {}({}) -> '.format(
            fn.__name__,
            ', '.join(
                list(map(str, args)) +
                ['{}={}'.format(k, str(v)) for k, v in kwargs.items()]
            )
        ), end='')
        ret = fn(*args, **kwargs)
        print(ret)
        return ret

    return wrapper


s = list(input())
s.sort()
if s == list('abc'):
    print('Yes')
else:
    print('No')
Buggy python submission (verdict: Runtime Error):
import bisect
import os
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import re
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

A, B, K = list(map(int, sys.stdin.readline().split()))

arr = list(range(A, B + 1))
a = list(range(A, min(B, A + K)))
b = list(range(max(A, B - K + 1), B + 1))



print('\n'.join(map(str, list(sorted(set(a + b))))))


Fixed submission:
import bisect
import os
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import re
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

# N, M, X = list(map(int, sys.stdin.readline().split()))
# A = np.array(list(map(int, sys.stdin.readline().split())))
#
# print(min(len(A[A > X]), len(A[A<X])))

A, B, K = list(map(int, sys.stdin.readline().split()))

a = list(range(A, min(B, A + K)))
b = list(range(max(A, B - K + 1), B + 1))



print('\n'.join(map(str, list(sorted(set(a + b))))))

Buggy python submission (verdict: Runtime Error):
import bisect
import os
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import re
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

# N, M, X = list(map(int, sys.stdin.readline().split()))
# A = np.array(list(map(int, sys.stdin.readline().split())))
#
# print(min(len(A[A > X]), len(A[A<X])))

A, B, K = list(map(int, sys.stdin.readline().split()))

arr = list(range(A, B + 1))

print('\n'.join(map(str, list(sorted(set(arr[:K] + arr[-K:]))))))


Fixed submission:
import bisect
import os
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import re
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

# N, M, X = list(map(int, sys.stdin.readline().split()))
# A = np.array(list(map(int, sys.stdin.readline().split())))
#
# print(min(len(A[A > X]), len(A[A<X])))

A, B, K = list(map(int, sys.stdin.readline().split()))

a = list(range(A, min(B, A + K)))
b = list(range(max(A, B - K + 1), B + 1))



print('\n'.join(map(str, list(sorted(set(a + b))))))
Buggy python submission (verdict: Runtime Error):
import functools

import os

INF = float('inf')


def inp():
    return int(input())


def inpf():
    return float(input())


def inps():
    return input()


def inl():
    return list(map(int, input().split()))


def inlf():
    return list(map(float, input().split()))


def inls():
    return input().split()


def debug(fn):
    if not os.getenv('LOCAL'):
        return fn

    @functools.wraps(fn)
    def wrapper(*args, **kwargs):
        print('DEBUG: {}({}) -> '.format(
            fn.__name__,
            ', '.join(
                list(map(str, args)) +
                ['{}={}'.format(k, str(v)) for k, v in kwargs.items()]
            )
        ), end='')
        ret = fn(*args, **kwargs)
        print(ret)
        return ret

    return wrapper


a = inls()
b = inls()
c = inls()
print(a[0] + b[1] + c[2])

Fixed submission:
import functools

import os

INF = float('inf')


def inp():
    return int(input())


def inpf():
    return float(input())


def inps():
    return input()


def inl():
    return list(map(int, input().split()))


def inlf():
    return list(map(float, input().split()))


def inls():
    return input().split()


def debug(fn):
    if not os.getenv('LOCAL'):
        return fn

    @functools.wraps(fn)
    def wrapper(*args, **kwargs):
        print('DEBUG: {}({}) -> '.format(
            fn.__name__,
            ', '.join(
                list(map(str, args)) +
                ['{}={}'.format(k, str(v)) for k, v in kwargs.items()]
            )
        ), end='')
        ret = fn(*args, **kwargs)
        print(ret)
        return ret

    return wrapper


a = inps()
b = inps()
c = inps()
print(a[0] + b[1] + c[2])
Buggy python submission (verdict: Runtime Error):
import sys

import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')

H, W, D = list(map(int, input().split()))
A = [list(map(int, input().split())) for _ in range(H)]
Q = int(input())
L, R = zip(*[list(map(int, input().split())) for _ in range(Q)])

# h_pos[a]: a がある位置の h
# w_pos[a]: a がある位置の w
h_pos = np.zeros(H * W + 1)
w_pos = np.zeros(H * W + 1)
for h in range(H):
    for w in range(W):
        h_pos[A[h][w]] = h
        w_pos[A[h][w]] = w

dp = np.zeros(H * W + 1, dtype=int)
for i in range(1, H * W + 1):
    if i - D >= 0:
        dp[i] = dp[i - D] + abs(h_pos[i - D] - h_pos[i]) + abs(w_pos[i - D] - w_pos[i])

for l, r in zip(L, R):
    print(dp[r] - dp[l])


Fixed submission:
import sys

import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')

H, W, D = list(map(int, input().split()))
A = [list(map(int, input().split())) for _ in range(H)]
Q = int(input())
L, R = zip(*[list(map(int, input().split())) for _ in range(Q)])

# h_pos[a]: a がある位置の h
# w_pos[a]: a がある位置の w
h_pos = np.zeros(H * W + 1)
w_pos = np.zeros(H * W + 1)
for h in range(H):
    for w in range(W):
        h_pos[A[h][w]] = h
        w_pos[A[h][w]] = w

dp = np.zeros(H * W + 1, dtype=int)
for i in range(1, H * W + 1):
    if i - D >= 0:
        dp[i] = dp[i - D] + abs(h_pos[i - D] - h_pos[i]) + abs(w_pos[i - D] - w_pos[i])

for l, r in zip(L, R):
    print(dp[r] - dp[l])
Buggy python submission (verdict: Runtime Error):
/// ローカル環境なら _in.txt から入力を受ける
fn read_input() -> String {
    use std::fs::File;
    use std::io::Read;
    let mut s = String::new();
    match option_env!("LOCAL") {
        Some(_) => File::open("src/_in.txt")
            .expect("File not found")
            .read_to_string(&mut s)
            .unwrap(),
        None => std::io::stdin().read_to_string(&mut s).unwrap(),
    };
    s
}

fn main() {
    let s = read_input();
    let mut ws = s.split_whitespace();
    let in_n: i32 = ws.next().unwrap().parse().unwrap();
    let mut txy: Vec<(i32, i32, i32)> = (0..in_n)
        .map(|_| {
            let t: i32 = ws.next().unwrap().parse().unwrap();
            let x: i32 = ws.next().unwrap().parse().unwrap();
            let y: i32 = ws.next().unwrap().parse().unwrap();
            (t, x, y)
        })
        .collect();
    txy.insert(0, (0, 0, 0));

    let mut ok = true;
    for window in txy.windows(2) {
        let ((t1, x1, y1), (t2, x2, y2)) = (window[0], window[1]);
        let dt = t2 - t1;
        let d = (x1 - x2).abs() + (y1 - y2).abs();
        ok &= dt >= d && (dt - d) % 2 == 0
    }
    println!("{}", if ok { "Yes" } else { "No" });
}


Fixed submission:
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
T, X, Y = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(N)]))

t, x, y = 0, 0, 0
ok = True
for i in range(N):
    dt = T[i] - t
    d = abs(x - X[i]) + abs(y - Y[i])
    if not (dt >= d and (dt - d) % 2 == 0):
        ok = False
    t = T[i]
    x = X[i]
    y = Y[i]
if ok:
    print('Yes')
else:
    print('No')
Buggy python submission (verdict: Runtime Error):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

S = sys.stdin.buffer.readline().decode().rstrip()
X, Y = list(map(int, sys.stdin.buffer.readline().split()))

# X 軸と Y 軸は独立に考えられる。
d = 0
cnt = 0
xy = [[], []]
for c in S:
    if c == 'F':
        cnt += 1
    else:
        xy[d].append(cnt)
        cnt = 0
        d = d + 1 & 1
xy[d].append(cnt)
X -= xy[0].pop(0)


def can_make(moves, obj):
    obj = 1 << (8000 + obj)
    dp = 1 << 8000
    for mv in moves:
        if mv == 0:
            continue
        dp = (dp << mv) | (dp >> mv)
    return (dp & obj) > 0


ok = can_make(xy[0], X) and can_make(xy[1], Y)
if ok:
    print('Yes')
else:
    print('No')


Fixed submission:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

S = sys.stdin.buffer.readline().decode().rstrip()
X, Y = list(map(int, sys.stdin.buffer.readline().split()))

# X 軸と Y 軸は独立に考えられる。
d = 0
cnt = 0
xy = [[], []]
for c in S:
    if c == 'F':
        cnt += 1
    else:
        xy[d].append(cnt)
        cnt = 0
        d = d + 1 & 1
xy[d].append(cnt)
X -= xy[0].pop(0)


def can_make(moves, obj):
    if obj < -8000:
        return False
    obj = 1 << (8000 + obj)
    dp = 1 << 8000
    for mv in moves:
        if mv == 0:
            continue
        dp = (dp << mv) | (dp >> mv)
    return (dp & obj) > 0


ok = can_make(xy[0], X) and can_make(xy[1], Y)
if ok:
    print('Yes')
else:
    print('No')
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import deque

sys.setrecursionlimit(10000)
INF = float('inf')

N, L = list(map(int, input().split()))
S = set()
for _ in range(N):
    S.add(input())


# 追加できるのが 01... だけで
# L が 4 とすると
# 01: 次はない
# 010: 011 がある
# 011: 010 がある
# 0100: 011, 0101 がある
# 0101: 011, 0100
# 0110: 010, 0111
# 0111: 010, 0110
# 候補の長さと L だけによって次の候補の長さと数が決まる
def grundy(size):
    """
    :param int size: 候補の長さ
    :return:
    """
    # gs = {0}
    # g = 0
    # for sz in range(size + 1, L + 1):
    #     g ^= grundy(sz)
    #     gs.add(g)
    #
    # i = 0
    # while i in gs:
    #     i += 1
    # return i
    i = 1
    while (L - size + 1) % i == 0:
        i *= 2
    return i // 2


prefixes = set()
for s in S:
    for i in range(len(s)):
        prefixes.add(s[:i + 1])

ok_set = set()
ng_set = deque()
ng_set.append('')
while len(ng_set) > 0:
    ng = ng_set.popleft()
    if len(ng) >= L:
        continue
    for c in '01':
        if ng + c not in prefixes:
            ok_set.add(ng + c)
        elif ng + c not in S:
            ng_set.append(ng + c)

g = 0
for ok in ok_set:
    g ^= grundy(len(ok))
if g != 0:
    print('Alice')
else:
    print('Bob')


Fixed submission:
import sys
from collections import deque

sys.setrecursionlimit(10000)
INF = float('inf')

N, L = list(map(int, input().split()))
S = set()
for _ in range(N):
    S.add(input())


# 追加できるのが 01... だけで
# L が 4 とすると
# 01: 次はない
# 010: 011 がある
# 011: 010 がある
# 0100: 011, 0101 がある
# 0101: 011, 0100
# 0110: 010, 0111
# 0111: 010, 0110
# 候補の長さと L だけによって次の候補の長さと数が決まる
def grundy(size):
    """
    :param int size: 候補の長さ
    :return:
    """
    # gs = {0}
    # g = 0
    # for sz in range(size + 1, L + 1):
    #     g ^= grundy(sz)
    #     gs.add(g)
    #
    # i = 0
    # while i in gs:
    #     i += 1
    # return i
    i = 1
    while (L - size + 1) % i == 0:
        i *= 2
    return i // 2


# S の各要素からトライ木つくる
trie = {}
for s in S:
    t = trie
    for c in s:
        if c not in t:
            t[c] = {}
        t = t[c]

# 候補文字列の長さのリスト
ok_size_list = []
children = deque()
children.append((trie, 0))
while len(children) > 0:
    node, size = children.popleft()
    # 0 か 1 か片方しか行けなかったら、行けない方は S の prefix にならない
    # 両方行けない場合はどう追加しても S のいずれかが prefix になってしまうからダメ
    if len(node) == 1:
        ok_size_list.append(size + 1)
    for c, child in node.items():
        children.append((child, size + 1))

g = 0
for size in ok_size_list:
    g ^= grundy(size)
if g != 0:
    print('Alice')
else:
    print('Bob')
Buggy python submission (verdict: Runtime Error):
import sys

import numpy as np
from scipy.sparse.csgraph import dijkstra

sys.setrecursionlimit(10000)
INF = float('inf')

H, W = list(map(int, input().split()))
C = np.array([list(map(int, input().split())) for _ in range(10)], dtype=int)
A = np.array([list(map(int, input().split())) for _ in range(H)], dtype=int)
A[A == -1] = 1

mp = dijkstra(C, directed=True)[:, 1]
nums, counts = np.unique(A, return_counts=True)
print(int((mp[nums] * counts).sum()))


Fixed submission:
import sys

import numpy as np
from scipy.sparse.csgraph import dijkstra

sys.setrecursionlimit(10000)
INF = float('inf')

H, W = list(map(int, input().split()))
C = np.array([list(map(int, input().split())) for _ in range(10)], dtype=int)
A = np.array([list(map(int, input().split())) for _ in range(H)], dtype=int)

mp = dijkstra(C, directed=True)[:, 1]
ans = 0
for n in range(10):
    ans += mp[n] * np.sum(A == n)
print(int(round(ans)))
Buggy python submission (verdict: Runtime Error):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N, M = list(map(int, sys.stdin.readline().split()))

N, M = list(map(int, sys.stdin.readline().split()))
# 1 回の時間は M*1900 + (N-M)*100
time = M * 1900 + (N - M) * 100
# AC になる確率
p_ac = 1 / 2 ** M

print(int(1 / p_ac * time))



Fixed submission:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N, M = list(map(int, sys.stdin.readline().split()))

# 1 回の時間は M*1900 + (N-M)*100
time = M * 1900 + (N - M) * 100
# AC になる確率
p_ac = 1 / 2 ** M

print(int(1 / p_ac * time))