Problem:


Score : 300 points

Problem Statement

Snuke has an integer sequence A of length N.

He will freely choose an integer b.
Here, he will get sad if A_i and b+i are far from each other.
More specifically, the sadness of Snuke is calculated as follows:

abs(A_1 - (b+1)) + abs(A_2 - (b+2)) + ... + abs(A_N - (b+N))

Here, abs(x) is a function that returns the absolute value of x.

Find the minimum possible sadness of Snuke.

Constraints

1 \leq N \leq 2 \times 10^5

1 \leq A_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the minimum possible sadness of Snuke.

Sample Input 1

5
2 2 3 5 5

Sample Output 1

2

If we choose b=0, the sadness of Snuke would be abs(2-(0+1))+abs(2-(0+2))+abs(3-(0+3))+abs(5-(0+4))+abs(5-(0+5))=2.
Any choice of b does not make the sadness of Snuke less than 2, so the answer is 2.

Sample Input 2

9
1 2 3 4 5 6 7 8 9

Sample Output 2

0

Sample Input 3

6
6 5 4 3 2 1

Sample Output 3

18

Sample Input 4

7
1 1 1 1 2 3 4

Sample Output 4

6



Sample input:
5
2 2 3 5 5


Sample output:
2

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left as bl
INF = 10 ** 20

def get_score(section):
  section_min = section[0]
  section_max = section[-1]
  section_sum = section_max - section_min
  section_len = len(section)
  cut = bl(section, section_min + section_sum // 2)
  diff = INF
  ans = (None, None)
  for i in range(cut - 2, cut + 3):
    if 0 <= i <= section_len - 1:
      div = section[i]
      a, b = div - section_min, section_max - div
      if a == 0 or b == 0:
        continue
      score = abs(b - a)
      if score < diff:
        ans = (a, b)
        diff = score
  return ans

def main():
  n = int(input())
  alst = list(map(int, input().split()))
  cums = [0]
  acc = 0
  for a in alst:
    acc += a
    cums.append(acc)
  
  ans = INF
  for i in range(2, n - 1):
    left = cums[:i]
    right = cums[i - 1:]
    p, q = get_score(left)
    r, s = get_score(right)
    if None in (p, q, r, s):
      continue
    tmp = max(p, q, r, s) - min(p, q, r, s)
    if tmp < ans:
      ans = tmp
  
  print(ans)

main()

Submission status: Wrong Answer

Solution code:
n = input()
l = list(map(int,input().split()))

ans = 0
result = 1000

for j in range(100):
	b = j - 50
	for i in range(len(l)):
		ans += abs(l[i]-(b+(i+1)))
	if result > ans:
		result = ans
	ans = 0

print(result)

Submission status: Wrong Answer

Solution code:
import numpy as np

N = int(input())

B = np.array([0]*N)

l = input().split()

for i in range(N):
    B[i] = int(l[i]) - (i+1)
    
B = np.sort(B)
b_mid = B[N//2]
dif = B - b_mid

print(np.sum(dif))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))

for i in range(n):
  a[i] -= (i+1)

m1 = a[n//2]
m2 = a[n//2-1]
ans1 = sum([abs(ele-m1) for ele in a])
ans2 = sum([abs(ele-m2) for ele in a])
print(min(ans1, ans2))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))

for i in range(n):
  a[i] -= i

m1 = a[n//2]
m2 = a[n//2-1]
ans1 = sum([abs(ele-m1) for ele in a])
ans2 = sum([abs(ele-m2) for ele in a])
print(min(ans1, ans2))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))

for i in range(n):
  a[i] -= i

m = a[n//2]
ans = sum([abs(ele-m) for ele in a])
print(ans)

Submission status: Wrong Answer

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

for i in range(N):
    A[i] = A[i]-i
A.sort()

print(A)

# 中央値を求める
mi = len(A)//2
print(mi)

print(sum(A[mi:]) - sum(A[:mi-1]))

Submission status: Wrong Answer

Solution code:
from statistics import mean, median
a = int(input())
b = list(map(int,input().split()))
 
for i in range(a):
	b[i] -= i + 1
 
b.sort()
su = 0
median = median(b)

for i in range(a):
	su += abs(b[i] - median)

print(su)

Submission status: Wrong Answer

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

for i in range(N):
    A[i] = A[i]-i
A.sort()

minA = min(A)

for i in range(N):
    A[i] -= minA

# 中央値を求める
mi = (len(A)-1)//2

print(sum(A[mi+1:]) - sum(A[:mi+1]))

Submission status: Wrong Answer

Solution code:
from statistics import mean, median
a = int(input())
b = list(map(int,input().split()))
 
for i in range(a):
	b[i] -= i + 1
 
b.sort()
su = 0
if a % 2 == 0:
    median1 = a/2
    median2 = a/2 + 1
    #pythonでは要素を0から数えるため-1します。
    #また除算演算子は結果が整数でも小数点を返すので(6 / 3 = 3.0)int関数で整数にします
    median1 = int(median1) - 1
    median2 = int(median2) - 1
    median = (b[median1] + b[median2]) / 2
    for i in range(a):
    	su += abs(b[i] - median)
    # 奇数の場合
else:
    median = (a + 1) / 2
    #pythonでは要素を0から数えるため-1します。
    median = int(median) - 1
    median = b[median]
    for i in range(a):
    	su += abs(b[i] - median)

print(su)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int ,input().split()))
for i in range(N):
    a[i] = a[i] - i
s = sum(a)
mean = s // N
for i in range(N):
    a[i] -= mean
check1 = 0
for i in range(N):
    check1 += abs(a[i]-1)
check2 = 0
for i in range(N):
    check2 += abs(a[i])
check3 = 0
for i in range(N):
    check3 += abs(a[i]+1)
check4 = 0
for i in range(N):
    check4 += abs(a[i]+2)
check5 = 0
for i in range(N):
    check5 += abs(a[i]-2)
print(min(check1,check2,check3,check4, check5))

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int ,input().split()))
for i in range(N):
    a[i] = a[i] - i
s = sum(a)
mean = s // N
for i in range(N):
    a[i] -= mean
check1 = 0
for i in range(N):
    check1 += abs(a[i]-1)
check2 = 0
for i in range(N):
    check2 += abs(a[i])
check3 = 0
for i in range(N):
    check3 += abs(a[i]+1)
print(min(check1,check2,check3))

Submission status: Wrong Answer

Solution code:
import statistics

def f(a, n):
    a2 = [ai - (i+1) for (i,ai) in enumerate(a)]
    b = statistics.median(a2)
    sadness = sum(abs(ai - b) for ai in a2)
        
    return sadness
    
n = int(input())
a = [int(i) for i in input().split()]
print(f(a, n))

Submission status: Wrong Answer

Solution code:
import statistics

def f(a, n):
    a = [a - i for (i,a) in enumerate(a, 1)]
    bs = [statistics.median(a), sum(a)//n]
    res = []
    for b in bs:
        sadness = sum(abs(ai - b) for ai in a)
        res.append(sadness)
        
    return min(res)
    
n = int(input())
a = [int(i) for i in input().split()]
print(f(a, n))

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int ,input().split()))
for i in range(N):
    a[i] = a[i] - i
s = sum(a)
mean = s // N
for i in range(N):
    a[i] -= mean
check1 = abs(sum(a)-2*N)
check2 = abs(sum(a)-N)
check3 = abs(sum(a))
check4 = abs(sum(a)+N)
check5 = abs(sum(a)+2*N)
print(min(check1,check2,check3,check4,check5))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a_ = []

for i in range(n):
    a_.append(a[i] - i)
b = round((sum(a_))/n)

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

ansp = 0
for i in range(n):
    ansp += abs(a[i] - (b + i+1))

ansm = 0
for i in range(n):
    ansm += abs(a[i] - (b + i-1))

ans = min(ans0, ansp, ansm)

if ans == ans0:
    print(ans)
else:
    if ans == ansp:
        p = 1
        while 1:
            ansp = 0
            for i in range(n):
                ansp += abs(a[i] - (b + i+p))
            if ansp > ans:
                break
            ans = ansp
            p += 1
    if ans == ansp:
        m = 1
        while 1:
            ansp = 0
            for i in range(n):
                ansm += abs(a[i] - (b + i-m))
            if ansm > ans:
                break
            ans = ansm
            p -= 1
    print(min(ansp, ansm))

Submission status: Wrong Answer

Solution code:
import numpy as np
 
n = int(input())
a = list(map(int, input().split(" ")))

b = [i for i in range(1, n+1, 1)]

a = np.array(a)
b = np.array(b)

a -= b

ans = sum(abs(a))
flag = 0
while(flag < 100):
    a1 = a[a < 0]
    a2 = a[a > 0]

    if(len(a1) > len(a2)):
        if(len(a1) == 0): tmp = 1
        elif(flag == 0): tmp = -int(np.average(a1))
        else: tmp = -min(a1)
        a += tmp
    else:
        if(len(a2) == 0): tmp = 1
        elif(flag == 0): tmp = int(np.average(a2))
        else: tmp = max(a2)
        a -= tmp
    if(ans <= sum(abs(a))): flag += 1
    else: ans = sum(abs(a))

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
 
n = int(input())
a = list(map(int, input().split(" ")))

b = [i for i in range(1, n+1, 1)]

a = np.array(a)
b = np.array(b)

a -= b

ans = sum(abs(a))
flag = 0
while(flag < 3):
    a1 = a[a < 0]
    a2 = a[a > 0]

    if(len(a1) > len(a2)):
        if(len(a1) == 0): tmp = 1
        elif(flag == 0): tmp = -int(np.average(a1))
        else: tmp = -min(a1)
        a += tmp
    else:
        if(len(a2) == 0): tmp = 1
        elif(flag == 0): tmp = int(np.average(a2))
        else: tmp = max(a2)
        a -= tmp
    if(ans <= sum(abs(a))): flag += 1
    else: ans = sum(abs(a))

print(ans)

Submission status: Wrong Answer

Solution code:
def calc(A,b):
    dif = 0
    for i,j in enumerate(A):
        dif+=abs(j-(b+i+1))
    return dif
 
N = int(input())
A = [int(i) for i in input().split()]
s = 0
for i in A:s+=i
m = s//N-N//2-1
a = calc(A,m)
b = calc(A,m+1)
c = calc(A,m-1)
d = calc(A,m+2)
e = calc(A,m-2)
print(min(a,b,c,d,e))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))

for i in range(n): a[i] -= i + 1
m = min(a)
a = list(map(lambda x: x - m, a))
b = round(sum(a) / n)
ans = 0
for i in range(n): ans += abs(a[i] - b)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a_ = []

for i in range(n):
    a_.append(a[i] - i)
b = round((sum(a_))/n)

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

ansp = 0
for i in range(n):
    ansp += abs(a[i] - (b + i+1))

ansm = 0
for i in range(n):
    ansm += abs(a[i] - (b + i-1))

print(min(ans0, ansp, ansm))

Submission status: Wrong Answer

Solution code:
a = int(input())
b = list(map(int,input().split()))
 
for i in range(a):
	b[i] -= i + 1
 
b.sort()
s = 0
co = 0
ss = 0
coco = 0
cococo = 0
summ = 0
su = 0
bb = 1
for i in range(a):
	if b[i] < 0:
		co += 1
	elif b[i] > 0:
		coco += 1
	else:
		cococo += 1
	su += abs(b[i])


if co > coco:	
	while su != 0:
		bb = 0
		for i in range(a):
			b[i] += 1
			bb += abs(b[i])
		if bb >= su:
			print(bb)
			break
		su = bb
		bb = 0


elif coco >= co:
	while su != 0:
		for i in range(a):
			b[i] -= 1
			bb += abs(b[i])
		if bb >= su:
			print(su)
			break
		su = bb
		bb = 0

if su == 0:
	print(0)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))

for i in range(n): a[i] -= i + 1
m = min(a)
a = list(map(lambda x: x - m, a))
s = sum(a)
b = (s // n) if (round(s / n) < n / 2) else (s // n + 1)
ans = 0
for i in range(n): ans += abs(a[i] - b)
print(ans)

Submission status: Wrong Answer

Solution code:
def Asum(A,b):
    sumA = 0
    for i in range(len(A)):
        sumA += abs(A[i] - i - b - 1)
    return sumA

def aveA(A):
    return sum(A)/len(A)


N = int(input())
ip = input().split()

A = []
for i in ip:
    A.append(int(i))

for i in range(N):
    A[i] -= i + 1

b1 = aveA(A)
b2 = b1 + 1
b3 = b1 - 1

ans = min(Asum(A,b1),Asum(A,b2),Asum(A,b3))

print(ans)
#buf = Asum(A,max(A))
#for i in range(max(A)-1,min(A)-N,-1):
#    if buf > Asum(A,i):
#        buf = Asum(A,i)
#    else:
#        break

print(Asum(A,i-1))

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
a = np.array(list(map(int, input().split())))
check = np.arange(1, n+1)
c = list(a - check)
b = c[int(n/2)]
count = 0
for i in range(1, n+1):
    count += abs(a[i-1] - i - b)
print(count)

Submission status: Wrong Answer

Solution code:
import statistics

def f(a, n):
    b = statistics.median(a)
    s = ((b+i) for i in range(1, n+1))
    sadness = sum(abs(ai - xi) for (ai, xi) in zip(a, s))
    return sadness
    
n = int(input())
a = [int(i) for i in input().split()]
print(f(a, n))

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int ,input().split()))
s = sum(a)
mean = s // N
cnt = 10**100
tmp = 0
j = mean - 100
while 1:
    tmp = 0
    for i in range(N):
        tmp += abs(a[i]-i-j-1)
    if cnt < tmp:
        break
    cnt = min(tmp,cnt)
    j += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
from bisect import bisect_left

for i in range(N):
    A[i] = A[i]-i
A.sort()

S = [0]*(N+1)
for i in range(N):
    S[i+1] = S[i]+A[i]

sumA = sum(A)
maxA,minA = max(A),min(A)

Ans = 10**9
for i in range(1000):
    l = bisect_left(A,minA)
    low  = abs(minA*l - S[l]) + abs(S[N]-S[l] - minA*(N-l))
    h = bisect_left(A,maxA)
    high  = abs(maxA*h - S[h]) + abs(S[N]-S[h] - maxA*(N-h))
    if low==high:
        minA += 1
    elif low < high:
        maxA = (maxA+minA)//2
    else:
        minA = (maxA+minA)//2
    #print(Ans,low,high,minA,maxA)
    Ans = min(Ans,low,high)

print(Ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
from bisect import bisect_left

for i in range(N):
    A[i] = A[i]-i
A.sort()

S = [0]*(N+1)
for i in range(N):
    S[i+1] = S[i]+A[i]

sumA = sum(A)
maxA,minA = max(A),min(A)

Ans = 10**9
for i in range(300):
    l = bisect_left(A,minA)
    low  = abs(minA*l - S[l]) + abs(S[N]-S[l] - minA*(N-l))
    h = bisect_left(A,maxA)
    high  = abs(maxA*h - S[h]) + abs(S[N]-S[h] - maxA*(N-h))
    if low==high:
        minA += 1
    elif low < high:
        maxA = (maxA+minA)//2
    else:
        minA = (maxA+minA)//2
    #print(Ans,low,high,minA,maxA)
    Ans = min(Ans,low,high)

print(Ans)

Submission status: Wrong Answer

Solution code:
import functools
N = int(input())
A = [int(x) for x in input().split()]
ave = functools.reduce(lambda x, y: x + y, [A[i] - i - 1 for i in range(N)]) // N
B0 = functools.reduce(lambda x, y: x + y, [abs(A[i] - ave - i) for i in range(N)])
B1 = functools.reduce(lambda x, y: x + y, [abs(A[i] - ave - i - 1) for i in range(N)])
B2 = functools.reduce(lambda x, y: x + y, [abs(A[i] - ave - i - 2) for i in range(N)])
print(min(B0, B1, B2))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A_dash = []
for i, A_i in enumerate(A):
    A_dash.append(A_i-(i+1))

A_set = set(A_dash)
grav = sum(A_dash)//len(A_dash)
left, mid, right = 0, 0, 0
for i, A_i in enumerate(A_dash):
    left += abs(A_i - (grav-1))
    mid += abs(A_i - (grav))
    right += abs(A_i - (grav+1))

print(min(left, mid, right))

Submission status: Wrong Answer

Solution code:
a = int(input())
b = list(map(int,input().split()))
 
for i in range(a):
	b[i] -= i + 1
 
b.sort()
s = 0
co = 0
ss = 0
coco = 0
cococo = 0
summ = 0
su = 0
bb = 0
for i in range(a):
	if b[i] < 0:
		co += 1
	elif b[i] > 0:
		coco += 1
	else:
		cococo += 1
	su += abs(b[i])


if co > coco:	
	while su <= bb:
		for i in range(a):
			b[i] += 1
			if b[i] < 0:
				co += 1
			elif b[i] > 0:
				coco += 1
			else:
				cococo += 1
			bb += abs(b[i])
		if bb >= su:
			print(su)
			break
		su = bb
		bb = 0

		co = 0
		coco = 0
		cococo = 0

elif coco >= co:
	while su >= bb:
		for i in range(a):
			b[i] -= 1
			if b[i] < 0:
				co += 1
			elif b[i] > 0:
				coco += 1
			else:
				cococo += 1
			bb += abs(b[i])
		if bb <= su:
			print(su)
			break
		su = bb
		bb = 0
		co = 0
		coco = 0
		cococo = 0

Submission status: Wrong Answer

Solution code:
import numpy as np
import collections
n = int(input())
a = np.array(list(map(int, input().split())))
check = np.arange(1, n+1)
c = list(a - check)
b = collections.Counter(c)
b = b.most_common(min(n, 10**3))[0]
count = 0
for i in range(1, n+1):
    count += abs(a[i-1] - i - b)
print(min(count))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A_dash = []
for i, A_i in enumerate(A):
    A_dash.append(A_i-(i+1))

A_set = set(A_dash)
grav = sum(A_dash)//len(A_dash)
left, right = 0, 0
for i, A_i in enumerate(A_dash):
    left += abs(A_i - (grav))
    right += abs(A_i - (grav + 1))
print(min(left, right))

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
As=list(map(int,input().split()))

b=-(n+1)/2+sum(As)/n
math.ceil(b)

b0,b1=math.ceil(b),math.floor(b)
res=min(sum(abs(As[i]-(b+i+1)) for i in range(n)) for b in (b0,b1))
print(res)

Submission status: Wrong Answer

Solution code:
import functools
N = int(input())
A = [int(x) for x in input().split()]
sum = functools.reduce(lambda x, y: x + y, sorted(A))
ave = sum // N - 1
for i,a in enumerate(A):
  A[i] = a - i - 1
B0 = functools.reduce(lambda x, y: x + y, [abs(a - ave) for a in A])
B1 = functools.reduce(lambda x, y: x + y, [abs(a - ave - 1) for a in A])
B2 = functools.reduce(lambda x, y: x + y, [abs(a - ave + 1) for a in A])
print(min(B0, B1, B2))

Submission status: Wrong Answer

Solution code:
_ = input()
aa = list(map(int, input().split()))

normalized = [aa[i-1] - i for i in range(1, len(aa) + 1)]

total0 = sum(normalized)
avg = total0 // len(normalized)

print(sum([abs(a - avg) for a in normalized]))

Submission status: Wrong Answer

Solution code:
N = int(input())
sum = 0
a = list(map(int, input().split()))
for i in range(N):
    a[i] -= (i + 1)
    sum += a[i] / N
mean = int(sum)
sad1 = 0
sad2 = 0
for i in range(N):
    sad1 += abs(a[i] - mean)
    sad2 += abs(a[i] - mean + 1)
print(min([sad1, sad2]))

Submission status: Wrong Answer

Solution code:
import functools
N = int(input())
A = [int(x) for x in input().split()]
sum = functools.reduce(lambda x, y: x + y, sorted(A))
ave = sum // N
B0 = functools.reduce(lambda x, y: x + y, [abs(a - ave) for a in A])
B1 = functools.reduce(lambda x, y: x + y, [abs(a - ave - 1) for a in A])
B2 = functools.reduce(lambda x, y: x + y, [abs(a - ave + 1) for a in A])
print(min(B0, B1, B2))

Submission status: Wrong Answer

Solution code:
N = int(input())
sum = 0
a = list(map(int, input().split()))
for i in range(N):
    a[i] -= (i + 1)
    sum += a[i]
mean = sum // N
sad1 = 0
sad2 = 0
for i in range(N):
    sad1 += abs(a[i] - mean)
    sad2 += abs(a[i] - mean + 1)
print(min([sad1, sad2]))

Submission status: Wrong Answer

Solution code:
N = int(input())
sum = 0
a = list(map(int, input().split()))
for i in range(N):
    a[i] -= (i + 1)
    sum += a[i]
mean = sum // N
sad1 = 0
sad2 = 0
sad3 = 0
for i in range(N):
    sad1 += abs(a[i] - mean)
    sad2 += abs(a[i] - mean + 1)
    sad3 += abs(a[i] - mean - 1)
print(min([sad1, sad2, sad3]))

Submission status: Wrong Answer

Solution code:
N = int(input())
sum = 0
a = list(map(int, input().split()))
for i in range(N):
    a[i] -= (i + 1)
    sum += a[i]
mean = sum // N
sad1 = 0
sad2 = 0
sad3 = 0
for i in range(N):
    sad1 += (a[i] - mean)
    sad2 += (a[i] - mean + 1)
    sad3 += (a[i] - mean - 1)
print(min([sad1, sad2, sad3]))

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[int(x) for x in input().split()]
P=A[:]
s=0
for i in range(N):
    A[i] = A[i]-(i+1)
    s+=A[i]
m=s//N
S=0
for i in range(N):
    S += abs(P[i]-(i+1)-m)
print(S)

Submission status: Wrong Answer

Solution code:

def f(a, n):
    b = sum(a) // n
    b2 = (1+n) // 2 
    
    res = []
    for x in [b, b2, b-b2, b2-b]:
        s = (x+i for i in range(1, n+1))
        sadness = sum(abs(ai - xi) for (ai, xi) in zip(a, s))
        res.append(sadness)
        
    return min(res)
    
n = int(input())
a = [int(i) for i in input().split()]
print(f(a, n))

Submission status: Wrong Answer

Solution code:
import numpy as np
 
n = int(input())
a = list(map(int, input().split(" ")))

b = [i for i in range(1, n+1, 1)]

a = np.array(a)
b = np.array(b)

a -= b

ans = sum(abs(a))
while(True):
    a1 = (a < 0)
    a2 = (a > 0)

    a1 = a1 * a
    a2 = a2 * a
    if(abs(sum(a1)) > abs(sum(a2))):
        tmp = (abs(sum(a1)) - abs(sum(a2))) // n
        if(tmp == 0): tmp += 1
        a += tmp
    else:
        tmp = (abs(sum(a2)) - abs(sum(a1))) // n
        if(tmp == 0): tmp += 1
        a -= tmp
    if(ans <= sum(abs(a))): break
    else: ans = sum(abs(a))

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
sum = 0
for i in range(n): sum += a[i] - (i + 1)
b = sum // n
ans = 0
for i in range(n): ans += abs(a[i] - (b + i + 1))
print(ans)

Submission status: Wrong Answer

Solution code:
import functools
N = int(input())
A = [int(x) for x in input().split()]
sum = functools.reduce(lambda x, y: x + y, sorted(A))
ave = sum // N - 1
B0 = functools.reduce(lambda x, y: x + y, [abs(a - ave) for a in A])
B1 = functools.reduce(lambda x, y: x + y, [abs(a - ave - 1) for a in A])
B2 = functools.reduce(lambda x, y: x + y, [abs(a - ave + 1) for a in A])
print(min(B0, B1, B2))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a_ = []

for i in range(n):
    a_.append(a[i] - (i+1))
if sum(a_) >= 0:
    b = round((sum(a_))/n)+1
else:
    b = -round((-sum(a_))/n)
    

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

Submission status: Wrong Answer

Solution code:

def f(a, n):
    b = sum(a) // n
    b2 = (1+n) // 2 
    
    s = (b-b2+i for i in range(1, n+1))
    sadness = sum(abs(ai - xi) for (ai, xi) in zip(a, s))
    
    return sadness
    
n = int(input())
a = [int(i) for i in input().split()]
print(f(a, n))

Submission status: Wrong Answer

Solution code:
N = int(input())
a = [0]*N
sum = 0
a = list(map(int, input().split()))
for i in range(N):
    a[i] -= (i + 1)
    sum += a[i]
mean = sum // N
sad1 = 0
sad2 = 0
for i in range(N):
    sad1 += (a[i] - mean)
    sad2 += (a[i] - mean + 1)
print(min([sad1, sad2]))

Submission status: Wrong Answer

Solution code:
import functools
N = int(input())
A = [int(x) for x in input().split()]
for i,a in enumerate(A):
  A[i] = a - i - 1
ave = 0
sum = 0
for a in A:
  sum += a
  if abs(sum) >= N:
    add = sum // N
    ave += add
    sum -= N * add
B0 = functools.reduce(lambda x, y: x + y, [abs(a - ave) for a in A])
B1 = functools.reduce(lambda x, y: x + y, [abs(a - ave - 1) for a in A])
B2 = functools.reduce(lambda x, y: x + y, [abs(a - ave - 2) for a in A])
B_1 = functools.reduce(lambda x, y: x + y, [abs(a - ave + 1) for a in A])
B_2 = functools.reduce(lambda x, y: x + y, [abs(a - ave + 2) for a in A])
print(min(B0, B1, B2, B_1, B_2))

Submission status: Wrong Answer

Solution code:
def calc(A,b):
    dif = 0
    for i,j in enumerate(A):
        dif+=abs(j-(b+i+1))
    return dif

N = int(input())
A = [int(i) for i in input().split()]
s = 0
for i in A:s+=i
m = s//N-N//2-1
a = calc(A,m)
b = calc(A,m+1)
c = calc(A,m-1)
print(min(a,b,c))

Submission status: Wrong Answer

Solution code:
import numpy as np
 
n = int(input())
a = list(map(int, input().split(" ")))

b = [i for i in range(1, n+1, 1)]

a = np.array(a)
b = np.array(b)

a -= b

ans = sum(abs(a))
while(True):
    a1 = (a < 0)
    a2 = (a > 0)

    a1 = a1 * a
    a2 = a2 * a
    if(abs(sum(a1)) > abs(sum(a2))):
        a += ((abs(sum(a1)) - abs(sum(a2))) // n + 1)
    else:
        a -= ((abs(sum(a2)) - abs(sum(a1))) // n + 1)
    if(ans <= sum(abs(a))): break
    else: ans = sum(abs(a))

print(ans)

Submission status: Wrong Answer

Solution code:
a = int(input())
b = list(map(int,input().split()))

for i in range(a):
	b[i] -= i + 1

b.sort()
s = 0
co = 0
ss = 0
coco = 0
cococo = 0
summ = 0
su = 0
for i in range(a):
	if b[i] < 0:
		s += b[i]
		co += 1
	elif b[i] > 0:
		ss += b[i]
		coco += 1
	else:
		cococo += 1
	su += abs(b[i])


if cococo == a:
	summ = 0

elif co == coco and abs(s) == abs(ss):
	for i in range(a):
		summ += abs(b[i])

elif co > coco:
	for i in range(a):
		if s != 0 and co != 0:
			summ += abs(b[i] - (s//co))
		else:
			summ += abs(b[i] - (s//co)+1)
elif co < coco:
	for i in range(a):
		if ss != 0 and ss % coco != 0:
			summ += abs(b[i] - (ss//coco))
		else:
			summ += abs(b[i] - (ss//coco - 1))

summ = min(su,summ)
print(summ)

Submission status: Wrong Answer

Solution code:
import functools
N = int(input())
A = [int(x) for x in input().split()]
for i,a in enumerate(A):
  A[i] = a - i - 1
ave = 0
sum = 0
for a in A:
  sum += a
  if abs(sum) >= N:
    add = sum // N
    ave += add
    sum -= N * add
B0 = functools.reduce(lambda x, y: x + y, [abs(a - ave) for a in A])
B1 = functools.reduce(lambda x, y: x + y, [abs(a - ave - 1) for a in A])
B2 = functools.reduce(lambda x, y: x + y, [abs(a - ave + 1) for a in A])
print(min(B0, B1, B2))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = []
plus = []
minus = []
zero = []
for i in range(n):
    tmp = a[i] - (i + 1)
    if tmp > 0:
        plus.append(tmp)
    elif tmp == 0:
        zero.append(tmp)
    else:
        minus.append(tmp)
    b.append(a[i] - (i + 1))

kouho = []
kouho.append(0)
if len(plus) == 0:
    pass
else:
    a_p = round(sum(plus)/len(plus))
    for i in range(3):
        kouho.append(a_p+ i-1)
if len(minus) == 0:
    pass
else:
    a_m = round(sum(minus)/len(minus))
    for i in range(3):
        kouho.append(a_m + i-1)
s = []
for i in kouho:
    s_tmp = 0
    for k in b:
        s_tmp += abs(k-i)
    s.append(s_tmp)
print(min(s))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
t=0
for i in range(n):
	t+=(a[i]-i-1)
b=t/n
b=int(b)-1
ans2=0
for i in range(n):
	ans2+=abs(a[i]-i-1-b)
b+=1
ans=0
for i in range(n):
	ans+=abs(a[i]-i-1-b)
ans1=0
b+=1
for i in range(n):
	ans1+=abs(a[i]-i-1-b)
print(min(min(ans,ans1),ans2))

Submission status: Wrong Answer

Solution code:
import sys
def calc(A,b):
    dif = 0
    for i,j in enumerate(A):
        dif+=abs(j-(b+i+1))
    return dif

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

s = 0
for i in A:s+=i
m = s//N
start = m-N//2-1
dif =calc(A,start)

if dif > calc(A,start+1):
    d = 1
    b = start+1
    while(True):
        if calc(A,b) > calc(A,b+d):
            dif = calc(A,b+d)
            b+=d
        else:
            break
elif dif > calc(A,start-1):
    d = -1
    b = start-1
    while(True):
        if calc(A,b) > calc(A,b+d):
            dif = calc(A,b+d)
            b+=d
        else:
            break
ans = dif
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
data = list(map(int, input().split()))
for i in range(N):
    data[i] -= (i + 1)
ave = sum(data) / N
if ave > 0:
    key = int(ave + 1)
    key1 = int(ave)
else:
    key = int(ave - 1)
    key1 = int(ave)
data.sort()
sumdata = 0
sumdata2 = 0
key = data[int(N / 2) - 1]
key2 = data[int(N / 2)]
print(data, key, key2)
for i in data:
    sumdata += abs(i - key)
    sumdata2 += abs(i - key2)

#print(sumdatax)
#print(data)
print(min([sumdata, sumdata2]))

Submission status: Wrong Answer

Solution code:
import statistics
import math

n = int(input())
a = [int(i) - (index+1) for index, i in enumerate(input().split())]

abs_total = 0
for i in a:
  abs_total += abs(i)

median = statistics.median(a) 

if n % 2 == 0 and median.is_integer() is False:
  median_high = int(median) + 1
  median_low = int(median)

  abs_high = abs(abs_total - (abs(median_high)*n))
  abs_low = abs(abs_total - (abs(median_high)*n))

  if abs_high < abs_low:
    print(int(abs_high))
  else:
    print(int(abs_low))
else:
  print(int(abs(abs_total - (abs(median)*n))))

Submission status: Wrong Answer

Solution code:
from math import ceil,floor
n=int(input())
a=[int(i) for i in input().split()]
for i in range(n):
  a[i]-=i+1


b1=ceil(sum(a)/n)

s=sum(a)
for i in range(b1-10**2,b1+10**2):
  def c1(x):
    return abs(x - i)
  s=min(s,sum(list(map(c1,a))))

print(s)

Submission status: Wrong Answer

Solution code:
import sys
def calc(A,b):
    dif = 0
    for i,j in enumerate(A):
        dif+=abs(j-(b+i+1))
    return dif

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

s = 0
for i in A:s+=i
m = s//N
start = m-N//2-1
dif =calc(A,start)

if dif > calc(A,start+1):
    d = 1
    b = 1
    while(True):
        if calc(A,b) > calc(A,b+d):
            dif = calc(A,b+d)
            b+=d
        else:
            break
elif dif > calc(A,start-1):
    d = -1
    b = -1
    while(True):
        if calc(A,b) > calc(A,b+d):
            dif = calc(A,b+d)
            b+=d
        else:
            break
ans = dif
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

def cost(b, A):
    N = len(A)
    c = 0
    for i in range(N):
        c += abs(b + i + 1 - A[i])
    return c

N = int(input())
l = input().split()
A = np.array([0]*N)
for i in range(N):
    A[i] = int(l[i])
    
b_sqmin = int(np.average(A) - (N+1)/2)
c_sqmin = cost(b_sqmin, A)
c_up = cost(b_sqmin+1, A)
c_down = cost(b_sqmin-1, A)

if c_sqmin == c_up or c_sqmin == c_down:
    print(c_sqmin)
    
elif c_up < c_sqmin:
    c_now = c_up
    b_now = b_sqmin + 1
    
    while True:
        c_next = cost(b_now+1, A)
        
        if c_next >= c_now:
            print(c_now)
            break
            
        c_now = c_next
        b_now = b_now + 1
        
else:
    c_now = c_down
    b_now = b_sqmin - 1
    
    while True:
        c_next = cost(b_now-1, A)
        
        if c_next >= c_now:
            print(c_now)
            break
            
        c_now = c_next
        b_now = b_now - 1

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a_total = sum(a)
n_total = 0
for i in range(1, n+1):
    n_total += i
b1 = int((a_total-n_total)/n)
b2 = int((a_total-n_total)/n - 1)
count1 = 0
count2 = 0
for i in range(1, n+1):
    count1 += abs(a[i-1] - i - b1)
    count2 += abs(a[i-1] - i - b2)
print(min(count1, count2))

Submission status: Wrong Answer

Solution code:
import functools
N = int(input())
A = [int(x) for x in input().split()]
for i,a in enumerate(A):
  A[i] = a - i - 1
sum = functools.reduce(lambda x, y: x + y, A)
print(int(((sum / N) - (sum // N)) * N))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
from bisect import bisect_left

Ans = 0
pans = 0
low,high = -(10**9),10**9
for i in range(100):
    anslow,anshigh = 0,0
    for i in range(N):
        anslow += abs(A[i]-(i+low))
        anshigh += abs(A[i]-(i+high))
    if anshigh > anslow:
        high=(high+low)//2
    else:
        low=(high+low)//2
    Ans = min(anshigh,anslow)

print(Ans)

Submission status: Wrong Answer

Solution code:
def calc(A,b):
    dif = 0
    for i,j in enumerate(A):
        dif+=abs(j-(b+i+1))
    return dif

N = int(input())
A = [int(i) for i in input().split()]
s = 0
for i in A:
    s+=i
m = s//N
print(calc(A,m-N//2-1))

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
A = np.array(list(map(int,input().split())))
n = np.array([i for i in range(A.size)][::-1])
A = A+n
ave = np.median(A)
print(ave)
print(A)
round = lambda x:int(x*2+1)//2
ave = round(ave)
A = A-ave
A = np.abs(A)
print(A.sum())

Submission status: Wrong Answer

Solution code:
a = int(input())
b = list(map(int,input().split()))

for i in range(a):
	b[i] -= i + 1

b.sort()
s = 0
co = 0
ss = 0
coco = 0
cococo = 0
summ = 0
su = 0
for i in range(a):
	if b[i] < 0:
		s += b[i]
		co += 1
	elif b[i] > 0:
		ss += b[i]
		coco += 1
	else:
		cococo += 1
	su += abs(b[i])


if cococo == a:
	summ = 0

elif co == coco and abs(s) == abs(ss):
	for i in range(a):
		summ += abs(b[i])

elif co > coco:
	for i in range(a):
		if s != 0:
			summ += abs(b[i] - (s//co))
elif co < coco:
	for i in range(a):
		if ss != 0:
			summ += abs(b[i] - (ss//coco))

summ = min(su,summ)
print(summ)