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

A_sum = [0]
for a in A:
    A_sum.append(A_sum[-1]+a)

score = []
for r in range(1,N+1):
    for l in range(0,r):
        score.append(A_sum[r]-A_sum[l])

max_num = max(score)
i = 0
while(True):
    if(2**(i+1)>max_num):
        break
    else:
        i+=1

ans = 0
for j in range(i,-1,-1):
    if len(score)<K:
        break
    count = 0
    score_a = []
    score_b = []
    for k in range(len(score)):
        if score[k] >= 2**j:
            count += 1
            score[k] -= 2**j
            score_a.append(score[k])
        score_b.append(score[k])
    if count >= K:
        ans += 2**j
        score = copy.deepcopy(score_a)
    else:
        score = copy.deepcopy(score_b)

print(ans)


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

A_sum = [0]
for a in A:
    A_sum.append(A_sum[-1]+a)

score = []
for r in range(1,N+1):
    for l in range(0,r):
        score.append(A_sum[r]-A_sum[l])

ans = 0
for i in range(40,-1,-1):
    count = 0
    score_a = []
    for j in score:
        if (j & (1<<i)):
            count += 1
            score_a.append(j)
    if count >= K:
        ans += (1<<i)
        score = copy.deepcopy(score_a)

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import copy
N,K = map(int,input().split())
A = [int(a) for a in input().split()]

A_sum = [0]
for a in A:
    A_sum.append(A_sum[-1]+a)

score = []
for r in range(1,N+1):
    for l in range(0,r):
        score.append(A_sum[r]-A_sum[l])

max_num = max(score)
i = 0
while(True):
    if(2**(i+1)>max_num):
        break
    else:
        i+=1

ans = 0
for j in range(i,-1,-1):
    count = 0
    score_a = []
    score_b = []
    for k in range(len(score)):
        if score[k] >= 2**j:
            count += 1
            score[k] -= 2**j
            score_a.append(score[k])
        score_b.append(score[k])
    if count >= K:
        ans += 2**j
        score = copy.deepcopy(score_a)
    else:
        score = copy.deepcopy(score_b)

print(ans)


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

A_sum = [0]
for a in A:
    A_sum.append(A_sum[-1]+a)

score = []
for r in range(1,N+1):
    for l in range(0,r):
        score.append(A_sum[r]-A_sum[l])

ans = 0
for i in range(40,-1,-1):
    count = 0
    score_a = []
    for j in score:
        if (j & (1<<i)):
            count += 1
            score_a.append(j)
    if count >= K:
        ans += (1<<i)
        score = copy.deepcopy(score_a)

print(ans)
Buggy python submission (verdict: Runtime Error):
H,W,K = map(int,input().split())

dp = [[0]*(W+2) for _ in range(H+1)]
dp[0][1] = 1

    

for i in range(1,H+1):
    for x in range(2**(W-1)):           
        Alloc = [0]*9
        tmp = x
        for y in range(1,8):  
            Alloc[y] = tmp%2
            tmp //= 2 
        for y in range(0,9):
            if Alloc[y] == 1 and Alloc[y+1] == 1:
                break
        else:   
            for j in range(1,9):  
                if Alloc[j-1] == 1: 
                    dp[i][j] += dp[i-1][j-1]
                elif Alloc[j] == 1:
                    dp[i][j] += dp[i-1][j+1]
                else:
                    dp[i][j] += dp[i-1][j]
                dp[i][j] %= 1000000007

print(dp[H][K])


Fixed submission:
H,W,K = map(int,input().split())

dp = [[0]*10 for _ in range(H+1)]   
dp[0][1] = 1

    

for i in range(1,H+1):
    for x in range(2**(W-1)):           
        Alloc = [0]*9
        tmp = x
        for y in range(1,8):  
            Alloc[y] = tmp%2
            tmp //= 2 
        for y in range(0,9):
            if Alloc[y] == 1 and Alloc[y+1] == 1:
                break
        else:   
            for j in range(1,9):  
                if Alloc[j-1] == 1: 
                    dp[i][j] += dp[i-1][j-1]
                elif Alloc[j] == 1:
                    dp[i][j] += dp[i-1][j+1]
                else:
                    dp[i][j] += dp[i-1][j]
                dp[i][j] %= 1000000007

print(dp[H][K])
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = [int(input()) for _ in range(N)].sorted()

B = []
for i in range(N):
    if i==0 or i==N-1:
        B.append((-1)**i)
    else:
        B.append(((-1)**i)*2)
B.sort()

print(max(abs(sum([A[i]*B[i] for i in range(N)])),abs(sum([A[i]*B[N-1-i] for i in range(N)]))))

Fixed submission:
N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))

A.sort()

B = []
for i in range(N):
    if i==0 or i==N-1:
        B.append((-1)**i)
    else:
        B.append(((-1)**i)*2)
B.sort()

print(max(abs(sum([A[i]*B[i] for i in range(N)])),abs(sum([A[i]*B[N-1-i] for i in range(N)]))))

Buggy python submission (verdict: Runtime Error):
N = int(input())
A = [int(input()) for _ in range(N)].sort()

B = []
for i in range(N):
    if i==0 or i==N-1:
        B.append((-1)**i)
    else:
        B.append(((-1)**i)*2)
B.sort()

print(max(abs(sum([A[i]*B[i] for i in range(N)])),abs(sum([A[i]*B[N-1-i] for i in range(N)]))))

Fixed submission:
N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))

A.sort()

B = []
for i in range(N):
    if i==0 or i==N-1:
        B.append((-1)**i)
    else:
        B.append(((-1)**i)*2)
B.sort()

print(max(abs(sum([A[i]*B[i] for i in range(N)])),abs(sum([A[i]*B[N-1-i] for i in range(N)]))))

Buggy python submission (verdict: Runtime Error):
N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))

A.sort()

B = []
for i in range(N):
    if i==0 or i==N-1:
        B[].append((-1)**i)
    else:
        B[i].append(((-1)**i)*2)
B.sort()

print(max(abs(sum([A[i]*B[i] for i in range(N)])),abs(sum([A[i]*B[N-1-i] for i in range(N)]))))

Fixed submission:
N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))

A.sort()

B = []
for i in range(N):
    if i==0 or i==N-1:
        B.append((-1)**i)
    else:
        B.append(((-1)**i)*2)
B.sort()

print(max(abs(sum([A[i]*B[i] for i in range(N)])),abs(sum([A[i]*B[N-1-i] for i in range(N)]))))
Buggy python submission (verdict: Runtime Error):
N = int(input())
t = [2,1]
h = [[1],[1]]
while t[1]<=N:
    if t[1]==N:
        print("Yes")
        print(t[0])
        [print("{0} {1}".format(len(h[i])," ".join([str(j) for j in h[i]]))) for i in ra
nge(len(h))]
        break
    else:
        [h[i].append(t[1]+1+i) for i in range(len(h))]
        h.append([t[1]+1+i for i in range(len(h))])
        t[1]+=t[0]
        t[0]+=1
else:
    print("No")
    exit()


Fixed submission:
N = int(input())
t = [2,1]
h = [[1],[1]]
while t[1]<=N:
    if t[1]==N:
        print("Yes")
        print(t[0])
        [print("{0} {1}".format(len(h[i])," ".join([str(j) for j in h[i]]))) for i in range(len(h))]
        break
    else:
        [h[i].append(t[1]+1+i) for i in range(len(h))]
        h.append([t[1]+1+i for i in range(len(h))])
        t[1]+=t[0]
        t[0]+=1
else:
    print("No")
    exit()
Buggy python submission (verdict: Runtime Error):
N = int(input())
XY = [list(map(int,input().split())) for _ in range(N)]

num_type = sum(XY[0])%2
for xy in XY:
    if(sum(xy)%2 != num_type):
        print(-1)
        break
else:
    print(20-num_type)
    print(' '.join(map(str,[1]*(20-num_type))))
    for xy in XY:
        ans = ""
        num = 0
        if xy[0] > 0:
            num += xy[0]
            ans += "R"*xy[0]
        elif xy[0] < 0:
            num += -xy[0]
            ans += "L"*(-xy[0])
        if xy[1] > 0:
            num += xy[1]
            ans += "U"*xy[1]
        elif xy[1] < 0:
            num += -xy[1]
            ans += "D"*(-xy[1])
        while(num<(20-num_type)):
            num += 1
            if num%2:
                ans += "R"
            else:
                ans += "L"
        print(ans)


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

num_type = sum(XY[0])%2 
for xy in XY:
    if(sum(xy)%2 != num_type):
        print(-1)
        break
else:
    m = 40-num_type
    print(m)
    D = [2**i for i in range(38,-1,-1)]
    if not(num_type):
        D.append(1)

    print(' '.join(map(str,D)))
    for xy in XY:
        p = xy
        w = ""
        for i in range(m):
            if 0<=p[0]-p[1] and 0<=p[0]+p[1]:
                w += "R"
                p[0] -= D[i]
            elif 0>p[0]-p[1] and 0<=p[0]+p[1]:
                w += "U"
                p[1] -= D[i]
            elif 0<=p[0]-p[1] and 0>p[0]+p[1]:
                w += "D"
                p[1] += D[i]
            else:
                w += "L"
                p[0] += D[i]
        print(w)
Buggy python submission (verdict: Time Limit Exceeded):
import math

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

D = {}
m = M
for i in range(2,M):
    while m % i == 0:
        D[i] = D.get(i,0)+1
        m = m//i

d = []
for v in D.values():
    d.append(v)

tmp = [0] * len(d)
for i in range(len(d)):
    tmp[i] = (math.factorial(N-1+d[i]) // (math.factorial(N-1)*math.factorial(d[i])))%(10**9 + 7)

ans = 1
for i in range(len(tmp)):
    ans = ans*tmp[i]%(10**9 +7)
print(ans)

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

m = M
f = {}
while m%2==0:
    f[2] = f.get(2,0)+1
    m = m//2

l = int(m**0.5)+1
k = 3
while m != 1:
    if k>l:
        f[m] = f.get(m,0)+1
        break
    while m%k==0:
        f[k] = f.get(k,0)+1
        m = m//k
    k+=2
ans = 1
for k in f:
    for i in range(N-1+f[k],N-1,-1):
        ans = (ans * i) 
    for i in range(f[k]):
        ans = ans // (i+1)
    ans = ans % ((10**9)+7)
print(ans)

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

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

D = {}
m = M
for i in range(2, int M):
    while m % i == 0:
        D[i] = D.get(i,0)+1
        m = m//i

d = []
for v in D.values():
    d.append(v)

tmp = [0] * len(d)
for i in range(len(d)):
    tmp[i] = (math.factorial(N-1+d[i]) // (math.factorial(N-1)*math.factorial(d[i])))%(10**9 + 7)

ans = 1
for i in range(len(tmp)):
    ans = ans*tmp[i]%(10**9 +7)
print(ans)


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

m = M
f = {}
while m%2==0:
    f[2] = f.get(2,0)+1
    m = m//2

l = int(m**0.5)+1
k = 3
while m != 1:
    if k>l:
        f[m] = f.get(m,0)+1
        break
    while m%k==0:
        f[k] = f.get(k,0)+1
        m = m//k
    k+=2
ans = 1
for k in f:
    for i in range(N-1+f[k],N-1,-1):
        ans = (ans * i) 
    for i in range(f[k]):
        ans = ans // (i+1)
    ans = ans % ((10**9)+7)
print(ans)

Buggy python submission (verdict: Runtime Error):
N,M = map(int,input().split())

D = {}
m = M
for i in range(2, int(M**0.5)+2):
    while m % i == 0:
        D[i] = D.get(i,0)+1
        m = m//i
if D == {}:
    D[M] = 1

d = []
for v in D.values():
    d.append(v)

tmp = [0] * len(d)
for i in range(len(d)):
    tmp[i] = (math.factorial(N-1+d[i]) // (math.factorial(N-1)*math.factorial(d[i])))%(10**9 + 7)

ans = 1
for i in range(len(tmp)):
    ans = ans*tmp[i]%(10**9 +7)
print(ans)


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

m = M
f = {}
while m%2==0:
    f[2] = f.get(2,0)+1
    m = m//2

l = int(m**0.5)+1
k = 3
while m != 1:
    if k>l:
        f[m] = f.get(m,0)+1
        break
    while m%k==0:
        f[k] = f.get(k,0)+1
        m = m//k
    k+=2
ans = 1
for k in f:
    for i in range(N-1+f[k],N-1,-1):
        ans = (ans * i) 
    for i in range(f[k]):
        ans = ans // (i+1)
    ans = ans % ((10**9)+7)
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
W = []
W.append(input())
for _ in range(N-1):
    W.append(input())
    if W[-1] in W[:-2]
        print("No")
        break
    if W[-1][0] != W[-2][-1]:
        print("No")
        break
else:
    print("Yes")

Fixed submission:
N = int(input())
W = []
W.append(input())
for _ in range(N-1):
    new_W = input()
    if new_W in W:
        print("No")
        break
    if new_W[0] != W[-1][-1]:
        print("No")
        break
    W.append(new_W)
else:
    print("Yes")
Buggy python submission (verdict: Runtime Error):
import fraction

N,X = map(int,input().split())
x = [int(i) for i in input().split()]
ans = abs(X-x[0])
now = X
for i in x:
    if abs(now - i) % ans:
        ans = fraction.gcd(ans, abs(now-i))
    now = i

print(ans)

Fixed submission:
def gcd(a,b):
    while b:
        a, b = b, a % b
    return a
N,X = map(int,input().split())
x = [int(i) for i in input().split()]
ans = abs(X-x[0])
now = X
for i in x:
    if abs(now - i) % ans:
        ans = gcd(ans, abs(now-i))
    now = i

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

B = [0]*M
B[0] = 1
tmp = 0
ans = 0



for a in A:
        tmp = (tmp+a)%M
        ans += B[tmp]
        B[tmp] += 1

print(ans)

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

B = {}
B[0] = 1
tmp = 0
ans = 0

for a in A:
        tmp = (tmp+a)%M
        ans += B.get(tmp,0)
        B[tmp] = B.get(tmp,0)+1

print(ans)

Buggy python submission (verdict: Runtime Error):
,M = map(int,input().split())
A = map(int,input().split())

B = [0]*M
B[0] = 1
tmp = 0
ans = 0



for a in A:
        tmp = (tmp+a)%M
        ans += B[tmp]
        B[tmp] += 1

print(ans)

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

B = {}
B[0] = 1
tmp = 0
ans = 0

for a in A:
        tmp = (tmp+a)%M
        ans += B.get(tmp,0)
        B[tmp] = B.get(tmp,0)+1

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

D,G = map(int,input().split())
PC = [0] + [[int(i) for i in input().split()] for _ in range(D)]

ans = 1e9
for i in range(2**D - 1):
    inSolve = -1
    score_tmp = 0
    solved = 0
    for j in range(D):
        if (i>>j)%2 == 1:
            score_tmp += (j+1)*100*PC[j][0]+PC[j][1]
            solved += PC[j][0]
        else:
            inSolve = max(j,inSolve)
    if score_tmp < G and inSolve != -1:
        if math.ceil((G-score_tmp)/((inSolve+1)*100)) <= PC[inSolve][0]:
            ans = min(ans,solved + math.ceil((G-score_tmp)/((inSolve+1)*100)))
    elif score_tmp >= G:
        ans = min(ans,solved)
print(ans)

Fixed submission:
import math
D,G = map(int,input().split())
p=[]
c=[]
for i in range(D):
    p_tmp,c_tmp = map(int,input().split())
    p.append(p_tmp)
    c.append(c_tmp)

ans = sum(p)
for i in range(2**D):
    score_tmp = 0
    ans_tmp = 0
    for j in range(D):
        if (i>>j)%2 == 1:
            score_tmp += p[j]*(j+1)*100+c[j]
            ans_tmp += p[j]

    if ans_tmp >= ans:
        continue
    elif score_tmp >= G:
        ans = ans_tmp
        continue
    else:
        for j in range(D):
            if (i>>(D-1-j))%2 == 1:
                continue
            elif score_tmp + p[D-1-j]*(D-j)*100 < G:
                break
            else:
                ans_tmp += math.ceil((G - score_tmp)/((D-j)*100))
                ans = min(ans,ans_tmp)
                break

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import math

D,G = map(int,input().split())
p = []
c = []
for i in range(D):
        p_tmp,c_tmp = map(int,input().split())
        p.append(p_tmp)
        c.append(c_tmp)

ans = sum(p)
for i in range(D):
        for j in range(p[i]):
                for k in range(2**D-1):
                        score = (i+1)*100*j
                        ans_tmp = j
                        for l in range(D):
                                if l == i:
                                        continue
                                elif (k>>l)%2 == 1:
                                        score += (l+1)*100*p[l]+c[l]
                                        ans_tmp += p[l]
                        if score >= G:
                                ans = min(ans,ans_tmp)

print(ans)

Fixed submission:
import math
D,G = map(int,input().split())
p=[]
c=[]
for i in range(D):
    p_tmp,c_tmp = map(int,input().split())
    p.append(p_tmp)
    c.append(c_tmp)

ans = sum(p)
for i in range(2**D):
    score_tmp = 0
    ans_tmp = 0
    for j in range(D):
        if (i>>j)%2 == 1:
            score_tmp += p[j]*(j+1)*100+c[j]
            ans_tmp += p[j]

    if ans_tmp >= ans:
        continue
    elif score_tmp >= G:
        ans = ans_tmp
        continue
    else:
        for j in range(D):
            if (i>>(D-1-j))%2 == 1:
                continue
            elif score_tmp + p[D-1-j]*(D-j)*100 < G:
                break
            else:
                ans_tmp += math.ceil((G - score_tmp)/((D-j)*100))
                ans = min(ans,ans_tmp)
                break

print(ans)
Buggy python submission (verdict: Runtime Error):
S = input()

A_left=[0]
C_left=[0]
Q_left=[0]

for (i,s) in enumerate(S):
    if s == "A":
        A_left.append(A_left[i]+1)
        C_left.append(C_left[i])
        Q_left.append(Q_left[i])
    elif s == "C":
        A_left.append(A_left[i])
        C_left.append(C_left[i]+1)
        Q_left.append(Q_left[i])
    elif s == "?":
        A_left.append(A_left[i])
        C_left.append(C_left[i])
        Q_left.append(Q_left[i]+1)
    else:
        A_left.append(A_left[i])
        C_left.append(C_left[i])
        Q_left.append(Q_left[i])

A_right = []
C_right = []
Q_right = []
for i in range(len(S)):
    A_right.append(A_left[-1] - A_left[i+1])
    C_right.append(C_left[-1] - C_left[i+1])
    Q_right.append(Q_left[-1] - Q_left[i+1])

ans = 0
for (i,s) in enumerate(S):
    if s == "B":
        ans = (ans + A_left[i] * C_right[i] * pow(3,Q_left[-1],10**9+7)) % (10**9+7)
        ans = (ans + (Q_left[i] * C_right[i] + A_left[i] * Q_right[i]) * pow(3,(Q_left[-1]-1),10**9+7)) % (10**9+7)
        ans = (ans + (Q_left[i] * Q_right[i]) * pow(3,(Q_left[-1]-2),10**9+7)) % (10**9+7)
    elif s == "?":
        ans = (ans + A_left[i] * C_right[i] * pow(3,(Q_left[-1]-1),10**9+7)) % (10**9+7)
        ans = (ans + (Q_left[i] * C_right[i] + A_left[i] * Q_right[i]) * pow(3,(Q_left[-1]-2),10**9+7)) % (10**9+7)
        ans = (ans + (Q_left[i] * Q_right[i]) * pow(3,(Q_left[-1]-3),10**9+7)) % (10**9+7)

print(ans)


Fixed submission:
S = input()

A_left=[0]
C_left=[0]
Q_left=[0]

for (i,s) in enumerate(S):
    if s == "A":
        A_left.append(A_left[i]+1)
        C_left.append(C_left[i])
        Q_left.append(Q_left[i])
    elif s == "C":
        A_left.append(A_left[i])
        C_left.append(C_left[i]+1)
        Q_left.append(Q_left[i])
    elif s == "?":
        A_left.append(A_left[i])
        C_left.append(C_left[i])
        Q_left.append(Q_left[i]+1)
    else:
        A_left.append(A_left[i])
        C_left.append(C_left[i])
        Q_left.append(Q_left[i])

A_right = []
C_right = []
Q_right = []
for i in range(len(S)):
    A_right.append(A_left[-1] - A_left[i+1])
    C_right.append(C_left[-1] - C_left[i+1])
    Q_right.append(Q_left[-1] - Q_left[i+1])

ans = 0
for (i,s) in enumerate(S):
    if s == "B":
        ans = (ans + A_left[i] * C_right[i] * pow(3,Q_left[-1],10**9+7)) % (10**9+7)
        if Q_left[-1]>=1:
            ans = (ans + (Q_left[i] * C_right[i] + A_left[i] * Q_right[i]) * pow(3,(Q_left[-1]-1),10**9+7)) % (10**9+7)
        if Q_left[-1]>=2:
            ans = (ans + (Q_left[i] * Q_right[i]) * pow(3,(Q_left[-1]-2),10**9+7)) % (10**9+7)
    elif s == "?":
        if Q_left[-1]>=1:
            ans = (ans + A_left[i] * C_right[i] * pow(3,(Q_left[-1]-1),10**9+7)) % (10**9+7)
        if Q_left[-1]>=2:
            ans = (ans + (Q_left[i] * C_right[i] + A_left[i] * Q_right[i]) * pow(3,(Q_left[-1]-2),10**9+7)) % (10**9+7)
        if Q_left[-1]>=3:
            ans = (ans + (Q_left[i] * Q_right[i]) * pow(3,(Q_left[-1]-3),10**9+7)) % (10**9+7)

print(ans)
Buggy python submission (verdict: Runtime Error):
N,M = map(int,input().split())
requests = []
for _ in range(M):
        a,b = map(int,input().split())
        requests.append([a,b])

ans = 1
requests = sorted(requests, key=lambda x:(x[1],x[0]))
b = min(requests, key=lambda x:x[1])[1]
for i in range(M):
        if requests[i][0] < b:
                continue
        else:
                ans += 1
                b = min(requests[i:], key=lambda x:x[1])[1]

print(ans)

Fixed submission:
A = list(map(int,input().split()))
B = [abs(A[0]-A[1]),abs(A[0]-A[2]),abs(A[1]-A[2])]
B.sort()
print(B[0]+B[1])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int,input().split()))

ans = sum(A)

imin = min(A)-N
imax = max(A)+N

def calcAns(b):
        global A
        return sum([abs(A[i]-(b+i+1)) for i in range(N)])

while True:
        if imin == imax:
                break
        else:
                imid = imin + (imax - imin)//2
                if calcAns(imid+1)<calcAns(imid):
                        imin = imid+1
                elif calcAns(imid-1)<calcAns(imid):
                        imax = imid-1
                else:
                        imin = imid
                        imax = imid

print(calcAns(imin))

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

ans = sum(A)

imin = min(A)-N
imax = max(A)+N

def calcAns(b):
        global A
        return sum([abs(A[i]-(b+i+1)) for i in range(N)])

while True:
        if imin == imax:
                break
        else:
                imid = imin + (imax - imin)//2
                tmp = calcAns(imid)
                if calcAns(imid+1)<tmp:
                        imin = imid+1
                elif calcAns(imid-1)<tmp:
                        imax = imid-1
                else:
                        imin = imid
                        imax = imid

print(calcAns(imin))

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

ans = sum(A)

for b in range(min(A)-N,max(A)+N):
        tmp = sum([abs(A[i]-(b+i+1)) for i in range(N)])
        if ans > tmp:
                ans = tmp

print(ans)

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

ans = sum(A)

imin = min(A)-N
imax = max(A)+N

def calcAns(b):
        global A
        return sum([abs(A[i]-(b+i+1)) for i in range(N)])

while True:
        if imin == imax:
                break
        else:
                imid = imin + (imax - imin)//2
                tmp = calcAns(imid)
                if calcAns(imid+1)<tmp:
                        imin = imid+1
                elif calcAns(imid-1)<tmp:
                        imax = imid-1
                else:
                        imin = imid
                        imax = imid

print(calcAns(imin))
Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int,input().split())
A = [int(i) for i in input().split()]

ans = 0

minA = min(A)

for i in range(len(A)):
        if A[i] == minA:
                A[i] = 0
        else:
                A[i] = 1

while 1 in A:
        if len(A) <= K:
                ans += 1
                break
        if A[0] == 0:
                if A[1] == 0:
                        A = A[1:]
                elif 0 in A[1:1+K]:
                        A[K] = 0
                        A = A[K:]
                        ans += 1
                else:
                        A[K-1] = 0
                        A = A[K-1:]
                        ans += 1
        else:
                A = A[K-1:]
                ans += 1
print(ans)

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

print((N-1)//(K-1)+((N-1)%(K-1)!=0))

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

ans = 0

minA = min(A)

for i in range(len(A)):
        if A[i] == minA:
                A[i] = 0
        else:
                A[i] = 1

while sum(A) != 0:
        if len(A) <= K:
                ans += 1
                break
        if A[0] == 0:
                if A[1] == 0:
                        A = A[1:]
                elif 0 in A[1:1+K]:
                        A[K] = 0
                        A = A[K:]
                        ans += 1
                else:
                        A[K-1] = 0
                        A = A[K-1:]
                        ans += 1
        else:
                A = A[K-1:]
                ans += 1
print(ans)

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

print((N-1)//(K-1)+((N-1)%(K-1)!=0))