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:
n=int(input())
a=list(map(int,input().split()))
b=[0]*n
for i in range(n):
  b[i]=a[i]-(i+1)
b.sort()
if n%2:
  ans=b[(n-1)//2]
  an=0
  for i in range(n):
    an+=abs(a[i]-ans)
  print(an)
else:
  ans=(b[n//2]+b[n//2-1])//2
  an=0
  for i in range(n):
    an+=abs(a[i]-ans)
  print(an)

Submission status: Wrong Answer

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

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

ma=round(sum(A)/N)

an=[]
for j in [-1,0,1]:
  an.append(sum([abs(i-(ma+j)) for i in A]))
print(min(an))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[x-i for i,x in enumerate(list(map(int,input().split())))]
if n%2==1:
  print(sum([abs(x-a[n//2]) for x in a]))
else:
  print(min(sum([abs(x-a[n//2]) for x in a]),sum([abs(x-a[n//2+1]) for x in a])))

Submission status: Wrong Answer

Solution code:
n = int(input())
an = [int(j)-(i+1) for i,j in enumerate(input().split())]
print(sum(abs(i - an[len(an)//2]) for i in an))

Submission status: Wrong Answer

Solution code:

import sys
def input():
	return sys.stdin.readline().strip()

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

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

ans = 10**14

one = 0
three = 2
for i in range(1, N - 2):
	if three == i:
		three += 1
	sum_half1 = A_sum[i + 1]
	sum_half2 = A_sum[-1] - A_sum[i + 1]
	while one < i - 1:
		if abs(A_sum[one + 1] - sum_half1/2) > abs(A_sum[one + 2] - sum_half1/2):
			one += 1
		else:
			break
	while three < N - 2:
		if abs(A_sum[three + 1] - A_sum[i + 1] - sum_half2/2) > abs(A_sum[three + 2] - A_sum[i + 1] - sum_half2/2):
			three += 1
		else:
			break

	x = max(A_sum[one + 1], A_sum[i + 1] - A_sum[one + 1], A_sum[three + 1] - A_sum[i + 1], A_sum[-1] - A_sum[three + 1])
	y = min(A_sum[one + 1], A_sum[i + 1] - A_sum[one + 1], A_sum[three + 1] - A_sum[i + 1], A_sum[-1] - A_sum[three + 1])
	ans = min(ans, x - y)
	#print(one, i, three, x - y, ans, sum_half2//2)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = [a-i for i, a in enumerate(A)]
m = sum(B)//N
print(min(sum(abs(b-m-i) for b in B)for i in range(-9,9)))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = [a-i for i, a in enumerate(A)]
m = sum(B)//N
print(min(sum(abs(b-m-i) for b in B)for i in range(-1,2)))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = [a-i for i, a in enumerate(A)]
m = sum(B)//N
print(min(sum(abs(b-m) for b in B), sum(abs(b-m-1) for b in B)))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = [a-i for i, a in enumerate(A)]
m = round(sum(B)/N)
print(sum(abs(b-m) for b in B))

Submission status: Wrong Answer

Solution code:
import numpy as np

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

A_rot = np.array(list(enumerate(A, 1))).T
theta = np.pi / 4
R = np.array([[np.cos(theta), np.sin(theta)], [-np.sin(theta), np.cos(theta)]])
A_rot = np.dot(R, A_rot).T
loss = np.abs(A_rot[:, 1] - np.median(A_rot[:, 1])).sum()
print(int(np.round(np.sqrt(2) * loss)))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
for i in range(N):
  A[i] -= i+1
#print(A)

def calc(b):
  res = 0
  for i in range(N):
    res += abs(A[i]-b)
  return res

m = sum(A)//N
print(min(calc(m),calc(m+1),calc(m-1)))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
for i in range(N):
  A[i] -= i+1
#print(A)

def calc(b):
  res = 0
  for i in range(N):
    res += abs(A[i]-b)
  return res

m = sum(A)//N
print(min(calc(m),calc(m+1)))

Submission status: Wrong Answer

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

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

b=[int(sum(A)/len(A))-1,int(sum(A)/len(A)),int(sum(A)/len(A))+1]
m1,m2,m3=0,0,0

for i in range(N):
  m1+=abs(A[i]-b[0])
  m2+=abs(A[i]-b[1])
  m3+=abs(A[i]-b[2])
print(min(m1,m2,m3))

Submission status: Wrong Answer

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

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

temp=0

if N%2==0:
  ans = B[N//2]
  ans2= B[N//2 -1]
  temp=0
  for j in range(N):
    temp+= abs(B[j] - ans)
  temp2=0
  for j in range(N):
    temp2+= abs(B[j] - ans2)
  ans= min(temp,temp2)
else:
  ans = B[N//2]
  temp=0
  for j in range(N):
    temp+= abs(B[j] - ans )
  ans=temp
print(ans)

Submission status: Wrong Answer

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

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

temp=0

if N%2==0:
  ans = B[N//2]
  ans2= B[N//2 -1]
  temp=0
  for j in range(N):
    temp+= abs(B[j] - ans)
  temp2=0
  for j in range(N):
    temp2+= abs(B[j] - ans2)
  ans= min(temp,temp2)
else:
  ans = B[N//2]
  temp=0
  for j in range(N):
    temp+= abs(B[j] - ans )
  ans=temp
print(ans)

Submission status: Wrong Answer

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

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

temp=0

if N%2==0:
  ans = B[N//2]
  ans2= B[N//2 -1]
  temp=0
  for j in range(N):
    temp+= abs(A[j] - ans)
  temp2=0
  for j in range(N):
    temp2+= abs(A[j] - ans2)
  ans= min(temp,temp2)
else:
  ans = B[N//2]
  temp=0
  for j in range(N):
    temp+= abs(A[j] - ans )
  ans=temp
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
import math
N=int(input())
A=list(map(int,input().split()))
diff_dic=collections.defaultdict(int)


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

temp=0

if N%2==0:
  ans = B[N//2]
  ans2= B[N//2 -1]
  temp=0
  for j in range(N):
    temp+= abs(A[j] - (ans + j + 1))
  temp2=0
  for j in range(N):
    temp2+= abs(A[j] - (ans2+ j + 1))
  ans= min(temp,temp2)
else:
  ans = B[N//2]
  temp=0
  for j in range(N):
    temp+= abs(A[j] - (ans + j + 1))
  ans=temp
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
import math
N=int(input())
A=list(map(int,input().split()))
diff_dic=collections.defaultdict(int)


B=[A[i]-(i+1) for i in range(N)]
for i in range(N):
  diff_dic[B[i]]+=1
  
diff_list=sorted(list(diff_dic.items()), key=lambda x:x[1],reverse=True)
ans=diff_list[0][0]
temp=0

ans = B[N//2]
for j in range(N):
  temp+= abs(A[j] - (ans + j + 1))

print(temp)

Submission status: Wrong Answer

Solution code:
import collections
import math
N=int(input())
A=list(map(int,input().split()))
diff_dic=collections.defaultdict(int)


B=[A[i]-(i+1) for i in range(N)]
for i in range(N):
  diff_dic[B[i]]+=1
  
diff_list=sorted(list(diff_dic.items()), key=lambda x:x[1],reverse=True)
ans=diff_list[0][0]
temp=0

if N%2==0:
  ans = B[N//2]
  ans2 = B[(N//2)-1]
  temp=0
  for j in range(N):
    temp+= abs(A[j] - (ans + j + 1))
  temp2=0
  for j in range(N):
    temp2+= abs(A[j] - (ans2+ j + 1))
  print(min(temp,temp2))
else:
  ans = B[N//2]
  temp=0
  for j in range(N):
    temp+= abs(A[j] - (ans + j + 1))

  print(temp)

Submission status: Wrong Answer

Solution code:
import collections
import math
N=int(input())
A=list(map(int,input().split()))
diff_dic=collections.defaultdict(int)


B=[A[i]-(i+1) for i in range(N)]
for i in range(N):
  diff_dic[B[i]]+=1
  
diff_list=sorted(list(diff_dic.items()), key=lambda x:x[1],reverse=True)
ans=diff_list[0][0]
temp=0

if N%2==0:
  ans = (B[N//2]+B[(N//2) - 1]) // 2
  ans2= ans+1
  temp=0
  for j in range(N):
    temp+= abs(A[j] - (ans + j + 1))
  temp2=0
  for j in range(N):
    temp2+= abs(A[j] - (ans2+ j + 1))
  print(min(temp,temp2))
else:
  ans = B[N//2]
  temp=0
  for j in range(N):
    temp+= abs(A[j] - (ans + j + 1))

  print(temp)

Submission status: Wrong Answer

Solution code:
import collections
import math
N=int(input())
A=list(map(int,input().split()))
diff_dic=collections.defaultdict(int)


B=[A[i]-(i+1) for i in range(N)]
for i in range(N):
  diff_dic[B[i]]+=1
  
diff_list=sorted(list(diff_dic.items()), key=lambda x:x[1],reverse=True)
ans=diff_list[0][0]
temp=0

if N%2==0:
  ans = (B[N//2]+B[N//2 - 1]) // 2
else:
  ans = B[N//2]

temp=0
for j in range(N):
  temp+= abs(A[j] - (ans + j + 1))
print(temp)

Submission status: Wrong Answer

Solution code:
import collections
import math
N=int(input())
A=list(map(int,input().split()))
diff_dic=collections.defaultdict(int)


B=[A[i]-(i+1) for i in range(N)]
for i in range(N):
  diff_dic[B[i]]+=1
  
diff_list=sorted(list(diff_dic.items()), key=lambda x:x[1],reverse=True)
ans=diff_list[0][0]
temp=0

ans=sum(B) / N
temp=0
for j in range(N):
  temp+= abs(A[j] - (int(ans) + j + 1) )


temp2=0
for j in range(N):
  if ans>=0:
    temp2+= abs(A[j] - (math.ceil(ans) + j + 1) )
  else:
    temp2+= abs(A[j] - (math.ceil(ans) + j))
print(min(temp,temp2))

Submission status: Wrong Answer

Solution code:
import collections
N=int(input())
A=list(map(int,input().split()))
diff_dic=collections.defaultdict(int)


B=[A[i]-(i+1) for i in range(N)]
for i in range(N):
  diff_dic[B[i]]+=1
  
diff_list=sorted(list(diff_dic.items()), key=lambda x:x[1],reverse=True)
ans=diff_list[0][0]
temp=0
for j in range(N):
  temp+= abs(A[j] - (ans + j + 1) )
print(temp)

Submission status: Wrong Answer

Solution code:
import collections
N=int(input())
A=list(map(int,input().split()))
diff_dic=collections.defaultdict(int)


B=[A[i]-(i+1) for i in range(N)]
for i in range(N):
  diff_dic[B[i]]+=1
  
diff_list=sorted(list(diff_dic.items()), key=lambda x:x[1],reverse=True)
ans=diff_list[0][0]
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#ARC100 C

import sys
import math
import bisect
import time
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
b = [a[i] - (i+1) for i in range(n)]
c,d = math.ceil(sum(b)/n),sum(b)//n
ans1,ans2 = 0,0
for i in range(n):
    ans1 += abs(a[i] -(c + i+1))
    ans2 += abs(a[i] -(d + i+1))
print(min(ans1,ans2))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#ARC100 C

import sys
import math
import bisect
import time
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
b = [a[i] - (i+1) for i in range(n)]
c = sum(b)//n
ans = 0
for i in range(n):
    ans += abs(a[i] -(c + i+1))
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A = [A[n]-n for n in range(N)]
A.sort()
if N % 2 == 1:
  A = [abs(a - A[N//2]) for a in A]
  ans = sum(A)
else:
  temp = A
  A = [abs(a - A[N//2]) for a in A]
  ans = sum(A)
  A = [abs(a - A[N//2-1]) for a in A]
  ans = min(ans, sum(A))

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A = [A[n]-n for n in range(N)]
ave_A = sum(A)//N
temp_A = A
A = [abs(a - ave_A) for a in A]
ans = abs(sum(A))
A = [abs(a -1) for a in temp_A]
ans = min(ans, abs(sum(A)))
A = [abs(a +1) for a in temp_A]
ans = min(ans, abs(sum(A)))
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A = [A[n]-n for n in range(N)]
ave_A = sum(A)//N
temp_A = A
A = [abs(a - ave_A) for a in A]
ans = abs(sum(A))
A = [abs(a -1) for a in temp_A]
ans = min(ans, abs(sum(A)))
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A = [A[n]-n for n in range(N)]
ave_A = sum(A)//N
A = [abs(a - ave_A) for a in A]
ans = abs(sum(A))
A = [abs(a  -1) for a in A]
ans = min(ans, abs(sum(A)))
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A = [A[n]-n for n in range(N)]
ave_A = sum(A)//N
A = [abs(a - ave_A) for a in A]
print(abs(sum(A)))

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 + 1)
a = sorted(a)
if n % 2 == 1:
    b = a[n // 2]
    total = 0
    for i in range(n):
        total += a[i] - b
    print(total)
else:
    bs = [a[n // 2], a[n // 2 + 1]]
    ret = float('inf')
    for b in bs:
        total = 0
        for i in range(n):
            total += a[i] - b
        ret = min(ret, total)
    print(total)

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 + 1)
a = sorted(a)
b = a[n // 2]

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

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 + 1)
a = sorted(a)
print(a[n // 2])

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int,input().split()))
A = [0] * N
for i in range(N):
    A[i] = a[i]-(i+1)
A_p = list(filter(lambda x: x > 0, A))
A_n = list(filter(lambda x: x < 0, A))
A_zero = list(filter(lambda x: x==0, A))
if len(A_zero) > len(A_p) and len(A_zero) > len(A_n):
    exit()
if len(A_p) > len(A_n):
    b = A[N//2]
elif len(A_p) < len(A_n):
    b = A[N//2]
else:
    b = 0
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 = [i-idx-1 for idx,i in enumerate(a)]
import statistics as st
b = st.median(a)
print(sum([abs(i-b) for i in a])//1)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a = [i-idx-1 for idx,i in enumerate(a)]
import statistics as st
b = st.median(a)
print(sum([abs(i-b) for i in a]))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a = [i-i-1 for idx,i in enumerate(a)]
import statistics as st
b = st.median(a)
print(sum([abs(i-b) for i in a]))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
for i in range(n):
	a[i]-=(i+1)
x=sum(a)/n
l=int(x)
r=int(x+1)
m=int(x-1)
ans1=0
ans2=0
ans3=0
for i in range(n):
	ans1+=abs(a[i]-l)
	ans2+=abs(a[i]-r)
	ans3+=abs(a[i]-m)
print(min(ans1,ans2,ans3))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
for i in range(n):
	a[i]-=(i+1)
if sum(a)/n>=0:
	x=int((sum(a)/n+0.5))
else:
	x=int((sum(a)/n)-0.5)
ans1=0
ans2=0
ans3=0
for i in range(n):
	ans1+=abs(a[i]-x)
	ans2+=abs(a[i]-x+1)
	ans3+=abs(a[i]-x-1)
print(min(ans1,ans2,ans3))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from statistics import mean
import math
n = int(input())
a = [int(i) for i in input().split()]
for i in range(n):
    a[i] -= i+1
a_fl = math.floor(mean(a))
a_ce = math.ceil(mean(a))
ans_fl=ans_ce=0

for i in range(n):
    ans_fl += abs(a[i]-a_fl)
    ans_ce += abs(a[i]-a_ce)
print(int(min(ans_fl,ans_ce)))

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res

def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

n = I()
a = LI()
for i in range(n):
    a[i] -= i+1
b = sum(a)//n
ans = 0
for i in range(n):
    ans += abs(a[i]-b)
b = sum(a)//n+1
ans_ = 0
for i in range(n):
    ans_ += abs(a[i]-b)
print(min(ans,ans_))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
minA = min(A)
for i in range(N):
    A[i] -= i+1 
minA = min(A)
for i in range(N):
    A[i] -= minA
#print(A)
b = round(sum(A) // len(A))
for i in range(N):
    A[i] = abs(A[i]-b)

print(sum(A))

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
tmp = 0
s = 0

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

B = np.copy(A)

tmp = np.sum(np.abs(A))
#print(tmp)

tmp1 = 10**7
tmp = np.sum(np.abs(A))

while tmp < tmp1:
    tmp1 = np.sum(np.abs(A))
    A -= 1
    tmp = np.sum(np.abs(A))

ans1 = tmp1

tmp = np.sum(np.abs(B))
tmp1 = 10**7

while tmp < tmp1:
    tmp1 = np.sum(np.abs(B))
    B += 1
    tmp = np.sum(np.abs(B))

ans2 = tmp1

print(min(ans1, ans2))

Submission status: Wrong Answer

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

S = sorted(A)
b = S[N//2]-N//2-1

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

Submission status: Wrong Answer

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

b = sum(A)//N - N//2 -1
ans = 0
for i in range(N):
    ans += abs(A[i] - (b + i + 1))
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    c = [a[i] - i - 1 for i in range(n)]
    bsmall = sum(c) // n
    sadsmall = sum([abs(cc - bsmall + 1) for cc in c])
    sadnormal = sum([abs(cc - bsmall) for cc in c])
    sadlarge = sum([abs(cc - bsmall - 1) for cc in c])
    print(min(sadsmall, sadnormal, sadlarge))


main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    c = [a[i] - i - 1 for i in range(n)]
    bsmall = int(sum(c) // n)
    sadsmall = sum([abs(cc - bsmall) for cc in c])
    sadlarge = sum([abs(cc - bsmall - 1) for cc in c])
    print(min(sadsmall, sadlarge))


main()

Submission status: Wrong Answer

Solution code:
from statistics import mean
import math
n = int(input())
a = list(map(int,input().split()))
for i in range(0,n):
    a[i] = a[i]-(i+1)
b1 = math.floor(mean(a))
b2 = math.ceil(mean(a))
a1 = []
a2 = []
for i in range(0,n):
    a1.append(abs(a[i]-b1))
    a2.append(abs(a[i]-b2))
print(min(sum(a1),sum(a2)))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
num = [int(i) for i in range(1, n+1)]

all_a = sum(a)
all_num = sum(num)

count = [0] * n
abs_count = [0] * n
ans = 0

for i in range(n):
    count[i] += a[i] - num[i]
    abs_count[i] += abs(a[i] - num[i])

if all_a - all_num >= 0 and sum(count) >= 0:
    ans = sum(abs_count)
else:
    b = abs(min(count))
    b_num = b * n
    ans = sum(count) + b_num

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

num_list = [ int(v) for v in input().split() ]
num_list = [ num_list[i] - (i+1) for i in range(n) ]
mean = sum(num_list)//n
mean2 = mean + 1 

d_list = [i-mean for i in num_list]
u_list = [i-mean2 for i in num_list]

print(min(sum(map(abs,d_list)),sum(map(abs,u_list))))

Submission status: Wrong Answer

Solution code:
N = int(input())
Ap = [int(x) for x in input().split()]
A = [Ap[i]  -i-1 for i in range(N)]

sumA = sum(A)
if sumA % N == 0:
    b = sumA//N
    print( sum( [abs(x-b) for x in A] ) )
else:
    b1 = sumA//N
    b2 = b1 + 1
    print( min( sum( [abs(x-b) for x in A] ) for b in [b1,b2]))

Submission status: Wrong Answer

Solution code:
import math
import numpy as np
N = int(input())
A = [int(_) for _ in input().split()]
B = np.array([A[i]-i for i in range(N)])
x = np.mean(B)
y = np.sum([abs(B[i] - math.floor(x)) for i in range(N)])
z = np.sum([abs(B[i] - math.ceil(x)) for i in range(N)])
print(min(y,z))

Submission status: Wrong Answer

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

l = sorted([ x - (idx+1) for x,idx in enumerate(A)])
print(l)

import statistics
median = statistics.median(l)
print(median)

ans = 0
for x in l:
  ans += abs(x - median)
  
print(int(ans))

Submission status: Wrong Answer

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

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

ave1 = sum(A)//N
ave2 = (sum(A)+N)//N
ave3 = ave1 - 1

ans1 = 0
for i in range(N):
    ans1 +=abs(A[i]-ave1)

ans2 = 0
for j in range(N):
    ans2 += abs(A[i]-ave2)

ans3 = 0
for k in range(N):
    ans3 += abs(A[i]-ave3)
    
print (min(ans1, ans2, ans3))

Submission status: Wrong Answer

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

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

ave1 = sum(A)//N
ave2 = (sum(A)+N)//N

ans1 = 0
for i in range(N):
    ans1 +=abs(A[i]-ave1)

ans2 = 0
for j in range(N):
    ans2 += abs(A[i]-ave2)

print (min(ans1, ans2))

Submission status: Wrong Answer

Solution code:
import statistics
import math

n = int(input())
A = list(map(int, input().split()))
B = []
ans = 0

for i in range(n):
    B.append(A[i]-i-1)
    
med = statistics.median(B)

for i in range(n):
    ans += abs(A[i]-(med+i+1))

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int, input().split()))
X=(N+1)*N/2
ans=abs(round(sum(A)-X))
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a= [int(i) for i in input().split()]

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

aa=sorted(a)
if n%2==0:
  b=(aa[int(n/2-1)]+aa[int(n/2)])/2
else:
  b=aa[int((n-1)/2)]

s=0
for i in aa:
  s+=abs(i-b)
print(s)

Submission status: Wrong Answer

Solution code:
n = int(input())
a= [int(i) for i in input().split()]

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

import math
import statistics
b=statistics.median(a)
#b=math.floor(sum(a)/n)


def p(b,k):
  s=0
  for i in a:
      s+=abs(i-b)
  t=0
  for i in a:
      t+=abs(i-b-1) 
  if s>t:
    if k==-1:
      print(t)
    else:
      return p(b+1,1)
  else:
    if k==1:
      print(s)
    else:
      return p(b-1,-1)
  
p(b,0)

Submission status: Wrong Answer

Solution code:
n = int(input())
a= [int(i) for i in input().split()]

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

import math
b=math.floor(sum(a)/n)

s=0
for i in a:
    s+=abs(i-b)
t=0
b+=1
for i in a:
    t+=abs(i-b) 
u=0
b-=2
for i in a:
    u+=abs(i-b) 

if s>=t and u>=t:
    print(t)
elif s<=u:
    print(s) 
else:
  print(u)

Submission status: Wrong Answer

Solution code:
n = int(input())
a= [int(i) for i in input().split()]

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

import math
b=math.floor(sum(a)/n)

s=0
for i in a:
    s+=abs(i-b)
t=0
b+=1
for i in a:
    t+=abs(i-b) 

if s>=t:
    print(t)
else:
    print(s)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
for i in range(N):
    A[i] = A[i] - (i+1)
A.sort
b = A[N//2]
ans = 0
for a in A:
    ans += abs(a - b)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
diff = [0] * N
for i in range(N):
    diff[i] = A[i] - (i+1)
diff.sort
b = diff[N//2]
ans = 0
for a in diff:
    ans += abs(a - b)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
diff = [0] * N
for i in range(N):
    diff[i] = A[i] - (i+1)
diff.sort

b1 = diff[(len(diff) - 1) // 2]
b2 = diff[(len(diff)) // 2]

ans1 = 0
for i, a in enumerate(A):
    ans1 += abs(a - (i+1+b1))
ans2 = 0
for i, a in enumerate(A):
    ans2 += abs(a - (i+1+b2))
print(min(ans1, ans2))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
diff = [0] * N
for i in range(N):
    diff[i] = A[i] - (i+1)
diff.sort
b = diff[len(diff) // 2]

ans = 0
for i, a in enumerate(A):
    ans += abs(a - (i+1+b))
print(ans)

Submission status: Wrong Answer

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

for i in range(n):
    SUM += a[i]-i-1
    B.append(a[i]-i-1)

B.sort()
if n%2 == 1:
    b = B[n//2]
else:
    b = (B[n//2-1]+B[n//2])//2
print(SUM-b*n)

Submission status: Wrong Answer

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

aa = [ai - i-1 for i,ai in enumerate(a)]

def tri_search(f:"f(x:float)->float", left, right, iter=100)->float:
    for _ in range(iter):
        ml = (left*2 + right) / 3
        mr = (left + right*2) / 3
        if f(ml) < f(mr):
            right = mr
        else:
            left = ml
    # print(left, right)
    return (right + left) / 2

def f(x):
    ret = 0
    x = int(x+0.5)
    for aai in aa:
        ret += abs(aai - x)
    return ret

b = tri_search(f, -10**9, 10**9)
print(min(f(b), f(b)+1, f(b)-1))

Submission status: Wrong Answer

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

aa = [ai - i-1 for i,ai in enumerate(a)]

def tri_search(f:"f(x:float)->float", left, right, iter=100)->float:
    for _ in range(iter):
        ml = (left*2 + right) / 3
        mr = (left + right*2) / 3
        if f(ml) < f(mr):
            right = mr
        else:
            left = ml
    # print(left, right)
    return (right + left) / 2

def f(x):
    ret = 0
    x = int(x+0.5)
    for aai in aa:
        ret += abs(aai - x)
    return ret

b = tri_search(f, -10**9, 10**9)
print(f(b))

Submission status: Wrong Answer

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

aa = [ai - i-1 for i,ai in enumerate(a)]

def tri_search(f:"f(x:float)->float", left, right, iter=100)->float:
    for _ in range(iter):
        ml = (left*2 + right) / 3
        mr = (left + right*2) / 3
        if f(ml) < f(mr):
            right = mr
        else:
            left = ml
        # print(left, right)
    return (right + left) / 2

def f(x):
    ret = 0
    for aai in aa:
        ret += abs(aai - x)
    return ret

b = tri_search(f, -10**9, 10**9)
print(f(round(b)))

Submission status: Wrong Answer

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

aa = [ai - i-1 for i,ai in enumerate(a)]

def tri_search(f:"f(x:float)->float", left, right, iter=100)->float:
    for _ in range(iter):
        ml = (left*2 + right) / 3
        mr = (left + right*2) / 3
        if f(ml) < f(mr):
            right = mr
        else:
            left = ml
        # print(left, right)
    return (right + left) / 2

def f(x):
    ret = 0
    for aai in aa:
        ret += abs(aai - x)
    return ret

ans = tri_search(f, -10**9, 10**9)
print(round(f(ans)))

Submission status: Wrong Answer

Solution code:
def mm(N, A, x):
  S = 0
  for i in range(N):
    S += abs(A[i] - x)
  return S

N = int(input())
A = []
j = 0
for i in input().split():
  j += 1
  A.append(int(i)-j)
x = sum(A) // N
print(min(mm(N, A, x), mm(N, A, x+1)))

Submission status: Wrong Answer

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

a = [aa-i for i, aa in enumerate(a, start = 1)]
if n%2 == 1:
    med = a[n//2]
    ans = sum([abs(aa - med) for aa in a])
else:
    med1 = (a[n//2]+a[n//2+1])//2
    ans1 = sum([abs(aa - med1) for aa in a])
    med2 = (a[n//2]+a[n//2+1])//2+1
    ans2 = sum([abs(aa - med2) for aa in a])
    ans = min(ans1, ans2)
print(ans)

Submission status: Wrong Answer

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

a = [aa-i for i, aa in enumerate(a, start = 1)]
med = a[n//2] if n%2 == 1 else (a[n//2]+a[n//2+1])//2
ans = sum([abs(aa - med) for aa in a])
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
B = (sum(A)-sum(range(1,N+1)))//N
ans = 0
for a,i in zip(A,range(1,N+1)):
    ans += abs(a-(B+i))
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
#a, b, c = map(int, input().split())
#name1 = str(input())
#alph = {"A": 1, "B": 2, "C": 3, "D": 4, "E": 5}
for i in range(N):
    A[i] = A[i] - (i + 1)
b = A[int(N / 2)]
ans = 0
for i in range(N):
    ans += abs(A[i] - b)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
#a, b, c = map(int, input().split())
#name1 = str(input())
#alph = {"A": 1, "B": 2, "C": 3, "D": 4, "E": 5}
for i in range(N):
    A[i] = A[i] - (i + 1)
B = [abs(x) for x in A]
if sum(A[:]) / N < 0:
    b = int(sum(A[:]) / N) - 1
    print(abs(sum(B[:]) + b * N))
else:
    b = int(sum(A[:]) / N)
    print(sum(B[:]) - b * N)

Submission status: Wrong Answer

Solution code:
n=int(input())
lista = [int(i) for i in input().split()]
summ = 0
for i in range(n):
    summ += lista[i]-(1*i +1)
ave = summ//n
ans = 0
for i in range(n):
    ans += abs(lista[i]-(1*i +1)-ave)
    
ave = summ//n
ave += 1
ans1 = 0
for i in range(n):
    ans1 += abs(lista[i]-(1*i +1)-ave)
    
ave = summ//n
ave -= 1
ans2 = 0
for i in range(n):
    ans2 += abs(lista[i]-(1*i +1)-ave)
    
print(min(ans,ans1,ans2))

Submission status: Wrong Answer

Solution code:
n=int(input())
lista = [int(i) for i in input().split()]
summ = 0
for i in range(n):
    summ += lista[i]-(1*i +1)
ave = summ//n
ans = 0
for i in range(n):
    ans += abs(lista[i]-(1*i +1)-ave)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import math

N = int(input())
a = np.array(list(map(int, input().split())))
adj = a - np.arange(1, N+1)
med = np.median(adj)

ans = 10 ** 10
if med.is_integer():
	t0 = int(med)
else:
	t0 = int(math.floor(med))

for opt in range(t0, t0 + 1):
	res = 0
	for i in range(N):
		res += abs(adj[i] - opt)
	ans = min(ans, res)
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import numpy as np

N = int(input())
list_A = list(map(int, input().split()))
arr_A = np.array(list_A)

b_opt = (arr_A.sum() - N * (N + 1) / 2) / N

sadness = min(np.abs(arr_A - np.arange(1, N + 1) - np.ceil(b_opt)).sum(),
              np.abs(arr_A - np.arange(1, N + 1) - np.floor(b_opt)).sum()
              )
print(int(sadness + 1e-5))