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:
# def decrement(a):
#    return a-1


N = int(input())
A = [int(i) for i in input().split()]
for i in range(len(A)):
    A[i] -= i+1
# print(A)
average_A = sum(A) / N
int_average = round(average_A)
#print(average_A, int_average)
"""
print([a for a in A])  # if a > 0])
while len([a for a in A if a > 0]) > N // 2:
    A = list(map(decrement, A))
    print(A)
# print(A)
print(sum([abs(a) for a in A]))
"""
ans = [sum(list(map(lambda x: abs(x-int_average+1), A)))
       for i in range(-10, 10)]
print(min(ans))

Submission status: Wrong Answer

Solution code:
input = open(0).read

N, *An = map(int, input().split())


def main():
    for i in range(N):
        An[i] = An[i] - i - 1

    ans = 0

    for i in range(N):
        ans += abs(An[i] - An[N // 2])

    print(ans)
    return


main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from statistics import median
n = int(input())
a = list(map(int,input().split()))
A = [a[i] - i - 1  for i in range(n)]
med = median(A)
ans = sum([abs(A[i]-med) for i in range(n)])
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int,input().split()))
A = [a[i] - i - 1  for i in range(n)]
ave = sum(A) // n
ans = sum([abs(A[i]-ave) for i in range(n)])
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter


def solve(string):
    n, *a = map(int, string.split())
    a = [_a - i - 1 for i, _a in enumerate(a)]
    ans = 2 * n * 10**9
    counts = Counter(a)
    max_count = max(counts.values())
    if max_count > 1:
        search = [k for k, v in counts.items() if v == max_count]
        for s in search:
            ans = min(ans, sum([abs(_a - s) for _a in a]))
    mean = sum(a) // n
    for i in range(-1, 2):
        ans = min(ans, sum([abs(_a - mean - i) for _a in a]))
    return str(ans)


if __name__ == '__main__':
    print(solve("\n".join([input(), input()])))

Submission status: Wrong Answer

Solution code:
from collections import Counter


def solve(string):
    n, *a = map(int, string.split())
    a = [_a - i - 1 for i, _a in enumerate(a)]
    counts = Counter(a)
    max_count = max(counts.values())
    ans = 2 * n * 10**9
    if max_count > 1:
        search = [k for k, v in counts.items() if v == max_count]
        for s in search:
            ans = min(ans, sum([abs(_a - s) for _a in a]))
    mean = sum(a) // n
    for i in range(2):
        ans = min(ans, sum([abs(_a - mean - i) for _a in a]))
    return str(ans)


if __name__ == '__main__':
    print(solve("\n".join([input(), input()])))

Submission status: Wrong Answer

Solution code:
from collections import Counter


def solve(string):
    n, *a = map(int, string.split())
    a = [_a - i - 1 for i, _a in enumerate(a)]
    counts = Counter(a)
    max_count = max(counts.values())
    search = [k for k, v in counts.items() if v == max_count]
    ans = 2 * n * 10**9
    for s in search:
        ans = min(ans, sum([abs(_a - s) for _a in a]))
    mean = sum(a) // n
    for i in range(2):
        ans = min(ans, sum([abs(_a - mean - i) for _a in a]))
    return str(ans)


if __name__ == '__main__':
    print(solve("\n".join([input(), input()])))

Submission status: Wrong Answer

Solution code:
def solve(string):
    n, *a = map(int, string.split())
    a = [_a - i - 1 for i, _a in enumerate(a)]
    mean = sum(a) // n
    return str(
        min(
            sum([abs(_a - mean) for _a in a]), sum([abs(_a - mean - 1) for _a in a]),
            sum([abs(_a - mean + 1) for _a in a])))


if __name__ == '__main__':
    print(solve("\n".join([input(), input()])))

Submission status: Wrong Answer

Solution code:
def solve(string):
    n, *a = map(int, string.split())
    a = [_a - i - 1 for i, _a in enumerate(a)]
    mean = sum(a) // n
    return str(min(sum([abs(_a - mean) for _a in a]), sum([abs(_a - mean - 1) for _a in a])))


if __name__ == '__main__':
    print(solve("\n".join([input(), input()])))

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
lst = np.array(list(map(int, input().split() )))
for i in range(len(lst)):
    lst[i] = lst[i] - (i +1)
#print("lst:",lst)
b = int(np.round(abs(np.mean(lst) )  ) )
if np.mean(lst) < 0 :
    b = b * (-1)
    if np.mean(lst) < b:
        b = b -1
#print("np.mean(lst):",np.mean(lst))
#print("b:",b)
count = 0
for A in lst:
    count += abs(A -b)
print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
tmp = [A[i-1]-i for i in range(1,N+1)]
B = tmp[N//2]
print(sum([abs(t-B) for t in tmp]))

Submission status: Wrong Answer

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

b = sum(a_) // N
b_ = b + 1
s = [abs(n - b) for i, n in enumerate(a_)]
s_ = [abs(n - b_) for i, n in enumerate(a_)]

print(min(sum(s), sum(s_)))

Submission status: Wrong Answer

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

b = sum(a_) // N

s = [abs(n - b) for i, n in enumerate(a_)]
print(sum(s))

Submission status: Wrong Answer

Solution code:
import bisect
N = int(input())
A = list(map(int, input().split()))
A = [A[i] - i - 1 for i in range(N)]
A.sort()
wa = sum(list(map(abs, A)))
x = N - bisect.bisect_right(A, 0)
y = bisect.bisect_left(A,0)
z = bisect.bisect_right(A, 0) - bisect.bisect_left(A, 0)
if x == y:
    print(wa)
elif x > y:
    r = bisect.bisect_right(A,0)
    while x > y + z:
        if r > N-1:
            break
        wa = min(wa, wa - x + z + y)
        y += z
        z = bisect.bisect_right(A, A[r]) - bisect.bisect_left(A, A[r])
        x -= z
        r = bisect.bisect_right(A,A[r])
    print(wa)
else:
    r = bisect.bisect_left(A,0) - 1
    while y > z + z:
        if r < 0:
            break
        wa = min(wa, wa - y + z + x)
        x += z
        z = bisect.bisect_right(A, A[r]) - bisect.bisect_left(A, A[r])
        y -= z
        r = bisect.bisect_left(A, A[r]) - 1
    print(wa)

Submission status: Wrong Answer

Solution code:
import statistics

N=int(input())
L=list(map(int,input().split()))
for i in range(N):
  L[i]=L[i]-(i+1)
m=statistics.median(L)
ans=0
for i in range(N):
  ans+=abs(L[i]-m) 
print(ans)

Submission status: Wrong Answer

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

if(N%2 == 0):
  print(A[N//2-1]*N)
else:
  print(sum(A)-A[N//2]*N)

Submission status: Wrong Answer

Solution code:
N=int(input())
L=list(map(int,input().split()))
for i in range(N):
  L[i]=L[i]-(i+1)
m=sum(L)//N
ans=[]

for j in range(-5,6):
  tmp=0
  for i in range(N):
    tmp+=abs(L[i]-(m+j))
  ans.append(tmp)
  
print(min(ans))

Submission status: Wrong Answer

Solution code:
# /user/bin/python
# -*- coding: utf-8 -*-
import sys 


n = int(input())
a = list(map(int, sys.stdin.readline().rstrip().split()))
for i in range(n):
  a[i] = a[i]-i-1
b = sum(a) // n

ans1, ans2, ans3 = 0, 0, 0

for i in range(n):
  ans1 += abs(a[i]-b)
  ans2 += abs(a[i]-b-1)
  ans3 += abs(a[i]-b+1)

print(min(ans1, ans2, ans3))

Submission status: Wrong Answer

Solution code:
# /user/bin/python
# -*- coding: utf-8 -*-
import sys 


n = int(input())
a = list(map(int, sys.stdin.readline().rstrip().split()))
for i in range(n):
  a[i] = a[i]-i-1
b = sum(a) // n

ans1, ans2 = 0, 0

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

print(min(ans1, ans2))

Submission status: Wrong Answer

Solution code:
# /user/bin/python
# -*- coding: utf-8 -*-
import sys 


n = int(input())
a = list(map(int, sys.stdin.readline().rstrip().split()))

for i in range(n):
  a[i] = a[i]-i-1
a_sum = sum(a)
b = a_sum // n

a1 = [0] * n
a2 = [0] * n
for i in range(n):
  a1[i] = abs(a[i] - b)
  a2[i] = abs(a[i] - b-1)
print(min(sum(a1), sum(a2)))

Submission status: Wrong Answer

Solution code:
# /user/bin/python
# -*- coding: utf-8 -*-
import sys 


n = int(input())
a = list(map(int, sys.stdin.readline().rstrip().split()))

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

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

print(sum(a))

Submission status: Wrong Answer

Solution code:
import math
input()
A = list(map(int, input().split()))
A = [a - n - 1 for n, a in enumerate(A)]
avg = sum(A)/len(A)
avg1 = math.ceil(avg)
avg2 = math.floor(avg)
print(min(sum([abs(a - avg1) for a in A]), sum([abs(a - avg2) for a in A])))

Submission status: Wrong Answer

Solution code:
input()
A = list(map(int, input().split()))
A = [a - n - 1 for n, a in enumerate(A)]
avg = sum(A)//len(A)
print(sum([abs(a - avg) for a in A]))

Submission status: Wrong Answer

Solution code:
import math

n = int(input())
a = list(map(int, input().split()))
b = []
answer = 0

for i in range(n):
	b.append(abs(a[i]-(i+1)))
b.sort()
mid = b[int(n/2)]

for i in range(n):
	answer = answer + abs(b[i]-mid)
	

print(answer)

Submission status: Wrong Answer

Solution code:
import fractions
import statistics
import operator
from functools import reduce
N = int(input())
a_list = list(map(int, input().split(' ')))
median = statistics.median(a_list)
bias = (N+1) / 2
b = median - bias
#print(bias)
#print(median)
#print(int(sum([abs(a - (median)) for i,a in enumerate(a_list, start=1)])))
#print(int(sum([abs(a - (b + i)) for i,a in enumerate(a_list, start=1)])))
print(int(abs(sum([abs(a - i) for i,a in enumerate(a_list, start=1)]) + b*N)))

Submission status: Wrong Answer

Solution code:
import fractions
import statistics
import operator
from functools import reduce
N = int(input())
a_list = list(map(int, input().split(' ')))
median = statistics.median(a_list)
bias = (N+1) / 2
b = median - bias
print(sum([abs(a - (b + i)) for i,a in enumerate(a_list, start=1)]))

Submission status: Wrong Answer

Solution code:
import fractions
import statistics
import operator
from functools import reduce
N = int(input())
a_list = list(map(int, input().split(' ')))
median = statistics.median(a_list)
bias = (N+1) / 2
b = median - bias
print(int(sum([abs(a - (b + i)) for i,a in enumerate(a_list, start=1)])))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on 2019/2/
Solved on 2019/2/
@author: shinjisu
"""


# ABC 102 C Linear Approximation
import statistics


def getInt(): return int(input())


def getIntList(): return [int(x) for x in input().split()]


def zeros(n): return [0]*n


def getIntLines(n): return [int(input()) for i in range(n)]


def getIntMat(n):
    mat = []
    for i in range(n):
        mat.append(getIntList())
    return mat


def zeros2(n, m): return [zeros(m)]*n


ALPHABET = [chr(i+ord('a')) for i in range(26)]
DIGIT = [chr(i+ord('0')) for i in range(10)]
N1097 = 10**9 + 7
INF = 10**12


def dmp(x, cmt=''):
    global debug
    if debug:
        if cmt != '':
            print(cmt, ':  ', end='')
        print(x)
    return x


def probC():
    N = getInt()
    A = getIntList()
    dmp((N, A))
    a = [A[i]-i-1 for i in range(N)]
    dmp(a, 'a')
    m = int(statistics.mean(a))
    dmp(m, 'mean')
    s = int(statistics.pstdev(a)) + 2
    dmp(s, 'std dev')
    minSum = sum([abs(a[j]) for j in range(N)])
    dmp(minSum, 'minSum')
    for i in range(1, s):
        aSum = sum([abs(a[j]-m+i) for j in range(N)])
        dmp((aSum, -m+i), 'aSum, -m+i')
        minSum = min(minSum, aSum)
        aSum = sum([abs(a[j]-m-i) for j in range(N)])
        minSum = min(minSum, aSum)
        dmp((aSum, -m-i), 'aSum, -m-i')
        dmp(minSum, 'minSum')
    dmp(minSum, 'minSum')
    return minSum


debug = False  # True False
ans = probC()
print(ans)
#for row in ans:
#    print(row)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
A=[e-i for i,e in enumerate(A,1)]
n=int(sum(A)/N)
t=0
t_min=10**9
for m in range(n-1,n+1):
  t=0
  for a in A:
    t+=abs(a-n)
  t_min=min(t,t_min)
print(int(t))

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
A=[e-i for i,e in enumerate(A,1)]
n=sum(A)/N
t=0
for a in A:
  t+=abs(a-n)
print(int(t))

Submission status: Wrong Answer

Solution code:
n=int(input())
l=list(map(int,input().split()))
if ' '.join([str(x) for x in l])=='2 2 3 5 5':
  exit()
s=[0]*2
f='first'
f2='front'
b=1
ans=0
for i in range(n):
  s[0]+=abs(l[i]-(i+1))
while True:
  if f2=='front':
    for i in range(n):
      s[1]+=abs(l[i]-(b+i+1))
    if s[0]<s[1]:
      if f=='first':
        s[1]=0
        f='not first'
        f2='back'
      else:
        ans=s[0]
        break
    else:
      s[0]=s[1]
      s[1]=0
      b+=1
  else:
    for i in range(n):
      s[1]+=abs(l[i]-(-b+i+1))
    if s[0]<s[1]:
      ans=s[0]
      break
    else:
      s[0]=s[1]
      s[1]=0
      b+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
N=int(input())
A=list(map(int,input().split()))
for i in range(N):
    A[i]=A[i]-(i+1)
c=collections.Counter(A)
b=c.most_common()[0][0]
A_abs=[abs(i-b) for i in A]
value=[]
value.append(sum(A_abs))
cp=0
f=1
while f==1 and cp<len(c)-1:
    if c.most_common()[cp][1]==c.most_common()[cp+1][1]:
        cp+=1
        b=c.most_common()[cp][0]
        A_abs=[abs(i-b) for i in A]
        value.append(sum(A_abs))
        continue
    f=0
print(min(value))

Submission status: Wrong Answer

Solution code:
import statistics
N = int(input())

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

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

med = statistics.median(a)

for i in range(N):
  a[i] = abs(a[i] - med)

print(sum(a))

Submission status: Wrong Answer

Solution code:
n,*a=map(int,open(0).read().split());print(min(sum(abs(a[s]-(b+s+1))for s in range(n))for b in range(n)))

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter

def main():
  input = sys.stdin.readline
  N = int(input())
  A = list(map(int, input().split()))
  B = []
  for i in range(N):
    B.append(A[i] - (i+1))
  C = Counter(B).most_common()
  ans = abs(C[0][0])
  for c in C[1:]:
    ans += abs(c[0] * c[1])
  
  print(ans)


if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
import sys

def main():
  input = sys.stdin.readline
  N = int(input())
  A = list(map(int, input().split()))
  ans = 0
  for i in range(N):
    ans += abs(A[i] - (i+1))
  print(ans)


if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
n=int(input())

X=list(map(int,input().split()))
Y=[]
for i in range(n):
    Y.append(X[i]-(i+1))
    
x=int(sum(Y)/n)
y=x+1
z=x-1
cn1=0
cn2=0
cn3=0
for i in range(n):
    cn1+=abs(Y[i]-x)
    cn2+=abs(Y[i]-y)
    cn3+=abs(Y[i]-z)
    
print(min(cn1,cn2,cn3))

Submission status: Wrong Answer

Solution code:
import statistics
n=int(input())
L=list(map(int, input().split()))
LL=[L[i]-i-1 for i in range(n)]
m=statistics.median(LL)
LLL=[abs(LL[i]-m) for i in range(n)]
print(sum(LLL))

Submission status: Wrong Answer

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

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)]

a = math.floor(sum(B) / N)
b = math.ceil(sum(B) / N)

C = [abs(B[i] - a) for i in range(N)]
D = [abs(B[i] - b) for i in range(N)]

print(min(sum(C), sum(D)))

Submission status: Wrong Answer

Solution code:
N = int(input())

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

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

ave = round(sum(B) / N)

C = [abs(B[i] - ave) for i in range(N)]

print(sum(C))

Submission status: Wrong Answer

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

p = []
m = []
for i in range(n):
    a[i] -= i+1
    if a[i] > 0:
        p += [a[i]]
    elif a[i] < 0:
        m += [a[i]]

if sum(p) == abs(sum(m)):
    print(sum([abs(i) for i in a]))
    exit()

if sum(p) > abs(sum(m)):
    for i in range(6):
        pre = sum([abs(j) for j in a])
        for j in range(n):
            a[j] -= 1
        total = sum([abs(j) for j in a])
        
        if total >= pre:
            print(pre)
            exit()
        pre = total
else:
    for i in range(6):
        pre = sum([abs(j) for j in a])
        for j in range(n):
            a[j] += 1
        total = sum([abs(j) for j in a])
        
        if total >= pre:
            print(pre)
            exit()
        pre = total

Submission status: Wrong Answer

Solution code:
import math


def solve(N, As):
    As = [a - (i + 1) for i, a in enumerate(As)]
    b1 = math.floor(sum(As) / N)
    b2 = math.ceil(sum(As) / N)
    return min(sum(abs(a - b1) for a in As),
               sum(abs(a - b2) for a in As)
               )


if __name__ == "__main__":
    N = int(input())
    As = list(map(int, input().split(" ")))
    print(solve(N, As))

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

import math
b = math.floor(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()))
def f(x):
    sum = 0
    i = 0
    for a in A:
        i += 1
        sum += abs(a - (x + i))
    return sum
mean = sum(A)/N
b = round(mean - (N/2+0.5))
if b < 0:
    b -= 1
print(f(b))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
def f(x):
    sum = 0
    i = 0
    for a in A:
        i += 1
        sum += abs(a - (x + i))
    return sum
mean = sum(A)/N
b = int(mean - (N/2+0.5))
if b < 0:
    b -= 1
print(f(b))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
total=0
for i in range(N):
    A[i]=A[i]-(i+1)
    total+=A[i]
tmp=total//N
tmp1=tmp
tmp2=tmp+1
tmp3=tmp-1
ans1=0
ans2=0
ans3=0
for i in range(N):
    ans1+=abs(A[i]-tmp1)
for i in range(N):
    ans2+=abs(A[i]-tmp2)
for i in range(N):
    ans3+=abs(A[i]-tmp3)
print(min(ans1,ans2,ans3))

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
total=0
for i in range(N):
    A[i]=A[i]-(i+1)
    total+=A[i]
tmp=total//N
tmp1=tmp
if tmp>=0:
    tmp2=tmp+1
else:
    tmp2=tmp-1
ans1=0
ans2=0
for i in range(N):
    ans1+=abs(A[i]-tmp1)
for i in range(N):
    ans2+=abs(A[i]-tmp2)
print(min(ans1,ans2))

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    ans = sum([abs(a - (0 + j + 1)) for j, a in enumerate(A)])
    for b in A:
        ans = min(ans, sum([abs(a - (b + j + 1)) for j, a in enumerate(A)]))
        ans = min(ans, sum([abs(a - (-b + j + 1)) for j, a in enumerate(A)]))
    print(ans)


main()

Submission status: Wrong Answer

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

A = []
for i,a_ in enumerate(A_):
    A.append(a_-i-1)

d = {}
for a in A:
    if a in d.keys():
        d[a] += 1
    else:
        d[a] = 1

count = 0
for d_ in sorted(d.items()):
    if count >= len(d)/2:
        break
    count += d_[1]
    d_prev = d_[0]

b1 = d_prev
b2 = d_[0]

ans1 = 0
ans2 = 0
for a in A:
    ans1 += abs(a-b1)
    ans2 += abs(a-b2)

print(min(ans1,ans2))

Submission status: Wrong Answer

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

A = []
for i,a_ in enumerate(A_):
    A.append(a_-i-1)

d = {}
for a in A:
    if a in d.keys():
        d[a] += 1
    else:
        d[a] = 1

count = 0
for d_ in sorted(d.items()):
    if count >= len(d)/2:
        break
    count += d_[1]
    d_prev = d_[0]

b1 = d_prev
b2 = d_[0]
print(b1,b2)

ans1 = 0
ans2 = 0
for a in A:
    ans1 += abs(a-b1)
    ans2 += abs(a-b2)

print(min(ans1,ans2))

Submission status: Wrong Answer

Solution code:
import math

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

A = []
for i,a_ in enumerate(A_):
    A.append(a_-i-1)

d = {}
for a in A:
    if a in d.keys():
        d[a] += 1
    else:
        d[a] = 1

d_max = max(d.values())
d_max_list = []
for k,v in d.items():
    if v == d_max:
        d_max_list.append(k)
b = int(sum(d_max_list)/len(d_max_list))

ans = 0
for a in A:
    ans += abs(a-b)

print(ans)

Submission status: Wrong Answer

Solution code:
import math

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

A = []
for i,a in enumerate(A_):
    A.append(a-i-1)

b1 = math.ceil(sum(A)/len(A))
b2 = math.floor(sum(A)/len(A))

ans1 = 0
ans2 = 0
for a in A:
    ans1 += abs(a-b1)
    ans2 += abs(a-b2)

print(min(ans1,ans2))

Submission status: Wrong Answer

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

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

M = sum(A) // len(A)
R = []

for m in [M-1, M, M+1]:
    R.append(sum([abs(a - m) for a in A]))

print(min(R))

Submission status: Wrong Answer

Solution code:
import sys
from functools import reduce
input = sys.stdin.readline

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

Submission status: Wrong Answer

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

for i in range(1, n + 1):
    B.append(A[i - 1] - i)
    
ans = 0
for i in range(1, n + 1):
    ans += abs(A[i - 1] - (B[n // 2] + i))
    
print(ans)

Submission status: Wrong Answer

Solution code:
from statistics import median

N = int(input())
A = list(map(int,input().split()))
Asort = sorted([A[i]-i-1 for i in range(N)])
# print(Asort)

b_tmp = int(median(Asort))
# print(b_tmp)
minA = 10**9
for b in range(b_tmp-3,b_tmp+3):
    submin = [abs(A[i]-b-i-1) for i in range(N)]
    # print(submin)
    minA = min(sum(submin),minA)

print(minA)

Submission status: Wrong Answer

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

if N%2 == 0:
    b_tmp = Asort[N//2]
else:
    b_tmp = (Asort[N//2-1] + Asort[N//2])// 2
# print(b_tmp)
minA = 10**9
for b in range(b_tmp-3,b_tmp+3):
    submin = [abs(A[i]-b-i-1) for i in range(N)]
    # print(submin)
    minA = min(sum(submin),minA)

print(minA)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
Asort = sorted([A[i]-i-1 for i in range(N)])
# minA = 10**9
#
# for b in range(min(A)-10,max(A)+N):
#     submin = [abs(A[i]-b-i-1) for i in range(N)]
#     # print(submin)
#     minA = min(sum(submin),minA)

b_tmp = Asort[N//2]
# print(b_tmp)
minA = 10**9

for b in range(b_tmp-10,b_tmp+10):
    submin = [abs(A[i]-b-i-1) for i in range(N)]
    # print(submin)
    minA = min(sum(submin),minA)

print(minA)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
Asort = sorted([A[i]-i-1 for i in range(N)])
# minA = 10**9
#
# for b in range(min(A)-10,max(A)+N):
#     submin = [abs(A[i]-b-i-1) for i in range(N)]
#     # print(submin)
#     minA = min(sum(submin),minA)

b_tmp = Asort[N//2]
# print(b_tmp)
minA = 10**9

for b in range(b_tmp-1,b_tmp+2):
    submin = [abs(A[i]-b-i-1) for i in range(N)]
    # print(submin)
    minA = min(sum(submin),minA)

print(minA)

Submission status: Wrong Answer

Solution code:
from statistics import mean

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

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

ave=round(mean(a))
ans1=0
ans2=0
ans3=0
ans4=0
ans5=5

for i in range(n):
  ans1 += abs(a[i]-ave-2)
  ans2 += abs(a[i]-ave-1)
  ans3 += abs(a[i]-ave)
  ans4 += abs(a[i]-ave+1)
  ans5 += abs(a[i]-ave+2)
  
  
print(min(ans1,ans2,ans3,ans4,ans5))

Submission status: Wrong Answer

Solution code:
from statistics import mean

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

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

ave=round(mean(a))
ans1=0
ans2=0
ans3=0

for i in range(n):
  ans1 += abs(a[i]-ave-1)
  ans2 += abs(a[i]-ave)
  ans3 += abs(a[i]-ave+1)
  
print(min(ans1,ans2,ans3))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
temp = [a-(i+1) for i, a in enumerate(A)]
mean = sum(temp)/N
cand_a = int(mean)
cand_b = cand_a + 1 if mean >= 0 else cand_a - 1

print(min(sum([abs(t-cand_a) for t in temp]), sum([abs(t-cand_b) for t in temp])))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
temp = [a-(i+1) for i, a in enumerate(A)]
mean = sum(temp)/N
cand_a = int(mean)
cand_b = cand_a + 1

print(min(sum([abs(t-cand_a) for t in temp]), sum([abs(t-cand_b) for t in temp])))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
for i in range(N):
    A[i] -= (i+1)
num1 = sum(A) // N

a = [abs(i) for i in A]
A1 = [abs(i - num1) for i in A]
A2 = [abs(i - (num1+1)) for i in A]
A3 = [abs(i - (num1-1)) for i in A]
A4 = [abs(i - (num1-2)) for i in A]
A5 = [abs(i - (num1+2)) for i in A]

print(min(sum(a), sum(A1), sum(A2), sum(A3), sum(A4), sum(A5)))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
for i in range(N):
    A[i] -= (i+1)
num1 = sum(A) // N

A1 = [abs(i - num1) for i in A]
A2 = [abs(i - (num1+1)) for i in A]
A3 = [abs(i - (num1-1)) for i in A]
A4 = [abs(i - (num1-2)) for i in A]
A5 = [abs(i - (num1+2)) for i in A]

print(min(sum(A1), sum(A2), sum(A3), sum(A4), sum(A5)))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
for i in range(N):
    A[i] -= (i+1)
num1 = sum(A) // N

A1 = [abs(i - num1) for i in A]
A2 = [abs(i - (num1+1)) for i in A]
A3 = [abs(i - (num1-1)) for i in A]

print(min(sum(A1), sum(A2), sum(A3)))

Submission status: Wrong Answer

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

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

sad0 = getSadness(A,0)
sad1 = getSadness(A,1)

min = min(sad0,sad1)
new = min

i=1
while True:
    if sad0<sad1:
        new = getSadness(A,0-i)
    else:
        new = getSadness(A,i)
    if new<min:
        min = new
    else:
        break
    i += 1

print(min)

Submission status: Wrong Answer

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


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

ave = sum(A)//len(A)

for x in range(N):
    A[x] = abs(A[x] - ave)

ans = min(sum(A),sum(A) + N )

print(ans)

Submission status: Wrong Answer

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

for i in range(n):
    B.append(A[i] - i)
    
mid = B[len(B)//2]

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

Submission status: Wrong Answer

Solution code:

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

a_list = sorted(a_list)
if n%2 != 0:
    median = a_list[int((n-1)/2)]
else:
    median = (a_list[int((n+1)/2)]+a_list[int((n-1)/2)])/2

sad = 0
for a in a_list:
    sad += abs(a - median)
print(sad)

Submission status: Wrong Answer

Solution code:
n = int(input())
A_list = list(map(int, input().split()))
for i in range(n):
    A_list[i] -= i
A_list.sort()
A_cum = [0] * n
for i in range(n):
    if i == 0:
        A_cum[0] = A_list[0]
    else:
        A_cum[i] = A_cum[i-1] + A_list[i]
def findinfindex(sortedlist, key, l, r):
    if r - l <= 0:
        return l
    m = (l+r+1)//2
    if sortedlist[m] > key:
        return findinfindex(sortedlist, key, l, m-1)
    else:
        return findinfindex(sortedlist, key, m, r)
sadmin = 10000000000
for b in range(A_list[0],A_list[n-1]+1):
    lastminus = findinfindex(A_list, b, 0, n-1)
    sadness = (2*lastminus - n + 2)*b - 2*A_cum[lastminus] + A_cum[n-1]
    if sadness < sadmin:
        sadmin = sadness
    else:
        break
print(sadmin)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
import collections

def calc_score(key):
    return sum([abs(b - key) for b in bList])

def calc_center():
    ans = 0
    for pair in scList:
        ans += pair[0]*pair[1]
    ans = ans / N
    return ans

N = int(input().strip())
aList = list(map(int, input().strip().split(" ")))

bList = [a - i - 1 for i,a in enumerate(aList)]
cList = collections.Counter(bList)
scList = cList.most_common()

ans = 100000000
for c in scList[:100]:
    ans = min(ans, calc_score(c[0]))
print(ans)

Submission status: Wrong Answer

Solution code:
import collections

def calc_score(key):
    return sum([abs(b - key) for b in bList])

def calc_center():
    ans = 0
    for pair in scList:
        ans += pair[0]*pair[1]
    ans = ans / N
    return ans

N = int(input().strip())
aList = list(map(int, input().strip().split(" ")))

bList = [a - i - 1 for i,a in enumerate(aList)]
cList = collections.Counter(bList)
scList = cList.most_common()

center = calc_center()
ans = min(calc_score(int(center)), calc_score(int(center) + 1))
ans = min(ans, calc_score(int(center) - 1))
print(ans)

Submission status: Wrong Answer

Solution code:
import collections

def calc_score(key):
    return sum([abs(b - key) for b in bList])

def calc_center():
    ans = 0
    for pair in scList:
        ans += pair[0]*pair[1]
    ans = ans / N
    return ans

N = int(input().strip())
aList = list(map(int, input().strip().split(" ")))

bList = [a - i - 1 for i,a in enumerate(aList)]
cList = collections.Counter(bList)

scList = cList.most_common()
    
center = calc_center()
print(int(min(calc_score(int(center)), calc_score(int(center)+1))))