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: Runtime Error

Solution code:
import statistics
import math

N = int(input())
A = list(map(int, input().split()))
b = 0
li = []
if max(A) == N:  
  for i in range(N):
    li.append(abs(A[i]-(b+i+1)))
  print(sum(li))
else :
  mode = max(li)
  mode = max(statistics.mode(li))
  b = -mode
  for i in range(N):
    li.append(abs(A[i]-(b+i+1)))
  print(sum(li))

Submission status: Runtime Error

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

sum = 0
ans = []

for b in range(int(-N / 2), int(N / 2)):
    for i in range(N):
        sum += abs(A[i] - (b + i))
    else:
        ans.append(sum)
        sum = 0

print(min(ans))

Submission status: Runtime Error

Solution code:
import statistics
N = int(input())
L = list(map(int,input().split( )))
f1 = [li-j for li,j in zip(L,range(1+N+1))]
b = statistics.median(f1)
if N%2 != 0:
	ans = sum([abs(li-j-b) for li,j in zip(L,range(1+N+1))])
else:
	b1 = f1[int(b/2-0.5)]
	b2 = f1[int(b/2+0.5)]
	ans1 = sum([abs(li-j-b1) for li,j in zip(L,range(1+N+1))])
	ans2 = sum([abs(li-j-b2) for li,j in zip(L,range(1+N+1))])
	ans = min(ans1,ans2)
print(ans)

Submission status: Runtime Error

Solution code:
import math
n=int(input())
num_str=input().split()
num=list(map(int, num_str))
num=[num[i]-i-1 for i in range(n)]
ans = math.inf
for b in range(max(num)):
    ans_list=list(map(lambda x:abs(x-b), num))
    ans=min(ans,sum(ans_list))
print(ans)

Submission status: Runtime Error

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

new_A = [a-i-1 for i, a in enumerate(A)]

s = sum(new_A)
X = s // N

s1 = 0
for a in new_A:
    s1 += abs(a - X - 1)

s2 = 0
for a in new_A:
    s2 += abs(a - X)

s3 = 0
for a in new_A:
    s3 += abs(a - X + 1)

print(min(s1,s2,s3))

Submission status: Runtime Error

Solution code:
import math as m
N = int(input())
arr = map(int, input().split())

sum = 0
for i in range(N):
    arr[i] = arr[i] - i - 1
    sum += arr[i]

average = round(sum / N)

res =0
for i in range(len(N)):
    res += abs(average - arr[i])

print(res)

Submission status: Runtime Error

Solution code:
#c

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

for i in range(1,n+1):
    a[i-1] -= i
num1 = a[int(n/2)]
num2 = a[int(n/2)+1]

ans1 = 0
for i in range(n):
    ans1 += abs(a[i]-num1)
ans2 = 0
for i in range(n):
    ans2 += abs(a[i]-num2)

ans = min(ans1,ans2)
print(ans)

Submission status: Runtime Error

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

sub_num = [0]*(2*10**6)

for i in range(1, n+1):
#    print(abs(int(a[i-1]-i)))
    sub_num[abs(int(a[i-1]-i))] += 1

b = -sub_num.index(max(sub_num))
#print(b)

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

print(result)

Submission status: Runtime Error

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

sum = 0
j = 1
for i in lst:
    sum += (i-j)
    j+=1

//四捨五入
b = round(sum/n)

#print(b)

j = 1
sad = 0
for a in lst:
    sad += abs(a-(b+j))
    j += 1
print(sad)

Submission status: Runtime Error

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

sub_num = [0]*(2*10**5)

for i in range(1, n+1):
#    print(abs(int(a[i-1]-i)))
    sub_num[abs(int(a[i-1]-i))] += 1

b = -sub_num.index(max(sub_num))
#print(b)

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

print(result)

Submission status: Runtime Error

Solution code:
N = int(raw_input())
A = map(int, raw_input().split())
fa = [A[i] - (i + 1) for i in xrange(i)]
fb = map(lambda x: x - min(fa), fa)
print sum(fb)

Submission status: Runtime Error

Solution code:
N = int(input())
nums = input().split(" ")
nums2 = [int(x)-i-1 for i,x in enumerate(nums)]
nums2.sort()
length = len(nums2)
numpre = 0
same = 1
for n,m in zip(nums2[:-1],nums2[1:]):
  if n == m:
    same += 1
  else:
    impact = same + numpre
    if impact > length-impact:
      value = n
      break
    numpre += same
    same = 1
  value = m

answer = 0
for i in nums2:
  answer += abs(i-value)
print(answer)

Submission status: Runtime Error

Solution code:

N = int(input())
S = input()

candidate = []
for j in range(-max(A),max(A)):
    sad = 0
    for i in range(N):
        sad += abs(A[i] - j - i)
    candidate.append(sad)
ans = min(candidate)
print(ans)

Submission status: Runtime Error

Solution code:

import math


def main():
    n=input()
    n=int(n)
    temp=input()
    temp=list(map(int,list(temp.split(" "))))    
    
    ans=0
    cans=[]
    for i in range(n):
        temp[i]-=(i+1)
    # print(temp)
    av=sum(temp)/len(temp)
    can1=math.ceil(av)
    cans.append(can1)
    can2=math.floor(av)
    cans.append(can2)
    can3=can1-1
    cans.append(can3)
    can4=can1+1
    cans.append(can4)
    can5=can2-1
    cans.append(can5)
    can6=can2+1
    cans.append(can6)
    minus=[i for i in temp if i<=0]        
    plus=[i for i in temp if i>=0]
    av = sum(minus)/len(minus)
    can1=math.ceil(av)
    cans.append(can1)
    can2=math.floor(av)
    cans.append(can2)
    can3=can1-1
    cans.append(can3)
    can4=can1+1
    cans.append(can4)
    can5=can2-1
    cans.append(can5)
    can6=can2+1
    cans.append(can6)

    av = sum(plus)/len(plus)
    can1=math.ceil(av)
    cans.append(can1)
    can2=math.floor(av)
    cans.append(can2)
    can3=can1-1
    cans.append(can3)
    can4=can1+1
    cans.append(can4)
    can5=can2-1
    cans.append(can5)
    can6=can2+1
    cans.append(can6)
    anss=[]
    for c in cans:
        for t in temp:
            ans+=abs(t-c) 
        anss.append(ans)  
        ans=0  
    # print(anss)
    print(min(anss))  
    

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

b = 10000000
for i in range(100):
    sum = 0
    for j in range(n):
        sum = sum + abs(a[j] - (i + n))

    if sum < b:
        c = i
        b = sum


print(c)

Submission status: Runtime Error

Solution code:
from math import *
n=int(input())
arr=list(map(int,input().split()))
for i in range(n):
    arr[i]-=(i+1)
k=sum(arr)
l=floor(k/n)
if(l==0):
    ans1=0
    ans2=0
    ans3=0
    for i in range(n):
        ans1+=abs(arr[i])
        ans2+=abs(arr[i]-1)
        ans3+=abs(arr[i]+1)
    print(min(ans1,ans2,ans3))
else:
    ans1=0
    ans2=0
    for i in range(n):
        ans1+=abs(arr[i]-l)
        ans2+=abs(arr[i]-l-1)
        ans2+=abs(arr[i]-l+1)
    print(min(ans1,ans2,ans3))

Submission status: Runtime Error

Solution code:
from sys import stderr
from functools import reduce
from operator import add
def f(): return [int(i) for i in input().split()]
def debug(*x, sep=" ", end="\n"):
    for item in x:
        stderr.write(repr(item))
        stderr.write(sep)
    stderr.write(end)

n = int(input())
a = f()

b1 = (sum(a) - sum(range(1,n+1))) // n
b2 = b1 + 1
ans1 = 0
ans2 = 
for i,v in enumerate(a):
    ans1 += abs(v - (b1 + i + 1))
    ans2 += abs(v - (b2 + i + 1))
print(min(ans1,ans2))

Submission status: Runtime Error

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

for b in range(int(N/2)):
    for i in range(N):
        X += abs(A[i] - (b + i+1))
    ans.append(X)
    X = 0
    #
    for i in range(N):
        X += abs(A[i] - (i+1 - b))
    ans.append(X)
    X = 0

print(min(ans))

Submission status: Runtime Error

Solution code:
N = int(input())
nums = input().split(" ")
nums2 = [int(x)-i-1 for i,x in enumerate(nums)]
nums2.sort()
length = len(nums2)
numpre = 0
same = 1
for n,m in zip(nums2,nums2[1:]):
  if n == m:
    same += 1
  else:
    impact = same + numpre
    if impact > length-impact:
      value = n
      break
    numpre += same
    same = 1
answer = 0
for i in nums2:
  answer += abs(i-value)
print(answer)

Submission status: Runtime Error

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

def abs(a):
    if a<0:
        return -a
    else:
        return a

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

a.sort()
ans=10**12
mid=n//2
for b in range(a[mid],a[mid+1]):
    S=0
    for j in range(n):
        S+=abs(a[j]-b)
    ans=min(ans,S)
if ans==10**12:
    ans=0
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
A = np.array(list(map(int,input().split())))
X = np.array(range(1,N+1))
M = np.array([X,np.ones(len(X))])
M = M.T
a,b = np.linalg.lstsq(M,A)[0]
m1 = np.sum(np.absolute(A-X-int(b)))
m2 = np.sum(np.absolute(A-X-int(b)-1))
print(min([m1,m2]))
import numpy as np
N = int(input())
A = np.array(list(map(int,input().split())))
X = np.array(range(1,N+1))
M = np.array([X,np.ones(len(X))])
M = M.T
a,b = np.linalg.lstsq(M,A)[0]
m0 = np.sum(np.absolute(A-X-int(b)+2))
m1 = np.sum(np.absolute(A-X-int(b)+1))
m2 = np.sum(np.absolute(A-X-int(b)))
m3 = np.sum(np.absolute(A-X-int(b)-1))
m4 = np.sum(np.absolute(A-X-int(b)-2))
print(min([m0,m1,m2,m3,m4]))

Submission status: Runtime Error

Solution code:
from statistics import mode
n = int(input())
a = list(map(int,input().split()))
b = []
c = []
cnt = 1
for num in a:
    num -= cnt
    b.append(num)
    cnt += 1
if sum(b) != 0:
    cnt = 1
    for num in a:
        st = 0
        st = abs(num - (mode(b) + cnt))
        c.append(st)
        cnt += 1
    print(sum(c))
else:
    print(sum(b))

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
sadlist = []
for h in range(n):
    a[h] = a[h] - (h + 1)
for i in range(min(a), max(a)):
    sad = 0
    for j in range(n):
        sad = sad + abs(a[j] - i)
    sadlist.append(sad)
print(min(sadlist))

Submission status: Runtime Error

Solution code:
def FindAns(A, b):
    ans = 0
    for a in A:
        ans += abs(a - b)
    return ans

n = int(input())
A = list(map(int, input().split()))
for i in range(n):
    A[i] -= i + 1

center = int(sum(A) / len(A))
ans = 100000000000000
for i in range(21):
    ans = min(ans, FindAns(center - 50))
print(ans)

Submission status: Runtime Error

Solution code:
from statistics import mean
import math
N = int(input())
*A, = map(int, input().split())
B = [A[i]-i for i in range(N)]
bm = math.median(B)
K = [x - bm for x in B]
KZ = [abs(x) for x in K]
Z = sum(KZ)
for i in range(200):
    C = [abs(x-i+100) for x in K]
    Z = min([sum(C),Z])
print(int(Z))

Submission status: Runtime Error

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

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

b = int(median(list))

for i in range(n):
    list[i] = abs(list[i] - b)

print(sum(list))

Submission status: Runtime Error

Solution code:
import unittest

from app.ABC102_C import run


class TestSample(unittest.TestCase):
    def test_run(self):
        self.assertEqual(run(5, [2, 2, 3, 5, 5]), 2)
        self.assertEqual(run(9, [1, 2, 3, 4, 5, 6, 7, 8, 9]), 0)
        self.assertEqual(run(6, [6, 5, 4, 3, 2, 1]), 18)
        self.assertEqual(run(7, [1, 1, 1, 1, 2, 3, 4]), 6)


if __name__ == '__main__':
    unittest.main()

Submission status: Runtime Error

Solution code:
from statistics import mean
import math
N = int(input())
*A, = map(int, input().split())
B = [A[i]-i for i in range(N)]
bm = median(B)
K = [x - bm for x in B]
KZ = [abs(x) for x in K]
Z = sum(KZ)
for i in range(200):
    C = [abs(x-i+100) for x in K]
    Z = min([sum(C),Z])
print(int(Z))

Submission status: Runtime Error

Solution code:
ans = 9999999
res = 0
for i in range(N):
    res += A[i] - (i+1)

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

Submission status: Runtime Error

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

boundary = (-max(A)-1, max(A)+1)
sads = []
for b in range(*boundary):
    sads.append(sadness(A, b))
    
minimum = min(sads)
print(minimum)

Submission status: Runtime Error

Solution code:
# coding=utf-8

if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))
    A_modify = [A[j] - j - 1 for j in range(N)]
    A_modify.sort()

    if N % 2 == 0:
        mid1 = A_modify[N//2]
        mid2 = A_modify[mid1-1]
        A_modify1 = [abs(elm - mid1) for elm in A_modify]
        A_modify2 = [abs(elm - mid2) for elm in A_modify]
        print(min(sum(A_modify1), sum(A_modify2)))
    else:
        mid = N//2
        b = A_modify[mid]
        A_modify = [abs(elm - b) for elm in A_modify]
        print(sum(A_modify))

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
A = np.array(map(int,input().split()))
X = np.array(range(1,N+1))
M = np.array([X,np.ones(len(X))])
M = M.T
a,b = np.linalg.lstsq(M,A)[0]
m1 = np.sum(np.absolute(A-N-int(b)))
m2 = np.sum(np.absolute(A-N-int(b)-1))
print(min([m1,m2]))

Submission status: Runtime Error

Solution code:
def main():
    N = int(input())
    A = []
    for i in range(N):
        A.append(int(input()))
    C = [A[i] - i - 1 for i in range(N)]
    C.sort()
    m = N // 2
    x = C[m]
    left = sum([x - C[i] for i in range(m)])
    right = sum([C[i] - x for i in range(m + 1, N)])
    print(left + right)
    
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
input_list = [int(i) for i in input().split()]

ans1 = 0
ans2 = 0

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

point1 = sum(input_list) // N
point2 = point + 1

for i in range(N):
    ans1 += abs(input_list[i] - point1)

for i in range(N):
    ans2 += abs(input_list[i] - point2)

print(min(ans1, ans2))

Submission status: Runtime Error

Solution code:
n = int(input())

arr = map(int,raw_input().split())

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

mi = min(arr)
ma = max(arr)


ans = float("inf")
for i in range(mi,ma+1):
	count = 0
	for j in range(n):
		count += abs(arr[j]-i)

	ans = min(ans,count)

print ans

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import math

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

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

s = sum(b)
N = len(b)
mean = math.floor(s / N)
meanb = mean+1

t = sum([abs(b[i]-mean) for i in b])
u = sum([abs(b[i]-meanb) for i in b])

print(min(t,u))

Submission status: Runtime Error

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

def abs(a):
    if a<0:
        return -a
    else:
        return a

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

a.sort()
ans=10**12
for b in range(a[n//2],a[n//2+1]):
    S=0
    for j in range(n):
        S+=abs(a[j]-b)
    ans=min(ans,S)
if ans==10**12:
    ans=0
print(ans)

Submission status: Runtime Error

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

def abs(a):
    if a<0:
        return -a
    else:
        return a

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

a.sort()
ans=10**9
for b in range(a[n//2],a[n//2+1]):
    S=0
    for j in range(n):
        S+=abs(a[j]-b)
    ans=min(ans,S)
if ans==10**9:
    ans=0
print(ans)

Submission status: Runtime Error

Solution code:
import math
N = int(input())
A = [int(x) for x in input().split(' ')]
def score(A, b):
    s = 0
    for i, Ai in enumerate(A):
        s = math.abs(Ai - i - b)
    return s
s = math.inf
for b in range(min(A), max(A)):
    si = score(A, b)
    if si < s:
        s = si
print(s)