Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################
from fractions import gcd

# 最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)


A, B, C, D = map(int, input().split())

A -= 1

# a/b以下の条件を満たす数
nb = B - B//C - B//D + B//lcm(C, D)
na = A - A//C - A//D + A//lcm(C, D)

print(nb - na)


Fixed submission:
S = input()
before = ''
for x in S:
    if before == x:
        print('Bad')
        exit()
    before = x

print('Good')

Buggy python submission (verdict: Runtime Error):

n, l = map(int, input().split())

# 味リストはL, L+1, L+2...
tastes = []
for i in range(n):
    tastes += [l+i]

# 味0があったらそれを食えばいい
if 0 in tastes:
    print(sum(tastes))
else:
    # 差が最小なのを食えばいい
    tastes.sort(key=abs)
    print(sum(tastes[1:]))

Fixed submission:
S = input()
before = ''
for x in S:
    if before == x:
        print('Bad')
        exit()
    before = x

print('Good')
Buggy python submission (verdict: Runtime Error):
# 味リストはL, L+1, L+2...
tastes = []
for i in range(n):
    tastes += [l+i]

# 味0があったらそれを食えばいい
if 0 in tastes:
    print(sum(tastes))
else:
    # 差が最小なのを食えばいい
    tastes.sort(key=abs)
    print(sum(tastes[1:]))

Fixed submission:
n, l = map(int, input().split())

# 味リスト
tastes = []
for i in range(n):
    tastes += [l+i]

# 全部
all_tastes = sum(tastes)

# 食ったあとの味リスト
ptn = []
for x in tastes:
    ptn += [all_tastes - x]

# 元との差(abs)
di = []
for i in range(n):
    di += [abs(all_tastes - ptn[i])]

min_value = min(di)
print(ptn[di.index(min_value)])
Buggy python submission (verdict: Time Limit Exceeded):

N = int(input())

# (締切, 時間)
DeadlineCost = [] * N

for i in range(N):
    c, d = map(int, input().split())
    DeadlineCost.append((d, c))

DeadlineCost.sort()
#print(DeadlineCost)

t = 0
for i in range(N):
    (d, c) = DeadlineCost.pop(0)

    t += c
    if t > d:
        print('No')
        exit()

print('Yes')

Fixed submission:

N = int(input())

# (締切, 時間)
DeadlineCost = [] * N

for i in range(N):
    c, d = map(int, input().split())
    DeadlineCost.append((d, c))

DeadlineCost.sort(reverse=True)
#print(DeadlineCost)

t = 0
for i in range(N):
    (d, c) = DeadlineCost.pop()

    t += c
    if t > d:
        print('No')
        exit()

print('Yes')
Buggy python submission (verdict: Time Limit Exceeded):

import sys
sys.setrecursionlimit(1000000)

# 壊れている床を無視すればフィボナッチ数になってる
from collections import defaultdict

def Fib(n, dd, broken):
    if n in broken:
        return 0

    if dd[n] != 0:
        return dd[n]

    if n <= 1:
        return 1

    x = Fib(n-1, dd, broken) + Fib(n-2, dd, broken)
    dd[n] = x
    return x

dd = defaultdict(int)

n, m = map(int, input().split())
A = [int(input()) for _ in range(m)]

ans = Fib(n, dd, A)
print(ans % 1000000007)

Fixed submission:

# 壊れている床を無視すればフィボナッチ数になってる
from collections import defaultdict

def Fib(n, broken):
    dd = defaultdict(int)

    dd[0] = 1

    for i in range(n):
        for j in range(i+1, min(n, i+2)+1):
            if broken[j] == 0:
                dd[j] += dd[i]
                dd[j] %= 1000000007

    return dd[n]


n, m = map(int, input().split())
A = [int(input()) for _ in range(m)]
broken = defaultdict(int)
for c in A:
    broken[c] = 1

ans = Fib(n, broken)
print(ans % 1000000007)

Buggy python submission (verdict: Runtime Error):

# 壊れている床を無視すればフィボナッチ数になってる

from collections import defaultdict

def Fib(n, dd, broken):
    if n in broken:
        return 0

    if dd[n] != 0:
        return dd[n]

    if n <= 1:
        return 1

    x = Fib(n-1, dd, broken) + Fib(n-2, dd, broken)
    dd[n] = x
    return x

dd = defaultdict(int)

n, m = map(int, input().split())
A = [int(input()) for _ in range(m)]

ans = Fib(n, dd, A)
print(ans % 1000000007)

Fixed submission:

# 壊れている床を無視すればフィボナッチ数になってる
from collections import defaultdict

def Fib(n, broken):
    dd = defaultdict(int)

    dd[0] = 1

    for i in range(n):
        for j in range(i+1, min(n, i+2)+1):
            if broken[j] == 0:
                dd[j] += dd[i]
                dd[j] %= 1000000007

    return dd[n]


n, m = map(int, input().split())
A = [int(input()) for _ in range(m)]
broken = defaultdict(int)
for c in A:
    broken[c] = 1

ans = Fib(n, broken)
print(ans % 1000000007)
Buggy python submission (verdict: Runtime Error):
give up

Fixed submission:

N, M = map(int,input().split())
src = [tuple(map(int,input().split())) for i in range(M)]
P = list(map(int,input().split()))

ans = 0
# (0, 1, 2, ... 2^n-1) の部分集合の全探索（0を含むので合計2^n個)
# 例えば8なら、000〜111までの全部なので、スイッチの全パターンをなめる
for b in range(1<<N):  # 2**nでも一緒
    # 縦軸（M個の電球）→ スイッチ0の電球全部、スイッチ1の電球全部, ...
    for i in range(M):
        c = 0

        # スイッチ番号を順番に取得
        for s in src[i][1:]:
            # bにswitch_num番目のフラグがたってるか？
            # つまり、全探索のなかで、ビットがたってたら「処理をする」というだけ
            switch_num = s-1

            # どうせ全部なめるので、どっちでもいい
#            if b & (1<<(switch_num)):
            if (b >> switch_num) & 1 == 1:
                c += 1

        if c%2 != P[i]:
            break
    else:
        # 割り切れたらその電球は点いてるのでカウント対象
        ans += 1

print(ans)
Buggy python submission (verdict: Runtime Error):
cannot understand the q

Fixed submission:


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

N, M = map(int, input().split())
L = [0] * M
R = [0] * M
for i in range(M):
    l, r = map(int, input().split())
    L[i] = l
    R[i] = r

left = max(L)
right = min(R)

if left <= right:
    print(right-left+1)
else:
    print(0)
Buggy python submission (verdict: Time Limit Exceeded):

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################


N, Q = map(int, input().split())
S = input().rstrip()
for i in range(Q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1

    count = 0
    for j in range(l+1, r+1):
        if S[j-1] == 'A' and S[j] == 'C':
            count += 1
    print(count)


Fixed submission:

N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)

'''
累積和
t[1] = t[0] + (if S[0]からの2文字がACなら1 or 0) → AC の C 位置なら1
t[2] = t[1] + (if S[1]からの2文字がACなら1 or 0)
t[3] = t[2] + (if S[2]からの2文字がACなら1 or 0)
t[4] = t[3] + (if S[3]からの2文字がACなら1 or 0)
t[5] = t[4] + (if S[4]からの2文字がACなら1 or 0)
t[6] = t[5] + (if S[5]からの2文字がACなら1 or 0)
t[7] = t[6] + (if S[6]からの2文字がACなら1 or 0)
t[8] = t[7] + (if S[7]からの2文字がACなら1 or 0)

# 01234567
# ACACTACG
# 011222333
'''

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

#print(t)

for i in range(Q):
    l, r = map(int, input().split())

    # 3, 7 なら、t[7-1] - t[3-1]
    #  → t[5]以下の数 - t[1]以下の数
    print(t[r-1] - t[l-1])

Buggy python submission (verdict: Time Limit Exceeded):

N, Q = map(int, input().split())
S = input()
for _ in range(Q):
    l, r = map(int, input().split())
    p = S[l-1:r]

    print(p.count('AC'))

Fixed submission:

N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)

'''
累積和
t[1] = t[0] + (if S[0]からの2文字がACなら1 or 0) → AC の C 位置なら1
t[2] = t[1] + (if S[1]からの2文字がACなら1 or 0)
t[3] = t[2] + (if S[2]からの2文字がACなら1 or 0)
t[4] = t[3] + (if S[3]からの2文字がACなら1 or 0)
t[5] = t[4] + (if S[4]からの2文字がACなら1 or 0)
t[6] = t[5] + (if S[5]からの2文字がACなら1 or 0)
t[7] = t[6] + (if S[6]からの2文字がACなら1 or 0)
t[8] = t[7] + (if S[7]からの2文字がACなら1 or 0)

# 01234567
# ACACTACG
# 011222333
'''

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

#print(t)

for i in range(Q):
    l, r = map(int, input().split())

    # 3, 7 なら、t[7-1] - t[3-1]
    #  → t[5]以下の数 - t[1]以下の数
    print(t[r-1] - t[l-1])

Buggy python submission (verdict: Time Limit Exceeded):

N, Q = map(int, input().split())
S = input()
for _ in range(Q):
    l, r = map(int, input().split())
    p = S[l-1:r]

    print(p.replace('AC', 'x').count('x'))

Fixed submission:

N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)

'''
累積和
t[1] = t[0] + (if S[0]からの2文字がACなら1 or 0) → AC の C 位置なら1
t[2] = t[1] + (if S[1]からの2文字がACなら1 or 0)
t[3] = t[2] + (if S[2]からの2文字がACなら1 or 0)
t[4] = t[3] + (if S[3]からの2文字がACなら1 or 0)
t[5] = t[4] + (if S[4]からの2文字がACなら1 or 0)
t[6] = t[5] + (if S[5]からの2文字がACなら1 or 0)
t[7] = t[6] + (if S[6]からの2文字がACなら1 or 0)
t[8] = t[7] + (if S[7]からの2文字がACなら1 or 0)

# 01234567
# ACACTACG
# 011222333
'''

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

#print(t)

for i in range(Q):
    l, r = map(int, input().split())

    # 3, 7 なら、t[7-1] - t[3-1]
    #  → t[5]以下の数 - t[1]以下の数
    print(t[r-1] - t[l-1])
Buggy python submission (verdict: Time Limit Exceeded):

S = input()
s = S

before_len = 0
while True:
    s = s.replace('0011', '').replace('1100', '').replace('0101', '').replace('1010', '').replace('01', '').replace('10', '')
    lens = len(s)
    if before_len == lens:
        break

    before_len = lens


print(len(S) - len(s))

Fixed submission:

S = input()
print(2 * min(S.count('0'), S.count('1')))
Buggy python submission (verdict: Runtime Error):

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

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

diff = []
for i in range(M-1):
    diff.append(X[i+1] - X[i])

#print(diff)

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

diff.sort()
for i in range(N-1):
    diff.pop()

print(sum(diff))

Fixed submission:

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

if N >= M:
    print(0)
    exit()

diff = []
for i in range(M-1):
    diff.append(X[i+1] - X[i])

#print(diff)

diff.sort()
for i in range(N-1):
    diff.pop()

print(sum(diff))
Buggy python submission (verdict: Time Limit Exceeded):

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

N, K = map(int, input().split())
H = list(map(int, input().split()))

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

print(dp[-1])

Fixed submission:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

N, K = map(int, input().split())
H = list(map(int, input().split()))

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

print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

N, K = map(int, input().split())
H = list(map(int, input().split()))

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

print(dp[-1])

Fixed submission:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

N, K = map(int, input().split())
H = list(map(int, input().split()))

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

print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):

import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# A = [ int(input()) for _ in range(N) ]
##############################

N, W = map(int, input().split())
w = []
v = []
for i in range(N):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)

dp = [ [0 for _ in range(W+1)] for _ in range(N+1) ]

for i in range(1, N+1):
    for j in range(1, W+1):
        if j < w[i-1]:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]]+v[i-1])

print(dp[N][W])

Fixed submission:


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################


N, W = map(int, input().split())
w = [0] * N
v = [0] * N

for i in range(N):
    a, b = map(int, input().split())
    w[i] = a
    v[i] = b

dp = [ [0 for _ in range(W+1)] for _ in range(N+1) ]

for i  in range(N):
    for sum_w in range(W+1):
        if sum_w - w[i] >= 0:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w-w[i]] + v[i])

        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])

print(dp[N][W])

Buggy python submission (verdict: Time Limit Exceeded):


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################


N, W = map(int, input().split())
w = [0] * N
v = [0] * N

for i in range(N):
    a, b = map(int, input().split())
    w[i] = a
    v[i] = b

dp = [ [0 for _ in range(W+1)] for _ in range(N+1) ]

for i  in range(N):
    for sum_w in range(W+1):
        if sum_w - w[i] >= 0:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w-w[i]] + v[i])

        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])

print(dp[N][W])


Fixed submission:


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################


N, W = map(int, input().split())
w = [0] * N
v = [0] * N

for i in range(N):
    a, b = map(int, input().split())
    w[i] = a
    v[i] = b

dp = [ [0 for _ in range(W+1)] for _ in range(N+1) ]

for i  in range(N):
    for sum_w in range(W+1):
        if sum_w - w[i] >= 0:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w-w[i]] + v[i])

        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])

print(dp[N][W])
Buggy python submission (verdict: Time Limit Exceeded):

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################


# https://qiita.com/drken/items/dc53c683d6de8aeacf5a#e-問題---knapsack-2


# N個の荷物、ナップザックの容量はW
N, W = map(int, input().split())
w = [0] * N
v = [0] * N

for i in range(N):
    a, b = map(int, input().split())
    w[i] = a
    v[i] = b

# 1 <= W <= 10^9なので横軸をWにするとテーブルがでかすぎる
# そのかわりにVの方を横軸にする


# 価値の総合計はまだ不明なので、適当にでかい値にしとく
# 最上部と最左部に0が入るので、その分を+1
V = 10**5
#dp = [ [0 for _ in range(W+1)] for _ in range(N+1) ]
dp = [ [float('inf') for _ in range(V+1)] for _ in range(N+1) ]

# 最小値を求めるので、上記でinfが入ってるので、初期値は0をいれる必要がある
dp[0][0] = 0

# dp[i][sum_v] = これまで(i-1)番目までの品物から価値がsum_v以上になるように選んだときの、重さの総和の最小値
for i in range(N):
    for sum_v in range(V):
        if sum_v - v[i] >= 0:
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v-v[i]]+w[i])

        dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])


# 中身がWなので、W以下であるうちのsum_vの最大値を求めればいい
for sum_v in range(V):
    # 最終行だけ見ればいいので、端からsum_vの最大値をなめるだけ
    if dp[N][sum_v] <= W:
        ans = sum_v

print(ans)


Fixed submission:


# N個の荷物、ナップザックの容量はW
N, W = map(int, input().split())
w = [0] * N
v = [0] * N

for i in range(N):
    a, b = map(int, input().split())
    w[i] = a
    v[i] = b

# 1 <= W <= 10^9なので横軸をWにするとテーブルがでかすぎる
# そのかわりにVの方を横軸にする

# 価値の総合計はまだ不明なので、適当にでかい値にしとく
# 最上部と最左部に0が入るので、その分を+1
V = N*1000+1
dp = [ [float('inf') for _ in range(V+1)] for _ in range(N+1) ]

# 最小値を求めるので、上記でinfが入ってるので、初期値は0をいれる必要がある
dp[0][0] = 0

# dp[i][sum_v] = これまで(i-1)番目までの品物から価値がsum_v以上になるように選んだときの、重さの総和の最小値
for i in range(N):
    for sum_v in range(V):
        if sum_v - v[i] >= 0:
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v-v[i]]+w[i])

        dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])


# 中身がWなので、W以下であるうちのsum_vの最大値を求めればいい
for sum_v in range(V):
    # 最終行だけ見ればいいので、端からsum_vの最大値をなめるだけ
    if dp[N][sum_v] <= W:
        ans = sum_v

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



import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

# https://qiita.com/drken/items/03c7db44ccd27820ea0d#f-問題---lcs
S = input().rstrip()
T = input().rstrip()

X = len(S) + 100
dp = [ [0 for _ in range(X)] for _ in range(X) ]

# DP作成
for i in range(len(S)):
    for j in range(len(T)):
        if S[i] == T[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+1)

        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j])
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1])

# 復元
ans = ""
i = len(S)
j = len(T)
while i > 0 and j > 0:
    if (dp[i][j] == dp[i-1][j]):
        i -= 1
    elif (dp[i][j] == dp[i][j-1]):
        j -= 1
    else:
        ans = S[i-1]+ans
        i -= 1
        j -= 1

print(ans)

Fixed submission:



import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

# https://qiita.com/drken/items/03c7db44ccd27820ea0d#f-問題---lcs
S = input().rstrip()
T = input().rstrip()

X = len(S) + 100
dp = [ [0 for _ in range(X)] for _ in range(X) ]

# DP作成
for i in range(len(S)):
    for j in range(len(T)):
        if S[i] == T[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+1)

        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j])
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1])

# 復元
ans = ""
i = len(S)
j = len(T)
while i > 0 and j > 0:
    if (dp[i][j] == dp[i-1][j]):
        i -= 1
    elif (dp[i][j] == dp[i][j-1]):
        j -= 1
    else:
        ans = S[i-1]+ans
        i -= 1
        j -= 1

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

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

from collections import defaultdict

N, M = map(int, input().split())
P = [0] * M
Y = [0] * M
dd = defaultdict(list)

for i in range(M):
    p, y = map(int, input().split())
    P[i] = p
    Y[i] = y

    dd[p].append(y)

for k, v in dd.items():
    v.sort()
    dd[k] = v

#print(dd)

for i in range(M):
    p = P[i]
    y = Y[i]

    print('{0:06d}'.format(p), end='')
    x = dd[p].index(y) +1
    print('{0:06d}'.format(x))

Fixed submission:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

N, M = map(int, input().split())
src = [tuple(map(int, input().split())) for _ in range(M)]
#print(src)

# 1-index なので+1
X = [ [] for _ in range(N+1) ]

for i, (p, y) in enumerate(src):
    X[p].append((y, i))
for c in X:
    c.sort()

#print(X)

ans = [None] * M
for p in range(len(X)):
    # 0([])の場合は、通らない
    for i,(_,j) in enumerate(X[p]):
        s = str(p).zfill(6) + str(i+1).zfill(6)
        ans[j] = s

print(*ans, sep='\n')
Buggy python submission (verdict: Runtime Error):


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

N, K = map(int, input().split())
X = list(map(int, input().split()))

left = []
right = []

# ある意味もとから累積和
for c in X:
    if c < 0:
        left.append(abs(c*2))
    else:
        right.append(c)

# 番兵
left.append(0)
left.reverse()
#print(left, right)


# i 個、左から取る
ans = float('inf')
for i in range(len(left)):
    remain = K-i

    # 個数足りない
    if len(right[:remain]) < remain:
        continue

    x = left[i] + right[K-i-1]
#    print(x, left[i], right[K-i-1])
    ans = min(ans, x)

print(ans)

Fixed submission:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################


'''
https://img.atcoder.jp/arc101/editorial.pdf
https://atcoder.jp/contests/abc107/submissions/5375441

l → r の順：|xl| + |xr-xl|
r → l の順：|xr| + |xr-xl|
'''


N, K = map(int, input().split())
X = list(map(int, input().split()))

ans = float('inf')
for i in range(N-K+1):
    left = X[i]
    right = X[i+K-1]
    ans = min(ans, abs(left)+abs(right-left), abs(right)+abs(left-right))

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

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

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

def right(N, A):
    X = [0] * N
    for i in range(N):
        X[i] = abs(A[i] - (i+1))

    return max(X)

r = right(N, A)
#print(r)

ans = float('inf')
for b in range(-r, r+1):
    c = 0
    for i in range(1, N+1):
        c += abs(A[i-1] - (b+i))

    ans = min(ans, c)

print(ans)

Fixed submission:


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

N = int(input())
A = list(map(int, input().split()))
a = [0] * len(A)

# bの値は中央値
# https://qiita.com/Noiri/items/291ae9bf4a2eacab6f5f
for i in range(N):
    a[i] = A[i]-i-1

a.sort()
b = a[N // 2 - 1] if (N % 2 == 0) else a[(N + 1) // 2 - 1]

ans = 0
for i in range(N):
    ans += abs(a[i] - b)

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

import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
##############################

S = input().rstrip()
K = int(input())

N = len(S)

ret = []
for nums in range(1, N+1):
    for i in range(N):
        s = S[i:i+nums]
        ret.append(s)

ret = sorted(set(ret))

print(ret[K-1])

Fixed submission:

import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
##############################

S = input().rstrip()
K = int(input())

N = len(S)

ret = []
for nums in range(1, K+1):
    for i in range(N):
        s = S[i:i+nums]
        ret.append(s)

ret = sorted(set(ret))
print(ret[K-1])

Buggy python submission (verdict: Time Limit Exceeded):

import sys
input = sys.stdin.readline
##############################

S = input().rstrip()
K = int(input())

N = len(S)

ret = []
for nums in range(1, N+1):
    for i in range(N):
        s = S[i:i+nums]
        if not s in ret:
            ret.append(s)

ret.sort()

print(ret[K-1])

Fixed submission:

import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
##############################

S = input().rstrip()
K = int(input())

N = len(S)

ret = []
for nums in range(1, K+1):
    for i in range(N):
        s = S[i:i+nums]
        ret.append(s)

ret = sorted(set(ret))
print(ret[K-1])
Buggy python submission (verdict: Time Limit Exceeded):

import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# A = [ int(input()) for _ in range(N) ]
##############################

import math
from collections import defaultdict

# 組み合わせ
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


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

A.sort(reverse=True)

max_v = 0
ans = 0
for i in range(N-1):
    memo = defaultdict(int)
    for j in range(i+1, N):
        if memo[A[j]] > 0:
            continue

        x = combinations_count(A[i], A[j])
        memo[A[j]] = x
#        print(x, A[i], A[j])
        if x > max_v:
            max_v = x
            ans = (A[i], A[j])

print(*ans)

Fixed submission:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# A = [ int(input()) for _ in range(N) ]
##############################

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

left = max(A)
center = left // 2

right = 0
diff = INF
for i in range(N):
    if A[i] == left:
        continue

    x = abs(center-A[i])
    if diff > x:
        diff = x
        right = A[i]

print(left, right)

Buggy python submission (verdict: Time Limit Exceeded):

import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# A = [ int(input()) for _ in range(N) ]
##############################

import math

# 組み合わせ
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


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

A.sort(reverse=True)

max_v = 0
ans = 0
for i in range(N-1):
    for j in range(i+1, N):
        x = combinations_count(A[i], A[j])
#        print(x, A[i], A[j])
        if x > max_v:
            max_v = x
            ans = (A[i], A[j])

print(*ans)

Fixed submission:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# A = [ int(input()) for _ in range(N) ]
##############################

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

left = max(A)
center = left // 2

right = 0
diff = INF
for i in range(N):
    if A[i] == left:
        continue

    x = abs(center-A[i])
    if diff > x:
        diff = x
        right = A[i]

print(left, right)