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: Accepted

Solution code:
#                         author:  kagemeka 
#                         created: 2019-11-08 14:51:29(JST)
## internal modules
import sys
# import collections
# import math
# import string
# import bisect
# import re
# import itertools
import statistics
# import functools
# import operator
## external modules
# import scipy.special   # if use comb function on AtCoder, 
# import scipy.misc      # select scipy.misc.comb (old version) 

def main():
    n, *a = (int(x) for x in sys.stdin.read().split())
    
    for i in range(n):
        a[i] -= (i + 1)

    if n % 2 != 0:
        b = statistics.median(a)
    else:
        if a.count(statistics.median_high(a)) >= a.count(statistics.median_low(a)):
            b = statistics.median_high(a)
        else:
            b = statistics.median_low(a)
    
    ans = sum([abs(a[i] - b) for i in range(n)])
    print(ans)


if __name__ == "__main__":
    # execute only if run as a script
    main()

Submission status: Accepted

Solution code:
#                         author:  kagemeka 
#                         created: 2019-11-08 14:51:29(JST)
## internal modules
import sys
# import collections
# import math
# import string
# import bisect
# import re
# import itertools
# import statistics
# import functools
# import operator
## external modules
# import scipy.special   # if use comb function on AtCoder, 
# import scipy.misc      # select scipy.misc.comb (old version) 

def main():
    n, *a = (int(x) for x in sys.stdin.read().split())
    
    for i in range(n):
        a[i] -= (i + 1)

    a.sort()
    if n % 2 != 0:
        b = a[n // 2]
    else:
        if a.count(a[n // 2]) >= a.count(a[n // 2 - 1]):
            b = a[n // 2]
        else:
            b = a[n // 2 - 1]
    
    ans = sum([abs(a[i] - b) for i in range(n)])
    print(ans)


if __name__ == "__main__":
    # execute only if run as a script
    main()

Submission status: Accepted

Solution code:
import numpy as np

n = int(input())
a = list(map(int, input().split()))
i = [i for i in range(1, n+1)]
l = np.array(a) - np.array(i)
b = int(np.median(l))

ans = sum(a)
for i in range(-3, 4):
    ans = min(ans, sum(abs(l-b+i)))

print(ans)

Submission status: Accepted

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

li = []

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

li.sort()
#print(li)
memo = len(li)
memo2 = li[memo//2]

li2 = [-(memo2) for i in range(len(li))]
for i in range(n):
    li[i] = li[i] + li2[i]
#print(li)
ttl = 0
for i in range(n):
    ttl += abs(li[i])

print(ttl)

Submission status: Accepted

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

Submission status: Accepted

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()
x = 0
ab = 0
if n%2==0:
    x = int(n//2)
    ab = b[x]+b[x-1]
    ab = ab//2
else:
    x = int((n+1)//2 -1)
    ab = b[x]
ans = 0
for i in range(n):
    ans += abs(b[i]-ab)
print(ans)

Submission status: Accepted

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

B = []
for i in range(N):
    B.append(A[i] - (i+1))
    
B = sorted(B)
b = B[len(B) // 2]
ans = 0
for i in range(N):
    ans += abs(A[i] - (b + i + 1))

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(a) for a in input().split()]
A = sorted([A[i] - i for i in range(N)])
b = A[N//2]

print(sum([abs(a-b) for a in A]))

Submission status: Accepted

Solution code:
import math
import copy
import sys
import fractions
import numpy as np
from functools import reduce
import statistics


# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputoData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

n = getInputInt()
data = getInputListInt()

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

ave = statistics.median(data)



ans = 0

for i in range(n):
    ans += abs(data[i] - ave)

print(int(ans))

Submission status: Accepted

Solution code:

# -*- coding utf-8 -*-

MOD = 10 ** 9 + 7

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

if len(an) % 2 == 0:
    b = (an[n//2] + an[n//2 - 1])/2
else:
    b = an[n//2]

ans = int(sum([abs(a - b) for a in an]))

print(ans)

Submission status: Accepted

Solution code:
# 絶対値誤差を最小値にする値は中央値である

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


def main():
    import math
    import collections
    import itertools
    import functools

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

    as_minus_i = [a - i for a, i in zip(as_, range(1, n + 1))]
    median = sorted(as_minus_i)[n // 2]
    
    ans = functools.reduce(lambda x, y: x + abs(y - median), as_minus_i, 0)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import statistics

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

B = [x - (i+1) for i,x in enumerate(A)]
cent = statistics.median(B)

print(int(sum([abs(x-cent) for x in B])))

Submission status: Accepted

Solution code:
import numpy as np

n=int(input())
a_list=np.array(list(map(int,input().split())))
i_list=np.array([i+1 for i in range(n)])
b_list=a_list-i_list

median_value=np.median(b_list)

print(int(sum([abs(i-median_value) for i in b_list])))

Submission status: Accepted

Solution code:
import numpy as np
import statistics

N = int(input())
A = np.array(list(map(int, input().split())))
R = np.array([x+1 for x in range(N)])

med = int(np.median((A-R)))
print(abs(A-R-med).sum())

Submission status: Accepted

Solution code:
n=int(input())
l=[int(i) for i in input().split()]
def check(x):
    sm=0 
    for i in range(n):
        sm+=abs(l[i]-(i+x+1))
    return sm 
lo=-(10**10)
hi=10**10 
while lo<=hi:
    mi=(lo+hi)>>1 
    a=check(mi)
    b=check(mi-1)
    c=check(mi+1)
   # print(mi,a,b,c)
    if b<=a: 
        hi=mi-1 
        ans=b
    elif c<=a:
        ans=c
        lo=mi+1 
    else:
        ans=a 
        break
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

n = int(input())
A = list(map(int,input().split()))
A = np.array([a-i for i,a in enumerate(A,1)])
A = np.sort(A)

#中央値
if n % 2:
	z = A[n//2]
else:
	x = A[n//2-1]
	y = A[n//2]
	z = (x+y)//2

Z = np.array([z]*n)
# print(A,Z)
print(abs(np.sum(abs(A-Z))))

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
A = list(map(int,input().split()))
B = []
ans = 0
 
for i in range (0,N):
  A[i] = A[i] - (i + 1)

median = np.median(A)

for i in range (0,N):
  ans = ans + abs(A[i] - median)
print(int(ans))

Submission status: Accepted

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

Submission status: Accepted

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

B=sorted([x-(i+1) for i,x in enumerate(A)])

print(sum([B[N-1-i]-B[i] for i in range(N//2)]))

Submission status: Accepted

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

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

# ave = sum(a)/n
# ave1= math.ceil(ave)
# ave2= math.floor(ave)


# print(min(sum([abs(a[i]-ave1) for i in range(n)]),sum([abs(a[i]-ave2) for i in range(n)])))

a.sort()
med1=a[n//2-1]
med3=a[n//2]

print(min(sum([abs(a[i]-med1) for i in range(n)]),sum([abs(a[i]-med3) for i in range(n)])))

Submission status: Accepted

Solution code:
N=int(input())
l=list(map(int,input().split()))
for i in range(N):
  l[i] -= i
l.sort()
center_num=l[N//2]
ans=0
for i in range(N):
  ans+=abs(l[i]-center_num)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import statistics

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

M=statistics.median(A)
A=[abs(i-M) for i in A]
print(int(sum(A)))

Submission status: Accepted

Solution code:


def resolve():
    N=int(input())
    A=[int(i) for i in input().split()]
    B=[A[i]-(i+1) for i in range(N)]
    B.sort()
    x=B[(N-1)//2]
    print(sum([abs(i-x) for i in B]))



if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import math
import statistics
n = int(input())
a = list(map(int,input().split()))
a = [aa-i-1 for i, aa in enumerate(a)]
answer = n*10**20
median_low = statistics.median_low(a)
median_high = statistics.median_high(a)

for m in (median_low,median_high):
  ans=0
  for aa in a:
    ans += abs(aa-m)
  answer = min(ans,answer)
print(answer)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N = int(readline())
A = np.array(read().split(),np.int64)

A -= np.arange(1,N+1)

# Aの中央値

A.sort()
x = A[N//2]
answer = np.abs(A-x).sum()
print(answer)

Submission status: Accepted

Solution code:
n = int(input())
ary = sorted([j-(i+1) for i,j in enumerate(map(int,input().split()))])
if len(ary) % 2 == 0:
    a = (ary[len(ary)//2]+ary[len(ary)//2-1])//2
    ans = 0
    for i in ary:
        ans += abs(i - a)
else:
    a = ary[len(ary)//2]
    ans = 0
    for i in ary:
        ans += abs(i - a)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
L = []
ans = 0
for i in range(N):
  L.append(A[i] - (i + 1))
L = sorted(L)
B = L[N // 2]
for i in range(N):
  ans += abs(A[i]-(B + i + 1))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
t = [int(n) - i for i, n in enumerate(input().split())]
t.sort()
b = t[len(t) // 2]
print(sum([abs(n - b) for n in t]))

Submission status: Accepted

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

Submission status: Accepted

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

def f(b):
    r = 0
    for i, ai in enumerate(A):
        r += abs(ai - (b + i + 1))
    return r


A2 = []
for i, ai in enumerate(A):
    A2.append(ai - (i+1))

SA2 = sorted(A2)
ans = f(SA2[((N+1)//2) - 1])
print(ans)

Submission status: Accepted

Solution code:
Data = []
def diff(b):
    sum1 = 0
    for d in Data:
        sum1 += abs(b-d)
    return sum1

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

Data.sort()
if N % 2 != 0:
    mid = Data[N//2]
    ans = diff(mid)
else:
    mid1 = Data[N//2-1]
    mid2 = Data[N//2]
    ans = min(diff(mid1),diff(mid2))

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
L = []
ans = 0
for i in range(N):
  L.append(A[i] - (i + 1))
L = sorted(L)
B = L[N // 2]
for i in range(N):
  ans += abs(A[i]-(B + i + 1))
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
An = np.array(list(map(int, input().split())))
Bn = np.array(list(range(1,N+1,1)))
Cn = An - Bn

ans = 0
b = int(round(np.median(Cn)))

for c in Cn:
    ans += abs(c - b)

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
A = list(map(int, input().split()))
B = list(range(1,N+1,1))

An = np.array(A)
Bn = np.array(list(range(1,N+1,1)))

Cn = An - Bn

ans = 0
b = int(round(np.median(Cn)))

for c in Cn:
    ans += abs(c - b)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from statistics import median_low
inputs = sys.stdin.readlines()

n = int(inputs[0])
A = list(map(int, inputs[1].split()))

B = list(map(lambda x: x[1]-x[0], enumerate(A, 1)))
b = median_low(B)
print(sum(map(lambda x: abs(x-b), B)))

Submission status: Accepted

Solution code:
import sys
from statistics import median_low
inputs = sys.stdin.readlines()

n = int(inputs[0])
A = list(map(int, inputs[1].split()))

B = list(map(lambda x: x[1]-x[0], enumerate(A, 1)))
b = median_low(B)
C = list(map(lambda x: abs(x-b), B))
print(sum(C))

Submission status: Accepted

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

B = [A[i]-i+1 for i in range(N)]
b = sorted(B)[N//2]

print(sum(abs(B[i]-b) for i in range(N)))

Submission status: Accepted

Solution code:
N = int(input().strip())
A = list(map(int, input().strip().split()))
bias = sorted([a-i for i, a in enumerate(A, 1)])
if N % 2 == 0:
    b = bias[N // 2 - 1]
else:
    b = bias[(N-1) // 2]
print(sum([abs(a - i - b) for i, a in enumerate(A, 1)]))

Submission status: Accepted

Solution code:
from statistics import median
import math

N = int(input())
A = list(map(int, input().split()))
A = [A[idx]-(idx+1) for idx in range(N)]

ans1 = 0
ans2 = 0
median_A = median(A)
median_floor_A = math.floor(median_A)
median_ceil_A = math.ceil(median(A))

for i in range(N):
    ans1 += abs(median_floor_A - A[i])
    ans2 += abs(median_ceil_A - A[i])
    
print(min(ans1,ans2))

Submission status: Accepted

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

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

mid = A[N // 2]
print(sum([abs(A[i] - mid) for i in range(N)]))

Submission status: Accepted

Solution code:
import sys
import statistics

N = int(input())
AAA = list(map(int, sys.stdin.readline().split()))

AAA_minus_i = [A - (i+1) for i, A in enumerate(AAA)]
median_AAA_minus_i = round(statistics.median(AAA_minus_i))

ans = sum(list(map(lambda x: abs(x-median_AAA_minus_i), AAA_minus_i)))

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

t = list(sorted(A[i] - (i + 1) for i in range(N)))
b = t[len(t) // 2]
print(sum(abs(A[i] - (b + i + 1)) for i in range(N)))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import statistics as st
import numpy as np

def test():
    ans = 0
    n = int(input())
    a = np.array(list(map(int,input().split())))
    i = np.array([i for i in range(1,n+1)])
    b = st.median(a-i)
    for k in range(n):
        ans += abs(a[k]-i[k]-b)
    print(int(ans))  


if __name__ == "__main__":
    test()

Submission status: Accepted

Solution code:
n = int(input())
A = sorted([int(val) - (i + 1) for i, val in zip(range(n), input().split())])

b = A[len(A)//2]
sad = 0
for i in range(n):
  sad += abs(A[i] - b)
print(sad)

Submission status: Accepted

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

Submission status: Accepted

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

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

A.sort()
b = A[n//2]

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

ans = sum(A)
print(ans)

Submission status: Accepted

Solution code:
import statistics

N = int(input())

A = list(map(int, input().split()))
c = 0

B = [A[i]-(i+1) for i in range(len(A))]
b = int(statistics.median(B))

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

print(c)

Submission status: Accepted

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

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

A.sort(reverse=True)


t=-A[N//2]
for i in range(N):
  A[i]+=t
print(sum([abs(x) for x in A]))

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
A = np.array([int(i) for i in input().split()])
A = np.sort(A - np.arange(N) - 1)
b = A[N//2]
print(np.sum(np.abs(A - b)))

Submission status: Accepted

Solution code:
def f(l, b):
    return sum(abs(x-b) for x in l)


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

xs = [x-i for i, x in enumerate(X, 1)]
if N % 2 != 0:
    b = sorted(xs)[N//2]
    print(f(xs, b))
else:
    b1 = sorted(xs)[N//2-1]
    b2 = sorted(xs)[N//2]
    print(min(f(xs, b1), f(xs, b2)))

Submission status: Accepted

Solution code:
import statistics
n=int(input())
A=list(map(int,input().split()))
B=sorted([j-(i+1) for i,j in enumerate(A)])
median=int(statistics.median(B))
count=0
for i,j in enumerate(A):
    count +=abs(j-(i+1)-median)
print(count)

Submission status: Accepted

Solution code:
import statistics

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

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

b = int(statistics.median(B))

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

print(sadness)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    A=map(int,input().split())
    B=[a-i for i,a in enumerate(A)]
    if n==1:
        print(0)
        return
    B.sort()
    f=lambda x:sum(abs(x-b) for b in B)
    ans=min(f(B[n//2]),f(B[n//2+1]))
    print(ans)
resolve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
A = [0] + list(map(int,input().split()))
#A_ = A[:(N+1)]

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

AA = sorted(A[1:N+1])
#print(AA)

if N % 2 == 0:
    b = AA[N//2 - 1]
else:
    b = AA[(N-1)//2]

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

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
A = [0] + list(map(int,input().split()))
A_ = A[:(N+1)]

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

AA = sorted(A_[1:])
#print(AA)

if N % 2 == 0:
    b = AA[N//2 - 1]
else:
    b = AA[(N-1)//2]

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

print(ans)

Submission status: Accepted

Solution code:
#import sys
#input = sys.stdin.readline

N = int(input())
A = [0] + list(map(int,input().split()))

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

AA = sorted(A[1:])
#print(AA)

if N % 2 == 0:
    b = AA[N//2 - 1]
else:
    b = AA[(N-1)//2]

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

print(ans)

Submission status: Accepted

Solution code:
import statistics
N = int(input())
A = list(map(int, input().split()))
B = []

for i in range(len(A)):
    B.append(A[i] - (i+1))

b = statistics.median(B)

ans = 0
for i in range(len(B)):
    ans += abs(B[i] - b)

print(int(ans))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A_ = [a-i-1 for i,a in enumerate(A)]

A_.sort()

b = A_[N//2]

print(sum([abs(ai-b) for ai in A_]))

Submission status: Accepted

Solution code:
n=int(input())
lists=list(map(int,input().split()))
uselists=[]
for _ in range(n):
    uselists.append(lists[_]-_-1)
uselist=sorted(uselists)
if n%2==0:
    num1=int(n/2-1)
    num2=int(n/2)
    numbers=min(uselist[num1],uselist[num2])
    
if n%2!=0:
    num1=int((n-1)/2)
    numbers=uselist[num1] 
ans=0
for x in range(n):
    ans+=abs(uselist[x]-numbers)
print(ans)

Submission status: Accepted

Solution code:
import math

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

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

B.sort()
if N % 2 == 1:
    b = B[(N-1) // 2]
else:
    b = (B[N // 2] + B[N // 2 - 1]) // 2

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

print(ans)

Submission status: Accepted

Solution code:
import statistics
n=int(input())
box=list(map(int,input().split()))
box_m=sorted(list(y-(x+1) for x,y in enumerate(box)))
median=int(statistics.median(box_m))
count=0
for x,y in enumerate(box):
    count +=abs(y-(median+x+1))
print(count)

Submission status: Accepted

Solution code:
import statistics
N = int(input())
A = [int(a)-(i+1) for i, a in enumerate(input().split())]
ans = float('inf')
medi = int(statistics.median(A))
for b in range(medi-1, medi+2):
  ans = min(ans, sum([abs(A[i]-b) for i in range(N)]))
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

B=sorted(A)
b=B[n//2]

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

Submission status: Accepted

Solution code:
# ABC102C - Linear Approximation (ARC100C)
def main():
    N, *A = map(int, open(0).read().split())
    B = [j - i for i, j in enumerate(A, 1)]
    B.sort()
    b = B[N // 2]
    ans = sum(abs(i - b) for i in B)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC102 C - Linear Approximation
n = int(input())
a = [int(x) for x in input().split()]
b = []
m = 0.0

for i in range(n):
    b.append(a[i]-i)

b.sort()

if n%2 == 0:
    m = (b[n//2] + b[(n//2)-1])//2
else:
    m = b[((n+1)//2)-1]
for i in range(n):
    b[i] = abs(b[i]-m)

print(int(sum(b)))

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
As = [int(item) - (i+1) for i, item in enumerate(input().split())]

b = int(np.median(As))

print(sum([abs(A-b) for A in As]))

Submission status: Accepted

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


def sad(A, b):
    return sum([abs(a - (b + i)) for a, i in zip(A, range(1, len(A) + 1))])

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

print(sad(A, B[(N - 1) // 2]))

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
for i in range(n):
  l[i]=l[i]-i-1
l=sorted(l)
if n%2==0:
  mid=(l[n//2-1]+l[n//2])//2
else:
  mid=l[(n-1)//2]
sum=0
for i in range(n):
  sum+=abs(l[i]-mid)
print(sum)

Submission status: Accepted

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

for i in range(n):
  B.append(a[i] - (i+1))
  
B = [0]+sorted(B)
b = B[int(n/2)]
b1 = B[int(n/2)+1]

tmp = 0
tmp1 = 0
for i in range(1,n+1):
  tmp += abs(B[i] - b)
  tmp1 +=abs(B[i] - b1)
  
print(min(tmp,tmp1))

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))
A=[A[i]-i-1 for i in range(n)]
A.sort()
b=A[n//2]
print(sum(abs(j-b) for j in A))

Submission status: Accepted

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

diff=[]

for i,x in enumerate(a,1):
    diff.append(x-i)
diff.sort()

n=n//2
b=diff[n]

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

print(ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = [int(val)-(i+1) for i,val in enumerate(input().split())]
    A.sort()
    if N&1:
        b = A[N//2]
        ans = sum([abs(a-b) for a in A])
    else:
        b1 = A[N//2]
        b2 = A[N//2 - 1]
        ans1 = [abs(a-b1) for a in A]
        ans2 = [abs(a-b2) for a in A]
        ans = min(sum(ans1),sum(ans2))
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

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

ans = 0
anslst = []
for i in range(N):
    anslst.append(a[i] - (i + 1))
anslst.sort()
tmp = int(statistics.median(anslst))
for i in range(N):
    ans += abs(a[i] - (tmp + i + 1))

print(ans)

Submission status: Accepted

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

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

a.sort()
med = [a[N//2-1],a[N//2]]
mina = 0
for i in range(N):
  mina += abs(a[i] - med[0])

minb = 0
for i in range(N):
  minb += abs(a[i] - med[1])

print(min(mina,minb))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline

def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = A.copy()
    for i in range(N):
        B[i] -= i+1
    B.sort()
    m = B[N//2]
    ans = 0
    for i,a in enumerate(A):
        ans += abs(a-(m+i+1))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#ABC102C
import numpy as np
n = int(input())
a = list(map(int,input().split()))
b = [0]*n
for i in range(n):
    b[i] = a[i]-(i+1)
ave = round(np.median(b))
ans = 0
for i in range(n):
    ans += abs(b[i]-ave)
print(int(ans))

Submission status: Accepted

Solution code:
from functools import reduce

N = int(input())
A = list(map(int,input().split()))
for i in range(N):
    A[i] = A[i]-(i+1)
A.sort()
b = A[len(A)//2]
A = list(map(lambda n:abs(n-b),A))
print(reduce(lambda a,b:a+b,A))

Submission status: Accepted

Solution code:
n = int(input())
arr = sorted([int(a)-i-1 for i, a in enumerate(input().split())])
b = arr[n//2]
res = sum((abs(i-b) for i in arr))
print(res)

Submission status: Accepted

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

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

if n % 2 == 1:
    idx = n // 2
    res = 0
    for ai in aa[:idx]:
        res += aa[idx] - ai
    for ai in aa[idx:]:
        res += ai - aa[idx]

else:
    idx_1 = n // 2 -1
    idx_2 = n // 2
    res_1 = 0
    for ai in aa[:idx_1]:
        res_1 += aa[idx_1] - ai
    for ai in aa[idx_1:]:
        res_1 += ai - aa[idx_1]
    res_2 = 0
    for ai in aa[:idx_2]:
        res_2 += aa[idx_2] - ai
    for ai in aa[idx_2:]:
        res_2 += ai - aa[idx_2]
    res = min(res_1, res_2)

print(res)

Submission status: Accepted

Solution code:
n = int(input())
ls = list(map(int, input().split()))
ls = sorted([x - i - 1 for i, x in enumerate(ls)])
m = ls[n // 2]
ls = [abs(x - m) for x in ls]
print(sum(ls))

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
B = []
for i in range(n):
    B += [A[i]-(i+1)]
B.sort()
b = B[len(B)//2]
C = list(map(lambda x: abs(x-b),B))
print(sum(C))

Submission status: Accepted

Solution code:
import numpy as np


#@profile
def solve(n, ax):
    substract_ax_from_i = []

    for i in range(n):
        substract_ax_from_i.append(ax[i]-i-1)
    substract_ax_from_i.sort()
    med = int(np.median(substract_ax_from_i))
    ans = sum(list(map(lambda x: abs(x-med), substract_ax_from_i)))

    return ans


if __name__ == '__main__':
    n = int(input())
    ax = list(map(int, input().split()))
    print(solve(n, ax))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import statistics
def resolve():
    n = int(input())
    aaa = list(map(int ,input().split()))
    l = [a-i-1 for i,a in enumerate(aaa)]
    median = statistics.median_low(l)
    print(sum([abs(k-median) for k in l]))
resolve()

Submission status: Accepted

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

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

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

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = sorted([a[i] - i - 1 for i in range(n)])
c = [i + (0 - b[0]) for i in b]

d = []
if n == 1:
    print(0)
else:
    if n % 2 == 1:
        d.append(0 - c[n//2])
    else:
        d.append(0 - c[n//2])
        d.append(0 - c[n//2 - 1])
        d.append(1 - c[n//2])
        d.append(-1 - c[n//2 - 1])

    ans = []
    for j in d:
        e = [i + j for i in c]
        ans.append(sum([abs(i) for i in e]))

    print(min(ans))

Submission status: Accepted

Solution code:
import statistics
n=int(input())
box=list(map(int,input().split()))
box_another=sorted(list(y-(x+1) for x,y in enumerate(box)))
median=int(statistics.median(box_another))
count=0
for x,y in enumerate(box):
    count +=abs(y-(x+1+median))
print(count)

Submission status: Accepted

Solution code:
import statistics

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

B = [A[i] - (i + 1) for i in range(N)]
b = int(statistics.median(B))
ans = 0

for i in B:
    ans += abs(i - b)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from statistics import median as m
n=int(input())
A=list(map(int,input().split()))
B=sorted([A[i]-i-1 for i in range(n)])
mb=m(B)
print(int(sum([abs(b-mb) for b in B])))