Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
def d_various_sushi(N, K, Param):
    import heapq

    # 寿司をおいしさの値が大きなものからK個取る
    sushi_parameter = sorted(Param, key=lambda x: x[1], reverse=True)
    sushi_invariably_chosen = []  # ネタが被っていない場合、貪欲に取っていい
    candidate_reject = []  # ネタの種類数を増やす時に取り除く候補(priority queueで管理)
    chosen_topping = set()  # 取った寿司ネタの種類
    for i in range(K):
        t, d = sushi_parameter[i]
        if t not in chosen_topping:
            sushi_invariably_chosen.append(d)
            chosen_topping.add(t)
        else:
            heapq.heappush(candidate_reject, d)

    # 暫定的な最大値を計算しておく
    delicious_sum1 = sum(sushi_invariably_chosen)
    delicious_sum2 = sum(candidate_reject)
    topping_variety = len(chosen_topping)
    ans = delicious_sum1 + delicious_sum2 + topping_variety**2
    if len(candidate_reject) == 0:
        return ans  # 除く寿司の候補がないので、満足度を大きくしようがない

    for i in range(K, N):
        t, d = sushi_parameter[i]
        if t in chosen_topping:
            # ネタが被った上、おいしさがこれまで取った寿司より小さな寿司と交換する理由はない
            continue

        # 取り除いてもネタの種類数が減らない寿司の中で最もおいしさの小さいものを取り除く
        delicious_sum2 -= heapq.heappop(candidate_reject)
        # これまでに取っている寿司にないネタを持ち、最もおいしさの大きい寿司を取る
        chosen_topping.add(t)
        delicious_sum1 += d
        topping_variety += 1

        ans = max(ans, delicious_sum1 + delicious_sum2 + topping_variety**2)
    return ans

N, K = [int(i) for i in input().split()]
Param = [[int(i) for i in input().split()] for j in range(N)]
print(d_various_sushi(N, K, Param))

Fixed submission:
def d_various_sushi(N, K, Param):
    import heapq

    # 寿司をおいしさの値が大きなものからK個取る
    sushi_parameter = sorted(Param, key=lambda x: x[1], reverse=True)
    sushi_invariably_chosen = []  # ネタが被っていない場合、貪欲に取っていい
    candidate_reject = []  # ネタの種類数を増やす時に取り除く候補(priority queueで管理)
    chosen_topping = set()  # 取った寿司ネタの種類
    for i in range(K):
        t, d = sushi_parameter[i]
        if t not in chosen_topping:
            sushi_invariably_chosen.append(d)
            chosen_topping.add(t)
        else:
            heapq.heappush(candidate_reject, d)

    # 暫定的な最大値を計算しておく
    delicious_sum1 = sum(sushi_invariably_chosen)
    delicious_sum2 = sum(candidate_reject)
    topping_variety = len(chosen_topping)
    ans = delicious_sum1 + delicious_sum2 + topping_variety**2

    for i in range(K, N):
        if len(candidate_reject) == 0:
            break  # 除く寿司の候補がないので、満足度を大きくしようがない

        t, d = sushi_parameter[i]
        if t in chosen_topping:
            # ネタが被った上、おいしさがこれまで取った寿司より小さな寿司と交換する理由はない
            continue

        # 取り除いてもネタの種類数が減らない寿司の中で最もおいしさの小さいものを取り除く
        delicious_sum2 -= heapq.heappop(candidate_reject)
        # これまでに取っている寿司にないネタを持ち、最もおいしさの大きい寿司を取る
        chosen_topping.add(t)
        delicious_sum1 += d
        topping_variety += 1

        ans = max(ans, delicious_sum1 + delicious_sum2 + topping_variety**2)
    return ans

N, K = [int(i) for i in input().split()]
Param = [[int(i) for i in input().split()] for j in range(N)]
print(d_various_sushi(N, K, Param))
Buggy python submission (verdict: Time Limit Exceeded):
N, K = [int(i) for i in input().split()]
H = [int(i) for i in input().split()]

dp = [float('inf')] * N
dp[0] = 0
for i in range(1, N):
    for j in range(1, K + 1):
        if i - j < 0:
            break
        dp[i] = min(dp[i], dp[i - j] + abs(H[i] - H[i - j]))
print(dp[N - 1])

Fixed submission:
N, K = [int(i) for i in input().split()]
H = [int(i) for i in input().split()]

dp = [float('inf')] * N
dp[0] = 0
for i in range(1, N):
    for j in range(1, K + 1):
        if i - j < 0:
            break
        dp[i] = min(dp[i], dp[i - j] + abs(H[i] - H[i - j]))
print(dp[N - 1])
Buggy python submission (verdict: Runtime Error):
N = int(input())
Happiness = [sorted([int(i) for i in input().split()]) for j in range(N)]

ans1 = ans2 = 0
for move, choice1, choice2 in zip(Happiness, cycle([1, 2]), cycle([2, 1])):
    ans1 += move[choice1]
    ans2 += move[choice2]

print(max(ans1, ans2))

Fixed submission:
N = int(input())
Happiness = [[int(i) for i in input().split()] for j in range(N)]

dp = [[0] * 3 for _ in range(N)]
dp[0] = Happiness[0][:]
for day in range(1, N):
    dp[day][0] = max(dp[day - 1][1], dp[day - 1][2]) + Happiness[day][0]
    dp[day][1] = max(dp[day - 1][2], dp[day - 1][0]) + Happiness[day][1]
    dp[day][2] = max(dp[day - 1][0], dp[day - 1][1]) + Happiness[day][2]
print(max(dp[N - 1]))
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
N, W = [int(i) for i in input().split()]
Things = [[int(i) for i in input().split()] for j in range(N)]

dp = defaultdict(int)
dp[0] = 0
for w, v in Things:
    for nw, nv in list(dp.items()):
        if nw + w <= W:
            dp[nw + w] = max(dp[nw + w], nv + v)
print(max(dp.values()))

Fixed submission:
from collections import defaultdict
N, W = [int(i) for i in input().split()]
Things = [[int(i) for i in input().split()] for j in range(N)]

dp = defaultdict(int)
dp[0] = 0
for w, v in Things:
    for nw, nv in list(dp.items()):
        if nw + w <= W:
            dp[nw + w] = max(dp[nw + w], nv + v)
print(max(dp.values()))
Buggy python submission (verdict: Runtime Error):
def g_longest_path(N, M, Edges):
    """
    N頂点M辺の有向グラフGが与えられる。Gは有向閉路を含まない。
    Gの有向パスのうち、最長のものについてその長さを求めよ。
    有向パスの長さとは、有向パスに含まれる辺の本数のことをいう。
    """
    # 隣接リストでグラフを持つ(0-based)
    graph = [[] for _ in range(N)]
    for x, y in Edges:
        graph[x - 1].append(y - 1)

    # メモ化再帰
    # ある頂点vから辿っていけるパスの長さは、vに着くまでにどのようにパスを
    # 辿ってきたかと無関係(有向閉路がないため)なので、この方法が使える
    def memorized_recursive(v):
        if dp[v] != -1:
            return dp[v]  # 頂点vはすでに更新済み

        ret = 0
        # 頂点vから1つ辺を通って行ける頂点の集合に対して同じ計算を行う
        for nv in graph[v]:
            ret = max(ret, memorized_recursive(nv) + 1)
        dp[v] = ret  # メモに追加
        return ret

    ans = 0
    dp = [-1] * N  # dp[v]: ノードvを始点としたときの、Gの有効パスの長さの最大値
    # 各頂点に対して調べる
    for v in range(N):
        ans = max(ans, memorized_recursive(v))
    return ans

N, M = [int(i) for i in input().split()]
Edges = [[int(i) for i in input().split()] for j in range(M)]
print(g_longest_path(N, M, Edges))

Fixed submission:
def g_longest_path(N, M, Edges):
    """
    N頂点M辺の有向グラフGが与えられる。Gは有向閉路を含まない。
    Gの有向パスのうち、最長のものについてその長さを求めよ。
    有向パスの長さとは、有向パスに含まれる辺の本数のことをいう。
    """
    import sys
    sys.setrecursionlimit(10**6)

    # 隣接リストでグラフを持つ(0-based)
    graph = [[] for _ in range(N)]
    for x, y in Edges:
        graph[x - 1].append(y - 1)

    # メモ化再帰
    # ある頂点vから辿っていけるパスの長さは、vに着くまでにどのようにパスを
    # 辿ってきたかと無関係(有向閉路がないため)なので、この方法が使える
    def memorized_recursive(v):
        if dp[v] != -1:
            return dp[v]  # 頂点vはすでに更新済み

        ret = 0
        # 頂点vから1つ辺を通って行ける頂点の集合に対して同じ計算を行う
        for nv in graph[v]:
            ret = max(ret, memorized_recursive(nv) + 1)
        dp[v] = ret  # メモに追加
        return ret

    ans = 0
    dp = [-1] * N  # dp[v]: ノードvを始点としたときの、Gの有効パスの長さの最大値
    # 各頂点に対して調べる
    for v in range(N):
        ans = max(ans, memorized_recursive(v))
    return ans

N, M = [int(i) for i in input().split()]
Edges = [[int(i) for i in input().split()] for j in range(M)]
print(g_longest_path(N, M, Edges))
Buggy python submission (verdict: Time Limit Exceeded):
def i_coins(N, P):
    """
    N枚の番号が振られたコインがある。i番目のコインを投げたときに
    表が出る確率はp_i, 裏が出る確率は1-p_iである。
    N枚のコインをすべて投げるとき、表の枚数が裏の枚数を上回る確率を求めよ。
    """
    # dp[i][j]: コインをi枚使ったとき、表がj枚である確率
    dp = [[0.0] * (N + 1) for _ in range(N + 1)]
    dp[0][0] = 1.0  # これで初期化(0枚投げて表が0枚である確率は考えられないが)
    for i in range(1, N + 1):
        # 表が出た回数が投げたコインの枚数を上回ることはありえない
        for j in range(i + 1):
            # i枚使ってj枚表が出る確率
            # = i-1枚使ってj-1枚表が出る確率 * i枚目が表である確率
            # + i-1枚使ってj枚表が出る確率 * i枚目が裏である確率
            dp[i][j] = (dp[i - 1][j - 1] * P[i - 1] * int(j >= 1)
                        + dp[i - 1][j] * (1.0 - P[i - 1]))

    ans = 0.0
    for i in range(N // 2 + 1, N + 1):
        ans += dp[N][i]  # N枚使ってN//2+1枚以上表が出る確率を足し合わせると解
    ans = round(ans, 11)  # round()は正確には偶数への丸めだが、使う
    return ans

N = int(input())
P = [float(i) for i in input().split()]
print(i_coins(N, P))

Fixed submission:
def i_coins(N, P):
    """
    N枚の番号が振られたコインがある。i番目のコインを投げたときに
    表が出る確率はp_i, 裏が出る確率は1-p_iである。
    N枚のコインをすべて投げるとき、表の枚数が裏の枚数を上回る確率を求めよ。
    """
    # dp[i][j]: コインをi枚使ったとき、表がj枚である確率
    dp = [[0.0] * (N + 1) for _ in range(N + 1)]
    dp[0][0] = 1.0  # これで初期化(0枚投げて表が0枚である確率は考えられないが)
    for i in range(1, N + 1):
        # 表が出た回数が投げたコインの枚数を上回ることはありえない
        for j in range(i + 1):
            # i枚使ってj枚表が出る確率
            # = i-1枚使ってj-1枚表が出る確率 * i枚目が表である確率
            # + i-1枚使ってj枚表が出る確率 * i枚目が裏である確率
            dp[i][j] = (dp[i - 1][j - 1] * P[i - 1] * int(j >= 1)
                        + dp[i - 1][j] * (1.0 - P[i - 1]))

    ans = 0.0
    for i in range(N // 2 + 1, N + 1):
        ans += dp[N][i]  # N枚使ってN//2+1枚以上表が出る確率を足し合わせると解
    ans = round(ans, 11)  # round()は正確には偶数への丸めだが、使う
    return ans

N = int(input())
P = [float(i) for i in input().split()]
print(i_coins(N, P))
Buggy python submission (verdict: Runtime Error):
print(' '.join('Christmas','Eve'*(25-int(input()))))

Fixed submission:
D = int(input())
if D == 25:
    print('Christmas')
elif D == 24:
    print('Christmas Eve')
elif D == 23:
    print('Christmas Eve Eve')
elif D == 22:
    print('Christmas Eve Eve Eve')
Buggy python submission (verdict: Runtime Error):
def c_christmas_eve(N, K, H):
    H.sort()
    ans = float('inf')
    for j in range(N - K + 1):
        h_max = H[j + 2]
        h_min = H[j]
        ans = min(ans, h_max - h_min)
    return ans

N, K = [int(i) for i in input().split()]
H = [int(input()) for _ in range(N)]
print(c_christmas_eve(N, K, H))

Fixed submission:
def c_christmas_eve(N, K, H):
    H.sort()
    ans = float('inf')
    for j in range(N - K + 1):
        h_max = H[j + K - 1]
        h_min = H[j]
        ans = min(ans, h_max - h_min)
    return ans

N, K = [int(i) for i in input().split()]
H = [int(input()) for _ in range(N)]
print(c_christmas_eve(N, K, H))
Buggy python submission (verdict: Runtime Error):
def c_id():
    from collections import defaultdict
    N, M = [int(i) for i in input().split()]
    Cities = [[int(i) for i in input().split()] for j in range(M)]

    dic = defaultdict(list)
    # 県毎に市をまとめる
    for p, y in Cities:
        dic[p].append(y)
    # 市の認識番号を (座標) 圧縮
    for p, lst in dic.items():
        dic[p] = {v: k for k, v in enumerate(sorted(lst), 1)}
    return '\n'.join([f'{p:06d}{dic[p][y]:06d}' for p, y in Cities])

print(c_id())

Fixed submission:
def c_id(N, M, City):
    City = sorted(City, key=lambda x: (x[0], x[1]))
    # print(City)
    a, b = City[0][0], 0
    for j, (p, y, k) in enumerate(City):
        if p == a:
            # print('a', j, p, y, k)
            b += 1
            City[j] = [p, b, k]
        else:
            # print('b', j, p, y, k)
            a = p
            b = 1
            City[j] = [p, b, k]
    city = sorted(City, key=lambda x: x[2])
    # print(city)

    ans_tmp = []
    for p, q, k in city:
        ans_tmp.append('{0:06d}{1:06d}'.format(p, q))
    ans = '\n'.join(ans_tmp)
    return ans

N, M = [int(i) for i in input().split()]
City = [[int(i) for i in input().split()] + [k] for j, k in enumerate(range(M), 1)]
print(c_id(N, M, City))

Buggy python submission (verdict: Runtime Error):
def c_id():
    from collections import defaultdict
    N, M = map(int, input().split())
    City = [[s] + [int(i) for i in input().split()] for s in range(M)]

    # 同じ県に属する市を誕生年の早い順に並べ、順序付けする
    city_dict = defaultdict(list)
    for k, p, y in City:
        city_dict[p].append([k, p, y])
    for p in city_dict.keys():
        city_dict[p].sort(key=lambda x: x[2])
        for i in range(len(city_dict[p])):
            city_dict[p][i][2] = i + 1

    # 変換は終わった。通し番号順に並べる
    ans = sorted([e for v in city_dict.values() for e in v])
    return '\n'.join([f'{p:06d}{num:06d}' for _, p, num in ans])  # 通し番号は不要

print(c_id())

Fixed submission:
def c_id(N, M, City):
    City = sorted(City, key=lambda x: (x[0], x[1]))
    # print(City)
    a, b = City[0][0], 0
    for j, (p, y, k) in enumerate(City):
        if p == a:
            # print('a', j, p, y, k)
            b += 1
            City[j] = [p, b, k]
        else:
            # print('b', j, p, y, k)
            a = p
            b = 1
            City[j] = [p, b, k]
    city = sorted(City, key=lambda x: x[2])
    # print(city)

    ans_tmp = []
    for p, q, k in city:
        ans_tmp.append('{0:06d}{1:06d}'.format(p, q))
    ans = '\n'.join(ans_tmp)
    return ans

N, M = [int(i) for i in input().split()]
City = [[int(i) for i in input().split()] + [k] for j, k in enumerate(range(M), 1)]
print(c_id(N, M, City))
Buggy python submission (verdict: Runtime Error):
def c_align(N, A):
    from collections import deque
    tmp = sorted(A)

    seq = tmp[:]
    old_check = seq.pop(-1 + N // 2) if N % 2 == 0 else seq.pop(N // 2)
    current_check = -1
    seq = deque(seq)
    ans1 = 0
    turn = 0
    while seq:
        current_check = seq.pop() if turn % 2 == 0 else seq.popleft()
        ans1 += abs(current_check - old_check)
        old_check = current_check
        turn += 1

    seq = tmp[:]
    old_check = seq.pop(1 + N // 2) if N % 2 == 0 else seq.pop(N // 2)
    current_check = -1
    seq = deque(seq)
    ans2 = 0
    turn = 0
    while seq:
        current_check = seq.popleft() if turn % 2 == 0 else seq.pop()
        ans2 += abs(current_check - old_check)
        old_check = current_check
        turn += 1

    ans = max(ans1, ans2)
    return ans

N = int(input())
A = [int(input()) for _ in range(N)]
print(c_align(N, A))

Fixed submission:
def c_align(N, A):
    from collections import deque
    if N == 2:
        return abs(A[0] - A[1])
    tmp = sorted(A)

    seq = tmp[:]
    old_check = seq.pop(-1 + N // 2) if N % 2 == 0 else seq.pop(N // 2)
    current_check = -1
    seq = deque(seq)
    ans1 = 0
    turn = 0
    while seq:
        current_check = seq.pop() if turn % 2 == 0 else seq.popleft()
        ans1 += abs(current_check - old_check)
        old_check = current_check
        turn += 1

    seq = tmp[:]
    old_check = seq.pop(1 + N // 2) if N % 2 == 0 else seq.pop(N // 2)
    current_check = -1
    seq = deque(seq)
    ans2 = 0
    turn = 0
    while seq:
        current_check = seq.popleft() if turn % 2 == 0 else seq.pop()
        ans2 += abs(current_check - old_check)
        old_check = current_check
        turn += 1

    ans = max(ans1, ans2)
    return ans

N = int(input())
A = [int(input()) for _ in range(N)]
print(c_align(N, A))
Buggy python submission (verdict: Runtime Error):
def c_pyramid(N, Pos):
    from itertools import product
    # 中心座標を全探索
    for cx, cy in product(range(101), repeat=2):
        height = set()
        for x, y, h in Pos:
            height.add(h + abs(cx - x) + abs(cy - y))
        if len(height) == 1:
            ans = (cx, cy, list(height)[0])
            break
    ans = '{0} {1} {2}'.format(*ans)
    return ans

N = int(input())
Pos = [[int(i) for i in input().split()] for j in range(N)]
print(c_pyramid(N, Pos))

Fixed submission:
def c_pyramid(N, Pos):
    from itertools import product
    # 中心座標を全探索
    for cx, cy in product(range(101), repeat=2):
        # ピラミッドの高さを求める
        for x, y, h in Pos:
            if h > 0:
                height = h + abs(cx - x) + abs(cy - y)
        # ピラミッドの高さが得られた情報に適合するか調べる
        for x, y, h in Pos:
            if h != max((height - abs(cx - x) - abs(cy - y)), 0):
                break
        else:
            ans = [cx, cy, height]
            break
    ans = '{0} {1} {2}'.format(*ans)
    return ans

N = int(input())
Pos = [[int(i) for i in input().split()] for j in range(N)]
print(c_pyramid(N, Pos))
Buggy python submission (verdict: Runtime Error):
def d_partition(N, M):
    if N == 1:
        return M  # a_1 = M とする他なく、これが最大公約数

    def divisor_list(n):
        # n の正の約数のリスト
        ret = []
        for k in range(1, int(n**0.5) + 1):
            if n % k == 0:
                ret.extend([k, n // k])
        ret.sort()
        return ret

    divisor_m = divisor_list(M)
    ans = -1
    for d in divisor_m:
        if d <= M // N:
            ans = d
        else:
            break
    return ans

sys.stdin = io.StringIO(textwrap.dedent(INPUT).strip())
N, M = [int(i) for i in input().split()]
print(d_partition(N, M))

Fixed submission:
def d_partition(N, M):
    if N == 1:
        return M  # a_1 = M とする他なく、これが最大公約数

    def divisor_list(n):
        # n の正の約数のリスト
        ret = []
        for k in range(1, int(n**0.5) + 1):
            if n % k == 0:
                ret.extend([k, n // k])
        ret.sort()
        return ret

    divisor_m = divisor_list(M)
    ans = -1
    for d in divisor_m:
        if d <= M // N:
            ans = d
        else:
            break
    return ans

N, M = [int(i) for i in input().split()]
print(d_partition(N, M))
Buggy python submission (verdict: Runtime Error):
def d_make_them_even(H, W, A):
    from itertools import product
    # グリッドを -1 の壁で包む
    wall = [[-1] * (W + 2)]
    grid = wall + [[-1] + row + [-1] for row in A] + wall

    ans_tmp = []
    for h, w in product(range(H), range(W)):
        if grid[h][w] % 2 == 1:
            # コイン1枚をグリッドの右か下に押し付ける
            for dh, dw in zip((0, 1), (1, 0)):
                nh, nw = h + dh, w + dw
                if grid[nh][nw] != -1:
                    grid[nh][nw] += 1
                    grid[h][w] -= 1
                    ans_tmp.append('{0} {1} {2} {3}'.format(h + 1, w + 1, nh + 1, nw + 1))
                    break
    ans = '\n'.join([str(len(ans_tmp)), *ans_tmp])
    return ans

H, W = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for j in range(H)]
print(d_make_them_even(H, W, A))

Fixed submission:
def d_make_them_even(H, W, A):
    board = [row for row in A]
    ans = []
    for h in range(H):
        for w in range(W):
            if board[h][w] % 2 == 1:
                for nh, nw in zip((0, 1), (1, 0)):
                    if 0 <= h + nh <= H - 1 and 0 <= w + nw <= W - 1:
                        board[h + nh][w + nw] += 1
                        board[h][w] -= 1
                        ans.append('{0} {1} {2} {3}'.format(h + 1, w + 1, h + nh + 1, w + nw + 1))
                        break
    ans.insert(0, str(len(ans)))
    ans = '\n'.join(ans)
    return ans

H, W = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for j in range(H)]
print(d_make_them_even(H, W, A))
Buggy python submission (verdict: Runtime Error):
N = int(input())
if N < 105:
  print(0)
elif N < 135:
  print(1)
elif N < 165:
  print(2):
elif N < 189:
  print(3)
elif N < 195:
  print(4)
else:
  print(5)

Fixed submission:
N = int(input())
if N < 105:
    print(0)
elif N < 135:
    print(1)
elif N < 165:
    print(2)
elif N < 189:
    print(3)
elif N < 195:
    print(4)
else:
    print(5)
Buggy python submission (verdict: Runtime Error):
def c_to_infinity(S, K):
    for k, s in enumerate(S, 1):
        if k > K:
            ans = '1'  # K文字目まで1しかなかった
            break
        if s != '1':
            ans = s  # 現れた数字が5000兆回の操作によってK文字目に必ず現れる
            break
    return ans

S = input().strip()
K = int(input())
print(c_to_infinity(S, K))

Fixed submission:
def c_to_infinity(S, K):
    for k, s in enumerate(S,1):
        if s != '1':
            if k > K:
                return '1'
            else:
                return s
    # Sは1のみで構成されていた
    return 1

S = input().strip()
K = int(input())
print(c_to_infinity(S, K))
Buggy python submission (verdict: Time Limit Exceeded):
def c_linear_approximation(N, A):
    t = [None for _ in range(len(A))]
    for j, k in enumerate(A):
        t[j] = k - (j+1)
    t_min, t_max = min(t), max(t)
    ans = float('inf')
    for b in range(-abs(t_min), abs(t_max)+1):
        tmp = 0
        for k in t:
            tmp += abs(k-b)
        ans = min(ans, tmp)
    return ans
N = int(input())
A = [int(i) for i in input().split()]
print(c_linear_approximation(N, A))

Fixed submission:
def c_linear_approximation(N, A):
    import numpy
    B = numpy.array([a-k for k, a in enumerate(A)])
    b = int(numpy.median(B))
    ans = 0
    for b_k in B:
        ans += abs(b_k - b)
    return ans

N = int(input())
A = [int(i) for i in input().split()]
print(c_linear_approximation(N, A))

Buggy python submission (verdict: Time Limit Exceeded):
def c_linear_approximation(N, A):
    t = [None for _ in range(len(A))]
    for j, k in enumerate(A):
        t[j] = k - (j+1)
    t_min, t_max = min(t), max(t)
    ans = float('inf')
    for b in range(-abs(t_min), abs(t_max)+1):
        tmp = 0
        for k in t:
            tmp += abs(k-b)
        ans = min(ans, tmp)
    return ans
N = int(input())
A = [int(i) for i in input().split()]
print(c_linear_approximation(N, A))

Fixed submission:
def c_linear_approximation(N, A):
    import numpy
    B = numpy.array([a-k for k, a in enumerate(A)])
    b = int(numpy.median(B))
    ans = 0
    for b_k in B:
        ans += abs(b_k - b)
    return ans

N = int(input())
A = [int(i) for i in input().split()]
print(c_linear_approximation(N, A))
Buggy python submission (verdict: Runtime Error):
def d_snuke_numbers(K):
    candidate = []
    for k in range(20):
        for l in range(1, 10):
            candidate.append(str(l)+str(9)*k)
    ans = []
    for k in range(K):
        ans.append(candidate[k])
    ans = '\n'.join(ans)
    return ans

K = int(input())
print(d_snuke_numbers(K))

Fixed submission:
def d_snuke_numbers(K):
    import math

    def ns(n):  # n/S(n)の計算
        return n / sum(map(int, list(str(n))))

    def f(n):  # n<=xの中で ns(x) を最小にするような最小の値xを求める
        digit = len(str(n))
        # n自身も候補の1つである
        min_ns = ns(n)
        ret = n
        for d in range(digit + 1):
            x = (10**(d+1)) * math.floor(n / (10**(d+1)) + 1) - 1
            s = ns(x)
            if min_ns > s:
                min_ns = s
                ret = x
        return ret

    n = 0
    candidate = []
    for _ in range(K):
        n = f(n + 1)
        candidate.append(n)
    ans = '\n'.join(map(str, candidate))
    return ans

K = int(input())
print(d_snuke_numbers(K))

Buggy python submission (verdict: Runtime Error):
def d_snuke_numbers(K):
    candidate = []
    for k in range(16):
        for l in range(1, 10):
            candidate.append(str(l)+str(9)*k)
    ans = []
    for k in range(K):
        ans.append(candidate[k])
    ans = '\n'.join(ans)
    return ans

K = int(input())
print(d_snuke_numbers(K))

Fixed submission:
def d_snuke_numbers(K):
    import math

    def ns(n):  # n/S(n)の計算
        return n / sum(map(int, list(str(n))))

    def f(n):  # n<=xの中で ns(x) を最小にするような最小の値xを求める
        digit = len(str(n))
        # n自身も候補の1つである
        min_ns = ns(n)
        ret = n
        for d in range(digit + 1):
            x = (10**(d+1)) * math.floor(n / (10**(d+1)) + 1) - 1
            s = ns(x)
            if min_ns > s:
                min_ns = s
                ret = x
        return ret

    n = 0
    candidate = []
    for _ in range(K):
        n = f(n + 1)
        candidate.append(n)
    ans = '\n'.join(map(str, candidate))
    return ans

K = int(input())
print(d_snuke_numbers(K))

Buggy python submission (verdict: Runtime Error):
def d_snuke_numbers(K):
    candidate = []
    for k in range(15):
        for l in range(1, 10):
            candidate.append(str(l)+str(9)*k)
    ans = []
    for k in range(K):
        ans.append(candidate[k])
    ans = '\n'.join(ans)
    return ans

K = int(input())
print(d_snuke_numbers(K))

Fixed submission:
def d_snuke_numbers(K):
    import math

    def ns(n):  # n/S(n)の計算
        return n / sum(map(int, list(str(n))))

    def f(n):  # n<=xの中で ns(x) を最小にするような最小の値xを求める
        digit = len(str(n))
        # n自身も候補の1つである
        min_ns = ns(n)
        ret = n
        for d in range(digit + 1):
            x = (10**(d+1)) * math.floor(n / (10**(d+1)) + 1) - 1
            s = ns(x)
            if min_ns > s:
                min_ns = s
                ret = x
        return ret

    n = 0
    candidate = []
    for _ in range(K):
        n = f(n + 1)
        candidate.append(n)
    ans = '\n'.join(map(str, candidate))
    return ans

K = int(input())
print(d_snuke_numbers(K))