Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))

# X1の拘束条件
# A1 * 2 && last
X1_up = min(A[0], A[-1]) * 2
Xlast_up = min(A[-1], A[-2]) * 2

def chk(x1, xlast):
    prev = x1
    for index in range(len(A)-1):
        d = 2 * (A[index] - int(prev //2))
        prev = d
    return prev == xlast


ansx1 = -1
ansxlast = -1
is_found = False
for x1 in range(0,X1_up + 1, 2):
    for xlast in range(0, Xlast_up + 1, 2):
        if x1 == 2 * A[-1] - xlast and chk(x1, xlast): 
            ansx1 = x1
            ansxlast = xlast
            is_found = True
            break
    if is_found:
        break


ans = []
ans.append(ansx1)
prev = ansx1
for index in range(len(A)-1):
    d = 2 * (A[index] - int(prev //2))
    ans.append(d)
    prev = d

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



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

# X1の拘束条件
# A1 * 2 && last

ansx1 = 0
is_m = False
for a in reversed(A):
    if is_m:
        ansx1 -= a
    else:
        ansx1 += a
    is_m = not is_m


ans = []
ans.append(ansx1)
prev = ansx1
for index in range(len(A)-1):
    d = 2 * (A[index] - int(prev //2))
    ans.append(d)
    prev = d

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


N, K = map(int, input().split())
MOD = 10 ** 9 + 7

def comb(n, k):
    return math.factorial(n) // math.factorial(k) // math.factorial(n - k)

for i in range(1, K + 1):
    if i > N-K+1:
        print(0)
    blue = comb(N-K+1, i) % MOD
    red = comb(K-1, i-1) % MOD

    ans = blue * red % MOD
    print(ans)


Fixed submission:
import math


N, K = map(int, input().split())
MOD = 10 ** 9 + 7

def comb(n, k):
    return math.factorial(n) // math.factorial(k) // math.factorial(n - k)

for i in range(1, K + 1):
    if i > N-K+1:
        print(0)
        continue
    blue = comb(N-K+1, i) % MOD
    red = comb(K-1, i-1) % MOD

    ans = blue * red % MOD
    print(ans)

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


N, K = map(int, input().split())
MOD = 10 ** 9 + 7

def comb(n, k):
    return math.factorial(n) // math.factorial(k) // math.factorial(n - k)

for i in range(1, K + 1):
    blue = comb(N-K+1, i) % MOD
    red = comb(K-1, i-1) % MOD

    ans = blue * red % MOD
    print(ans)


Fixed submission:
import math


N, K = map(int, input().split())
MOD = 10 ** 9 + 7

def comb(n, k):
    return math.factorial(n) // math.factorial(k) // math.factorial(n - k)

for i in range(1, K + 1):
    if i > N-K+1:
        print(0)
        continue
    blue = comb(N-K+1, i) % MOD
    red = comb(K-1, i-1) % MOD

    ans = blue * red % MOD
    print(ans)

Buggy python submission (verdict: Runtime Error):
from scipy.misc import comb

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

def f2(n, k):
    return int(comb(n+k-1, k - 1))

def f(n, k):
    if n < k:
        return 0
    if k < 1:
        return 0
    if n == 0 and k== 0:
        return 0
    return f2(n-k, k)



for i in range(1, K + 1):
    blue = f(K, i)
    red = 0
    red += f(N - K, i - 1)
    red += f(N - K, i)
    red += f(N - K, i)
    red += f(N - K, i+1)

    ans = blue * red
    print(ans)


Fixed submission:
import math


N, K = map(int, input().split())
MOD = 10 ** 9 + 7

def comb(n, k):
    return math.factorial(n) // math.factorial(k) // math.factorial(n - k)

for i in range(1, K + 1):
    if i > N-K+1:
        print(0)
        continue
    blue = comb(N-K+1, i) % MOD
    red = comb(K-1, i-1) % MOD

    ans = blue * red % MOD
    print(ans)

Buggy python submission (verdict: Runtime Error):
from scipy.special import comb

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

def f2(n, k):
    return int(comb(n+k-1, k - 1))

def f(n, k):
    if n < k:
        return 0
    if k < 1:
        return 0
    if n == 0 and k== 0:
        return 0
    return f2(n-k, k)



for i in range(1, K + 1):
    blue = f(K, i)
    red = 0
    red += f(N - K, i - 1)
    red += f(N - K, i)
    red += f(N - K, i)
    red += f(N - K, i+1)

    ans = blue * red
    print(ans)


Fixed submission:
import math


N, K = map(int, input().split())
MOD = 10 ** 9 + 7

def comb(n, k):
    return math.factorial(n) // math.factorial(k) // math.factorial(n - k)

for i in range(1, K + 1):
    if i > N-K+1:
        print(0)
        continue
    blue = comb(N-K+1, i) % MOD
    red = comb(K-1, i-1) % MOD

    ans = blue * red % MOD
    print(ans)
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]


MOD = 1000000007

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

dp[0] = 1



next_ng_index = 0

for index in range(N):
    current = index + 1
    if current == A[next_ng_index]:
        next_ng_index += 1
        if next_ng_index == M:
            next_ng_index = 0
        continue

    pre_stair = current - 1
    dp[current] += dp[pre_stair]

    prepre_stair = current -2
    if prepre_stair >= 0:
        dp[current] += dp[prepre_stair]

    dp[current] %= MOD

print(dp[-1]%MOD)







Fixed submission:
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
A.append(-1)


MOD = 1000000007

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

dp[0] = 1



next_ng_index = 0

for index in range(N):
    current = index + 1
    if current == A[next_ng_index]:
        next_ng_index += 1
        continue

    pre_stair = current - 1
    dp[current] += dp[pre_stair]

    prepre_stair = current -2
    if prepre_stair >= 0:
        dp[current] += dp[prepre_stair]

    dp[current] %= MOD

print(dp[-1]%MOD)

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]


MOD = 1000000007

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

dp[0] = 1

for index in range(N):
    current = index + 1
    if current in A:
        continue

    pre_stair = current - 1
    dp[current] += dp[pre_stair]

    prepre_stair = current -2
    if prepre_stair >= 0:
        dp[current] += dp[prepre_stair]

    dp[current] %= MOD

print(dp[-1]%MOD)







Fixed submission:
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
A.append(-1)


MOD = 1000000007

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

dp[0] = 1



next_ng_index = 0

for index in range(N):
    current = index + 1
    if current == A[next_ng_index]:
        next_ng_index += 1
        continue

    pre_stair = current - 1
    dp[current] += dp[pre_stair]

    prepre_stair = current -2
    if prepre_stair >= 0:
        dp[current] += dp[prepre_stair]

    dp[current] %= MOD

print(dp[-1]%MOD)
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int,input().split())) for _ in range(M)]

A.sort()
BC.sort(key=lambda x:x[1], reverse=True)

a_i = 0
is_fin = False
for b, c in BC:
    if is_fin:
        break

    for _ in range(b):
        if A[a_i] < c:
            A[a_i] = c 
            a_i += 1
        else:
            is_fin = True
            break

print(sum(A))


Fixed submission:
N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int,input().split())) for _ in range(M)]

A.sort()
BC.sort(key=lambda x:x[1], reverse=True)

a_i = 0
is_fin = False
for b, c in BC:
    if is_fin:
        break

    for _ in range(b):
        if A[a_i] < c:
            A[a_i] = c 
            a_i += 1
            if a_i >= len(A):
                is_fin = True
                break
        else:
            is_fin = True
            break

print(sum(A))
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import combinations

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

devide_num = min(N -1, M - 1)

devides = combinations(range(len(X)), devide_num)


mincost = X[-1] - X[0]
for devide in devides:
    previous = 0
    cost = 0
    for next_point in devide:
        cost += X[next_point] - X[previous]
        if next_point + 1 < M:
            previous = next_point + 1
        else:
            break
    # last
    cost += X[-1] - X[previous]

    mincost = min(cost, mincost)

print(mincost)






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

diffs = [X[i+ 1] - X[i] for i in range(len(X) - 1)]
diffs.sort(reverse=True)

skip = N - 1
print(sum(diffs[skip:]))
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
h = list(map(int, input().split()))

MAX = pow(10, 4) * N
costs = [MAX for _ in range(N)]
costs[0] = 0

for h_i in range(N - 1):
    next_step = h_i + 1
    back_max = min(next_step, K)
    for back_index in range(back_max):
        costs[next_step] = min(abs(h[next_step] - h[next_step - back_index -1]) + costs[next_step - back_index -1 ], costs[next_step])


print(costs[N - 1])


Fixed submission:
N, K = map(int, input().split())
h = list(map(int, input().split()))

MAX = pow(10, 4) * N
costs = [MAX for _ in range(N)]
costs[0] = 0

for h_i in range(N - 1):
    next_step = h_i + 1
    back_max = min(next_step, K)
    for back_index in range(back_max):
        costs[next_step] = min(abs(h[next_step] - h[next_step - back_index -1]) + costs[next_step - back_index -1 ], costs[next_step])


print(costs[N - 1])

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
h = list(map(int, input().split()))

MAX = pow(10, 4) * N
costs = [MAX for _ in range(N)]
costs[0] = 0

for h_i in range(N):
    move_max = min(N - h_i - 1, K) 
    for step in range(1, move_max + 1):
        costs[h_i + step] = min(abs(h[h_i + step] - h[h_i]) + costs[h_i], costs[h_i + step])


print(costs[N - 1])


Fixed submission:
N, K = map(int, input().split())
h = list(map(int, input().split()))

MAX = pow(10, 4) * N
costs = [MAX for _ in range(N)]
costs[0] = 0

for h_i in range(N - 1):
    next_step = h_i + 1
    back_max = min(next_step, K)
    for back_index in range(back_max):
        costs[next_step] = min(abs(h[next_step] - h[next_step - back_index -1]) + costs[next_step - back_index -1 ], costs[next_step])


print(costs[N - 1])
Buggy python submission (verdict: Time Limit Exceeded):
import copy
N, W = map(int, input().split())

WV = [map(int,input().split()) for _ in range(N) ]


costs = [(0,0)]

for w, v in WV:
    new_costs = copy.deepcopy(costs)
    for cw, cv in costs:
        if cw + w > W:
            continue
        new_costs.append((cw + w, cv + v))
    costs = new_costs



print( max(costs,key=lambda item:item[1])[1])



Fixed submission:
import copy
N, W = map(int, input().split())

WV = [map(int,input().split()) for _ in range(N) ]


#dp[w] = max cost
costs = [-1 for _ in range(W + 1)]
costs[0] = 0

for w, v in WV:
    for index in reversed(range(W + 1)):
        if costs[index] == -1:
            continue
        if index + w > W:
            continue
        costs[index + w] = max(costs[index] + v, costs[index + w])


print(max(costs))
Buggy python submission (verdict: Time Limit Exceeded):
import copy
N, W = map(int, input().split())

WV = [map(int,input().split()) for _ in range(N) ]


#dp[w] = max cost
costs = [-1 for _ in range(W + 1)]
costs[0] = 0

for w, v in WV:
    for index in reversed(range(W + 1)):
        if costs[index] == -1:
            continue
        if index + w > W:
            continue
        costs[index + w] = max(costs[index] + v, costs[index + w])


print(max(costs))



Fixed submission:
N, W = map(int, input().split())
WV = [list(map(int, input().split())) for _ in range(N)]

max_weight = W + 1
max_cost = sum([v for w,v in WV])
dp = [max_weight for _ in range(max_cost + 1)]
# dp[cost] weight
dp[0] = 0

for w,v in WV:
    for index in reversed(range(len(dp))):
        if dp[index] == max_weight:
            continue

        dp[index + v] = min(dp[index + v], dp[index] + w)


for cost in reversed(range(max_cost + 1)):
    if dp[cost]<=W:
        print(cost)
        break
Buggy python submission (verdict: Runtime Error):
 N, K = map(int, input().split())
H = [int(input()) for _ in range(N)]

H.sort(reverse=True)

min_score = pow(10, 9)
for i in range(N - K + 1):
    min_score = min(min_score, H[i] - H[i + K - 1])

print(min_score)



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

H.sort(reverse=True)

min_score = pow(10, 9)
for i in range(N - K + 1):
    min_score = min(min_score, H[i] - H[i + K - 1])

print(min_score)
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
A = list(map(int, input().split()))

# 累積和

cumsum = [0]
for i in range(len(A)):
    cumsum.append(cumsum[i] + A[i])

ret = 0
for l in range(1, N+1):
    for r in range(l, N+1):
        s = cumsum[r] - cumsum[l -1]
        if s % M == 0:
            ret += 1
print(ret)


Fixed submission:
from collections import defaultdict

N, M = map(int, input().split())
A = list(map(int, input().split()))
 
# 累積和
 
cumsum = [0]
for i in range(len(A)):
    cumsum.append(cumsum[i] + A[i])
 
mod_cumsum = []
for i in cumsum:
    mod_cumsum.append(i % M)

moddict = defaultdict(int)

ret = 0
for i in mod_cumsum:
    ret += moddict[i]
    moddict[i] += 1

    
print(ret)
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
ab = []
for _ in range(M):
    a, b = map(int, input().split())
    ab.append((a,b))

# bの昇順でsort
ab.sort(key=lambda inv: inv[1])   


count = 0
while(0 < len(ab)):
    count += 1
    cutb = ab[0][1]
    # cutbで除外できる闘争を除外する
    remove_list = []
    for i in range(len(ab)):
        a, b = ab[i]
        if a <= cutb - 1 and cutb <= b:
            remove_list.append(i)

    for remove_index in reversed(remove_list):
        ab.pop(remove_index)

print(count)


Fixed submission:
N, M = map(int, input().split())
ab = []
for _ in range(M):
    a, b = map(int, input().split())
    ab.append((a,b))

# bの昇順でsort
ab.sort(key=lambda inv: inv[1])   


count = 0
while(0 < len(ab)):
    count += 1
    cutb = ab[0][1]
    # cutbで除外できる闘争を除外する
    remove_index = 0
    for i in range(len(ab)):
        a, b = ab[i]
        if a <= cutb - 1 and cutb <= b:
            remove_index = i
        else:
            break

    ab = ab[remove_index+1:]

print(count)
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))

def sunuke(b):
    ret = 0
    sub = 1
    for a in A:
        ret += abs(a - (b+ sub))
        sub += 1
    return ret


B = []

sub = 1
for a in A:
    b = a - sub
    B.append(b)
    sub += 1

B.sort()
b1 = N // 2
if N < 3:
    print(sunuke(B[b1]))
    exit()

b2 = b1 + 1
b1_s = sunuke(B[b1])
b2_s = sunuke(B[b2])
if b1_s < b2_s:
    print(b1_s)
else:
    print(b2_s)


Fixed submission:
N = int(input())

if N % 2 == 0:
    print(N)
else:
    print(N * 2)
Buggy python submission (verdict: Time Limit Exceeded):
import itertools


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

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

max_socre = 0
for cakes in itertools.combinations(scores, m):
    b = 0
    t = 0
    p = 0
    for cake in cakes:
        b += cake[0]
        t += cake[1]
        p += cake[2]

    score = abs(b) + abs(t) + abs(p)
    if score > max_socre:
        max_socre = score

print(max_socre)



Fixed submission:
import itertools


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

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

# 8 pattern

max_of_sum = 0
for pick in range(8):
    sum_scores = []
    for score in scores:
        sum_of_score = 0
        if pick & 0b001 == 0:
            # plus
            sum_of_score += score[0]
        else:
            sum_of_score -= score[0]

        if pick & 0b010 == 0:
            # plus
            sum_of_score += score[1]
        else:
            sum_of_score -= score[1]

        if pick & 0b100 == 0:
            # plus
            sum_of_score += score[2]
        else:
            sum_of_score -= score[2]

        sum_scores.append(sum_of_score)

    sum_scores.sort(reverse=True)
    current_sum = sum(sum_scores[:m])
    if current_sum > max_of_sum:
        max_of_sum = current_sum

print(max_of_sum)
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import permutations

N, C = map(int, input().split())

d = [list(map(int, input().split()))  for i in range(C)] 
c = [list(map(int, input().split()))  for i in range(N)] 

# 3行にまとめる
c_listed = [[],[],[]]

for i in range(N):
    for j in range(N):
        index = (i + j) % 3
        c_listed[index].append(c[i][j])



# 色の選び方
color_seq = permutations(range(C), 3)

ret = N * N * 1000
for color in color_seq:
    count = 0
    for line, line_color in zip(c_listed, color):
        for f in line:
            # f to line_color
            count += d[f-1][line_color]

    # 
    if count < ret:
        ret = count

print(ret)



Fixed submission:
from itertools import permutations

N, C = map(int, input().split())

d = [list(map(int, input().split()))  for i in range(C)] 
c = [list(map(int, input().split()))  for i in range(N)] 

# 3行にまとめる
c_listed = [{},{},{}]

for i in range(N):
    for j in range(N):
        index = (i + j) % 3
        c_listed[index][c[i][j]] = c_listed[index].get(c[i][j], 0) + 1

# 色の選び方
color_seq = permutations(range(C), 3)

ret = N * N * 1000
for color in color_seq:
    count = 0
    for line, line_color in zip(c_listed, color):
        for f, v in line.items():
            # f to line_color
            count += d[f-1][line_color] * v

    # 
    if count < ret:
        ret = count

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

base = 998244353

n, a, b, k =  map(int, input().split())

fac = [1] * (n + 1)
rev = [1] * (n + 1)
for i in range(1, n + 1):
    fac[i] = fac[i - 1] * i % base
    rev[i] = pow(fac[i], base -2, base)



def comb(n,r):
    hoge = (fac[n] * rev[r] * rev[n - r] ) % base
    return hoge





count = 0

an = 0 

for an in range(n+1):
    if k - an * a < 0 or (k - an * a) % b != 0:
        continue
    bn = (k -an * a) // b
    if not 0 <= bn <= n:
        continue

    count += comb(n, an) * comb(n, bn) % base
    count %= base



print(count)







    



Fixed submission:
import math


def digitSum(n):
    count = 0
    while n != 0:
        count += n % 10
        n //= 10
    return count


n =  int(input())


# 0が多くなるようにする
ans = digitSum(n)
if ans == 1:
    print(10)
else :
    print(ans)
Buggy python submission (verdict: Runtime Error):
import math

base = 998244353

n, a, b, k =  map(int, input().split())

fac = [1] * (n + 1)
rev = [1] * (n + 1)
for i in range(1, n + 1):
    fac[i] = fac[i - 1] * i % base
    rev[i] = pow(fac[i], base -2, base)



def comb(n,r):
    hoge = (fac[n] * rev[r] * rev[n - r] ) % base
    return hoge





count = 0

an = 0 

for an in range(n+1):
    if k - an * a < 0 or (k - an * a) % b != 0:
        continue
    bn = (k -an * a) // b

    count += comb(n, an) * comb(n, bn) % base
    count %= base



print(count)







    



Fixed submission:
import math

base = 998244353

n, a, b, k =  map(int, input().split())

fac = [1] * (n + 1)
rev = [1] * (n + 1)
for i in range(1, n + 1):
    fac[i] = fac[i - 1] * i % base
    rev[i] = pow(fac[i], base -2, base)



def comb(n,r):
    hoge = (fac[n] * rev[r] * rev[n - r] ) % base
    return hoge





count = 0

an = 0 

for an in range(n+1):
    if k - an * a < 0 or (k - an * a) % b != 0:
        continue
    bn = (k -an * a) // b
    if not 0 <= bn <= n:
        continue

    count += comb(n, an) * comb(n, bn) % base
    count %= base



print(count)

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

base = 998244353

n, a, b, k =  map(int, input().split())

fac = [1] * (n + 1)
rev = [1] * (n + 1)
for i in range(1, n + 1):
    fac[i] = fac[i - 1] * i % base
    rev[i] = pow(fac[i], base -2, base)



def comb(n,r):
    hoge = (fac[n] * rev[r] * rev[n - r] ) % base
    return hoge





count = 0

an = 0 

while an <= n:
    if (k - an * a) % b != 0:
        an += 1
        continue
    bn = (k -an * a) // b

    count += comb(n, an) * comb(n, bn) % base
    count %= base

    an += 1


print(count)







    



Fixed submission:
import math

base = 998244353

n, a, b, k =  map(int, input().split())

fac = [1] * (n + 1)
rev = [1] * (n + 1)
for i in range(1, n + 1):
    fac[i] = fac[i - 1] * i % base
    rev[i] = pow(fac[i], base -2, base)



def comb(n,r):
    hoge = (fac[n] * rev[r] * rev[n - r] ) % base
    return hoge





count = 0

an = 0 

for an in range(n+1):
    if k - an * a < 0 or (k - an * a) % b != 0:
        continue
    bn = (k -an * a) // b
    if not 0 <= bn <= n:
        continue

    count += comb(n, an) * comb(n, bn) % base
    count %= base



print(count)
Buggy python submission (verdict: Runtime Error):
n = int(input())
s = input()


count_list = []
for index in range(1, len(s) - 1):
    a = s[:index]
    b = s[index:]

    kind_a = set(a)
    kind_b = set(b)

    count = 0
    for c in kind_a:
        if c in kind_b:
            count+=1
    count_list.append(count)

print(max(count_list))


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


count_list = []
for index in range(1, len(s)):
    a = s[:index]
    b = s[index:]

    kind_a = set(a)
    kind_b = set(b)

    count = 0
    for c in kind_a:
        if c in kind_b:
            count+=1
    count_list.append(count)

print(max(count_list))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = input()


count_list = []
for index in range(1, len(s)+1):
    l = s[:index-1]
    r = s[index:]
    count = 0
    count += l.count("W")
    count += r.count("E")
    count_list.append(count)


print(min(count_list))


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


count_list = []

prevous_count = s[1:].count("E")
current_min = prevous_count

for index in range(len(s) - 1):
    add_man = s[index]
    leader = s[index+1]

    if add_man == "W":
        prevous_count += 1
    if leader == "E":
        prevous_count -= 1
    if current_min > prevous_count:
        current_min = prevous_count


print(current_min)