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:
# -*- coding: utf-8 -*-
# モジュールのインポート
import itertools


def get_input() -> tuple:
    """
    標準入力を取得する.

    Returns:\n
        tuple: 標準入力
    """
    N = int(input())
    A = list(map(int, input().split()))

    return N, A


def main(A: list) -> None:
    """
    メイン処理.

    Args:\n
        A (list): 整数列(1 <= A_i <= 10^9)
    """
    # 求解処理
    ans = 0
    for A_i, A_j in itertools.combinations(A, r=2):
        ans = max(ans, abs(A_i - A_j))

    # 結果出力
    print(ans)


if __name__ == "__main__":
    # 標準入力を取得
    N, A = get_input()

    # メイン処理
    main(A)

Submission status: Wrong Answer

Solution code:
n=int(input())
alist=list(map(int, input().split()))
blist=[]
for i in range(n):
  blist.append(alist[i]-i-1)
blist.sort()
if n%2==1:
  cnt=0
  for i in range(n):
    cnt+=abs(blist[i]-blist[(i+1)//2])
  print(cnt)
else:
  cnt=0
  num=(blist[i//2]+blist[i//2+1])//2
  for i in range(n):
    cnt+=abs(blist[i]-num)
  print(cnt)

Submission status: Wrong Answer

Solution code:
n=int(input())
alist=list(map(int, input().split()))
blist=[]
for i in range(n):
  blist.append(alist[i]-i-1)
blist.sort()
if n%2==1:
  cnt=0
  for i in range(n):
    cnt+=abs(blist[i]-blist[(i+1)//2])
  print(cnt)
else:
  cnt=0
  num=(blist[i//2]+blist[i//2+1])//2
  for i in range(n):
    cnt+=abs(blist[i]-num)
  cnt2=0
  num2=(blist[i//2]+blist[i//2+1])//2+1
  for i in range(n):
    cnt2+=abs(blist[i]-num2)
  print(cnt,cnt2)

Submission status: Wrong Answer

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

res = 10 ** 9
for i in range(1000):
  c = 0
  for j in range(n):
    c += abs(a[j] - (i + j + 1))
  res = min(res,c)

print(res)

Submission status: Wrong Answer

Solution code:
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==0:
  a=N/2
  b=int((B[int(a)]+B[int(a-1)])/2)
else:
  a=(N+1)/2
  b=B[int(a-1)]
for i in range(N):
  B[N-1]=abs(B[N-1]-b)
print(sum(B))

Submission status: Wrong Answer

Solution code:
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==0:
  a=N/2
else:
  a=(N+1)/2
b=B[int(a-1)]
for i in range(N):
  B[N-1]=abs(B[N-1]-b)
print(sum(B))

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

s = sum(A)
t1 = s // N
t2 = t1 + 1
t3 = t1 - 1

ans1 = 0
ans2 = 0
ans3 = 0

for i in range(N):
    ans1 += abs(A[i] - t1)
    ans2 += abs(A[i] - t2)
    ans3 += abs(A[i] - t3)

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] = A[i] - i - 1

s = sum(A)
t1 = s // N
t2 = t1 + 1

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

print(min(ans1, ans2))

Submission status: Wrong Answer

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

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

s = sum(A)
t1 = s // N
t2 = t1 + 1

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

print(min(ans1, ans2))

Submission status: Wrong Answer

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

ans=0
for i in range(n):
  ans+=a[i]-(i+1)
  
b=ans//n
b1=ans/n

if b<0:
  c=b-1
else:
  c=b+1
  
if abs(b1-b)>=abs(b1-c):
  mid=c
else:
  mid=b
  
ans1=0

for j in range(n):
  ans1+=abs(a[j]-mid-(j+1))
  
print(ans1)

Submission status: Wrong Answer

Solution code:
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
N = int(input())
lsA = [0]+list(map(int,input().split()))
lsA2 = [int(lsA[i]) - i for i in range(1,N+1)]
ave = sum(lsA2)/N
b = Decimal(str(ave)).quantize(Decimal('0'), rounding=ROUND_HALF_UP)
ans = 0
for i in range(N):
    ans += abs(lsA2[i]-b)
print(ans)

Submission status: Wrong Answer

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

diff = [0] * n
for i in range(n):
    d = a[i] - (i + 1)
    diff[i] = d
        
x = sum(diff) // n
y = x + 1

ans = [0] * 2
for i in range(n):
    ans[0] += abs(diff[i] - x)
    ans[1] += abs(diff[i] - y)
    
print(min(ans))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
ls = list(map(int,input().split()))
bs = [ls[i]-i-1 for i in range(n)]
bs.sort()
#print(bs)
if n %2 ==0:
    a = round(n/2)
    #print(a)
    can = [bs[a],bs[a-1],math.floor((bs[a] +bs[a-1])/2),math.ceil((bs[a] +bs[a-1])/2)]
elif n ==1:
    can = [bs[0],bs[0]]
else:
    a = math.floor(n/2)
    #print(a)
    can = [bs[a+1],bs[a-1],bs[a]]

#print(can)
result = 10**10
for k in can:
    ans =0
    for kn in bs:
        ans += abs(kn-k)
    #print(ans)
    result = min(result, ans)
    
print(result)

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
ls = list(map(int,input().split()))
bs = [ls[i]-i-1 for i in range(n)]
bs.sort()
print(bs)
if n %2 ==0:
    a = round(n/2)
    #print(a)
    can = [bs[a],bs[a-1]]
elif n ==1:
    can = [bs[0],bs[0]]
else:
    a = math.floor(n/2)
    #print(a)
    can = [bs[a+1],bs[a-1]]

#print(can)
result = 10**10
for k in range(can[1],can[0]+1,1):
    ans =0
    for kn in bs:
        ans += abs(kn-k)
    
    result = min(result, ans)
print(result)

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
if n % 2 == 1:
    print(sum(list(map(lambda x: abs(x-l[((n//2))]),l))))
else:
    print(min(sum(list(map(lambda x: abs(x-l[(n//2)-1]),l))),sum(list(map(lambda x: abs(x-l[(n//2)]),l)))))

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
if n % 2 == 1:
    print(sum(list(map(lambda x: x-l[((n//2))],l))))
else:
    print(max(sum(list(map(lambda x: x-l[(n//2)-1],l))),sum(list(map(lambda x: x-l[((n//2))],l)))))

Submission status: Wrong Answer

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

hu=0
sei=0
ans=0
ahu=[]
asei=[]

for i in range(1,n+1):
  a[i-1]-=i
  ans+=abs(a[i-1])
  if a[i-1]<0:
    hu+=1
    ahu.append(abs(a[i-1]))
  elif a[i-1]>0:
    asei.append(a[i-1])
    sei+=1
zero=n-sei-hu
now=0
#print(ahu)
#print(asei)
asei.sort()
ahu.sort()

if sei < hu and sei+zero <hu:
  sei+=zero
  for i in range((hu-sei)//2+1):
    ans-=(ahu[i]-now)*(hu-sei-2*i)
    now=ahu[i]
    
elif sei > hu and sei > hu+zero:
  hu+=zero
  for i in range((sei-hu)//2+1):
    ans-=asei[i]*(sei-hu-2*i)
    now=asei[i]

print(ans)

Submission status: Wrong Answer

Solution code:
import statistics

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

print(ans)

Submission status: Wrong Answer

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

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

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

print(sum(A))

Submission status: Wrong Answer

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

sum_A = sum(A)
sum_i = (N * (N + 1)) / 2

b = (sum_A - sum_i) / N

if b < 0:
    b2 = int(b)
    b1 = b2 - 1
else:
    b1 = int(b)
    b2 = b + 1

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

print(min(ans1, ans2))

Submission status: Wrong Answer

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

li = [a[i]-(i+1) for i in range(n)]
ave = sum(li)/n
import math
ave1 = math.floor(ave)
ave2 = math.ceil(ave)

ll = []
c = 0
for i in range(n):
    c += abs(a[i]-(ave1+i+1))
else:
    ll += [c]

c =0
for i in range(n):
    c += abs(a[i]-(ave2+i+1))
else:
    ll += [c]


c = 0
for i in range(n):
    c += abs(a[i]-(ave1+i+1-1))
else:
    ll += [c]


c =0
for i in range(n):
    c += abs(a[i]-(ave2+i+1+1))
else:
    ll += [c]

print(min(ll))

Submission status: Wrong Answer

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

li = [a[i]-(i+1) for i in range(n)]
ave = sum(li)/n
import math
ave1 = math.floor(ave)
ave2 = math.ceil(ave)

ll = []
c = 0
for i in range(n):
    c += abs(a[i]-(ave1+i+1))
else:
    ll += [c]

c =0
for i in range(n):
    c += abs(a[i]-(ave2+i+1))
else:
    ll += [c]

print(min(ll))

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

m = sum(b) // n

s1 = sum([abs(b[i] - m) for i in range(n)])
s2 = sum([abs(b[i] - (m+1)) for i in range(n)]) 

print(min(s1, s2))

Submission status: Wrong Answer

Solution code:
n=int(input())

a=list(map(int,input().split()))
ahu=[]
asei=[]
hu=0
ans=0
for i in range(1,n+1):
  if a[i-1]-i<0:
    hu+=1
    ahu.append(abs(a[i-1]-i))
  else:
    asei.append(a[i-1]-i)
  ans+=abs(a[i-1]-i)  
sei=n-hu
asei.sort()
ahu.sort()
#print(ahu)
#print(asei)
#print(ans)
rui=0
if sei<hu:
  for i in range((hu-sei)//2):
    ans-=(hu-sei-i)*(ahu[i]-rui)
    rui=ahu[i]
  print(ans)
elif sei>hu:
  for i in range((hu-sei)//2):
    ans-=(sei-hu-i)*(asei[i]-rui)
    rui=asei[i]
  print(ans)
else:
  print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())

a=list(map(int,input().split()))
ahu=[]
asei=[]
hu=0
ans=0
for i in range(1,n+1):
  if a[i-1]-i<0:
    hu+=1
    ahu.append(abs(a[i-1]-i))
  else:
    asei.append(a[i-1]-i)
  ans+=abs(a[i-1]-i)  
sei=n-hu
asei.sort()
ahu.sort()
#print(ahu)
#print(asei)
#print(ans)
rui=0
if sei<hu:
  for i in range((hu-sei)//2):
    ans-=(hu-sei-i)*(ahu[i]-rui)
    rui=ahu[i]
  print(ans)
elif sei>hu:
  for i in range((hu-sei)//2):
    ans-=(sei-hu-i-1)*(asei[i]-rui)
    rui=asei[i]
  print(ans)
else:
  print(ans)

Submission status: Wrong Answer

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

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

pin=b[n//2]

ans=0

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

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def nearest_int(i):
  if i - int(i) < 0.5:
    return int(i) + 1
  else:
    return int(i)

N = int(input())
A = [a - i - 1 for i, a in enumerate(list(map(lambda x: int(x), input().split(" "))))]
A.sort()

ini = int(N/2) - 1
m_abs = ""
sumlist = 0
for i in range(ini, len(A)):
  tmp = 0
  if i == ini:
    sumlist = - sum(A[:i]) + sum(A[i:])
  else:
    sumlist -= 2 * A[i]

  if 2 * i - N > 0:
    tmp = sumlist + (2 * i - N) * A[i - 1]
  else:
    tmp = sumlist + (2 * i - N) * A[i]
  if not m_abs or m_abs > tmp:
    m_abs = tmp
  if m_abs and m_abs <= tmp:
    break
    
print(m_abs)

Submission status: Wrong Answer

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

cnt = 1
for i in range(N):
    A[i] = A[i] - cnt
    cnt += 1
A.sort(reverse=True)
medA = statistics.median(A)

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

print(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)]
A.sort()
cumsum = [0]*N
cumsum[0] = A[0]
for i in range(1, N):
    cumsum[i] = cumsum[i-1] + A[i]
ans = 1e10
for i in range(N):
    tmp = -(cumsum[i]) + (cumsum[N-1]-cumsum[i]) + (i+1)*A[i] - (N-i-1)*A[i]
    ans = min(ans, tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
from statistics import median
N=int(input())
A=list(map(int,input().split()))
B=[0]*N
for i in range(N):
  B[i]=A[i]-i
b=median(B)
ans=0
for i in range(N):
  ans+=abs(B[i]-b)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
from math import ceil, floor


stdin = sys.stdin
def ns(): return stdin.readline().rstrip()
def ni(): return int(stdin.readline().rstrip())
def nm(): return map(int, stdin.readline().split())
def nl(): return list(map(int, stdin.readline().split()))


def main():
    n = ni()
    A = nl()
    A = np.array(list(map(lambda x: A[x] - (x + 1), range(n))))
    ave = np.mean(A)
    print(min(np.sum(np.abs(A - ceil(ave))), np.sum(np.abs(A - floor(ave)))))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
A=list(map(int,input().split()))
if n==1:print(A[0]);exit()
A=[A[i]-i-1 for i in range(n)]
A.sort()
if n%2==1:
    d=A[n//2+1]
    print(sum([abs(A[i]-d) for i in range(n)]))
    exit()

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

Submission status: Wrong Answer

Solution code:
n=int(input())
A=list(map(int,input().split()))
if n==1:print(A[0]);exit()
A=[A[i]-i-1 for i in range(n)]
A.sort()
if n%2==1:
    d=A[n//2+1]
    print(sum([abs(A[i]-d) for i in range(n)]))
    exit()

ans=0
d=(A[n//2-1]+A[n//2])//2
ans=sum([abs(A[i]-d) for i in range(n)])
d=(A[n//2-1]+A[n//2])//2+1
print(min(ans,sum([abs(A[i]-d) for i in range(n)])))

Submission status: Wrong Answer

Solution code:
import collections

if __name__ == '__main__':

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

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

    #配列Bの最大countを検索
    C = collections.Counter(B)
    #整数bを決定
    b = C.most_common()[0][0]
    len_b = len(C.most_common())
    
    if len_b == n:
        #総差分を足す
        CC = [abs(c) for c in C]
        print(sum(CC))
    else:
        D = [abs(a-(b+j)) for j,a in enumerate(A,1)]
        print(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)]
b = sorted(b)
if n % 2 == 1:
  c = b[(n-1)//2]
else:
  c = (b[n//2] + b[n//2+1])//2-1

print(sum(map(abs,[b[i]-c for i in range(n)])))

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)]
b = sorted(b)
if n % 2 == 1:
  c = b[(n-1)//2]
else:
  c = (b[n//2] + b[n//2+1])//2

print(sum([b[i]-c for i in range(n)]))

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)]
b = sorted(b)
if n % 2 == 1:
  print(b[(n-1)//2])
else:
  print((b[n//2] + b[n//2+1])//2)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from statistics import median

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

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

b = median(A)

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

print(ans)

Submission status: Wrong Answer

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

print(sum(l) if sum(l) < sum(s) else sum(s))

Submission status: Wrong Answer

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

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

print(a)
a = [j-(i+1) for i, j in enumerate(a)]

a.sort()

print(a)

Submission status: Wrong Answer

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

#めぐる式二分探索
#indexが条件を満たすか判定
def isOK(now, A):
  score = 0
  for i in range(N):
    score += abs(A[i] - now - 1 - i)
  return score
  
#にぶたん
#A : 配列
def binary_search(A):
  ng = -10 ** 9 - 1
  ok = 10 ** 9 + 1
  now = 10 ** 15
  while (abs(ok - ng) > 1):
    mid = int((ok + ng) / 2)
    if isOK(ng, A) > isOK(ok, A):
      ng = mid
    elif isOK(ng, A) == isOK(ok, A):
      ng += 1
    else:
      ok = mid
    
    #print(ok, ng, mid, isOK(ok, A), isOK(ng, A))
  return min(isOK(ok, A), isOK(ng, A))
  
#a = [1, 14, 32, 51, 51, 51, 243, 419, 750, 910]
#print(binary_search(911, a))

print(binary_search(A))

Submission status: Wrong Answer

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

#めぐる式二分探索
#indexが条件を満たすか判定
def isOK(now, A):
  score = 0
  for i in range(N):
    score += abs(A[i] - now - 1 - i)
  return score
  
#にぶたん
#A : 配列
def binary_search(A):
  ng = -10 ** 9 - 1
  ok = 10 ** 9 + 1
  now = 10 ** 15
  while (abs(ok - ng) > 1):
    mid = int((ok + ng) / 2)
    if isOK(ng, A) > isOK(ok, A):
      ng = mid
    else:
      ok = mid
    
    #print(ok, ng, mid, isOK(ok, A), isOK(ng, A))
  return min(isOK(ok, A), isOK(ng, A))
  
#a = [1, 14, 32, 51, 51, 51, 243, 419, 750, 910]
#print(binary_search(911, a))

print(binary_search(A))

Submission status: Wrong Answer

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

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

ave = sum(arr) // n

ans = []
s = 0
b = ave
for i in range(n):
    s += abs(a[i] - (b + (i+1)))
ans.append(s)

s = 0
b = ave + 1
for i in range(n):
    s += abs(a[i] - (b + (i+1)))
ans.append(s)

s = 0
b = ave - 1
for i in range(n):
    s += abs(a[i] - (b + (i+1)))
ans.append(s)

print(min(ans))

Submission status: Wrong Answer

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

point = point/N
point = math.floor(point)
 
ans_list = []
ans = 0
for b in range(point-2 , point+2):
  for i in range(N):
    X = B[i]-b
    ans += np.abs(X)
  ans_list.append(ans)
  ans = 0

min_ans_list = min(ans_list)
print(min_ans_list)

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
#-------------
N = int(input())
A = list(map(int, input().split()))
#-------------

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

point = 0
for i in range(N):
  point += B[i]

point = point/N
point = math.floor(point)

ans_list = []
ans = 0
for b in range(point-1 , point+2):
  for i in range(N):
    X = B[i]-b
    ans += np.abs(X)
  ans_list.append(ans)
  ans = 0

min_ans_list = min(ans_list)
print(min_ans_list)

Submission status: Wrong Answer

Solution code:
from math import ceil,floor

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

if len(set(A)) == 1:
  print(0)
  exit()

def f(b):
  return sum([abs(A[i]-b) for i in range(N)])

mean = sum(A)//N

print(min(f(floor(mean)),f(ceil(mean))))

Submission status: Wrong Answer

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

if len(set(A)) == 1:
  print(0)
  exit()

def f(b):
  return sum([abs(A[i]-b) for i in range(N)])

def ternary_search(f, x_min, x_max, epsilon=1e-15):
    while True:
        x1,x2 = 1/3*(x_max-x_min)+x_min,2/3*(x_max-x_min)+x_min
        gap = f(x1)-f(x2)
        if gap < 0: x_max=x2
        else: x_min=x1
        if abs(gap) <= epsilon:break
    return (x_max+x_min)/2
  
x_opt = ternary_search(f,-10**12,10**12)

print(min(f(int(x_opt)), f(int(x_opt)+1),  f(int(x_opt)-1)))

Submission status: Wrong Answer

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

if len(set(A)) == 1:
  print(0)
  exit()

def f(b):
  return sum([abs(A[i]-b) for i in range(N)])

def ternary_search(f, x_min, x_max, epsilon=1e-10):
    while True:
        x1,x2 = 1/3*(x_max-x_min)+x_min,2/3*(x_max-x_min)+x_min
        gap = f(x1)-f(x2)
        if gap < 0: x_max=x2
        else: x_min=x1
        if abs(gap) <= epsilon:break
    return (x_max+x_min)/2
  
x_opt = ternary_search(f,-10**5,10**5)

print(min(f(int(x_opt)), f(int(x_opt)+1),  f(int(x_opt)-1)))

Submission status: Wrong Answer

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

if len(set(A)) == 1:
  print(0)
  exit()

def f(b):
  return sum([abs(A[i]-b) for i in range(N)])

def ternary_search(f, x_min, x_max, epsilon=1e-20):
    while True:
        x1,x2 = 1/3*(x_max-x_min)+x_min,2/3*(x_max-x_min)+x_min
        gap = f(x1)-f(x2)
        if gap < 0: x_max=x2
        else: x_min=x1
        if abs(gap) <= epsilon:break
    return (x_max+x_min)/2
  
x_opt = ternary_search(f,-10**15,10**15)

print(min(f(int(x_opt)), f(int(x_opt)+1),  f(int(x_opt)-1)))

Submission status: Wrong Answer

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

if len(set(A)) == 1:
  print(0)
  exit()

def f(b):
  return sum([abs(A[i]-b) for i in range(N)])

def ternary_search(f, x_min, x_max, epsilon=1e-10):
    while True:
        x1,x2 = 1/3*(x_max-x_min)+x_min,2/3*(x_max-x_min)+x_min
        gap = f(x1)-f(x2)
        if gap < 0: x_max=x2
        else: x_min=x1
        if abs(gap) <= epsilon:break
    return (x_max+x_min)/2
  
x_opt = ternary_search(f,-10**15,10**15)

print(min(f(int(x_opt)), f(int(x_opt)+1),  f(int(x_opt)-1)))

Submission status: Wrong Answer

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

if len(set(A)) == 1:
  print(0)
  exit()

def f(b):
  return sum([abs(A[i]-b) for i in range(N)])

def ternary_search(f, x_min, x_max, epsilon=1e-12):
    while True:
        x1,x2 = 1/3*(x_max-x_min)+x_min,2/3*(x_max-x_min)+x_min
        gap = f(x1)-f(x2)
        if gap < 0: x_max=x2
        else: x_min=x1
        if abs(gap) <= epsilon:break
    return (x_max+x_min)/2
  
x_opt = ternary_search(f,-10**9,10**9)

print(min(f(int(x_opt)), f(int(x_opt)+1),  f(int(x_opt)-1)))

Submission status: Wrong Answer

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

def f(b):
  return sum([abs(A[i]-(b+i+1)) for i in range(N)])

def ternary_search(f, x_min, x_max, epsilon=1e-20):
    while True:
        x1,x2 = 1/3*(x_max-x_min)+x_min,2/3*(x_max-x_min)+x_min
        gap = f(x1)-f(x2)
        if gap < 0: x_max=x2
        else: x_min=x1
        if abs(gap) <= epsilon:break
    return (x_max+x_min)/2
  
x_opt = ternary_search(f,-10**9,10**9)

print(min(f(int(x_opt)), f(int(x_opt)+1),  f(int(x_opt)-1)))

Submission status: Wrong Answer

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

def f(b):
  return sum([abs(A[i]-(b+i+1)) for i in range(N)])

def ternary_search(f, x_min, x_max, epsilon=1e-15):
    while True:
        x1,x2 = 1/3*(x_max-x_min)+x_min,2/3*(x_max-x_min)+x_min
        gap = f(x1)-f(x2)
        if gap < 0: x_max=x2
        else: x_min=x1
        if abs(gap) <= epsilon:break
    return (x_max+x_min)/2
  
x_opt = ternary_search(f,-10**9,10**9)

print(min(f(int(x_opt)), f(int(x_opt)+1),  f(int(x_opt)-1)))

Submission status: Wrong Answer

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

def f(b):
  return sum([abs(A[i]-(b+i+1)) for i in range(N)])

def ternary_search(f, x_min, x_max, epsilon=1e-12):
    while True:
        x1,x2 = 1/3*(x_max-x_min)+x_min,2/3*(x_max-x_min)+x_min
        gap = f(x1)-f(x2)
        if gap < 0: x_max=x2
        else: x_min=x1
        if abs(gap) <= epsilon:break
    return (x_max+x_min)/2
  
x_opt = ternary_search(f,-10**9,10**9)

print(min(f(int(x_opt)), f(int(x_opt)+1),  f(int(x_opt)-1)))

Submission status: Wrong Answer

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

def f(b):
  return sum([abs(A[i]-(b+i+1)) for i in range(N)])

def ternary_search(f, x_min, x_max, epsilon=1e-10):
    while True:
        x1,x2 = 1/3*(x_max-x_min)+x_min,2/3*(x_max-x_min)+x_min
        gap = f(x1)-f(x2)
        if gap < 0: x_max=x2
        else: x_min=x1
        if abs(gap) <= epsilon:break
    return (x_max+x_min)/2
  
x_opt = ternary_search(f,-10**9,10**9)

print(min(f(int(x_opt)), f(int(x_opt)+1),  f(int(x_opt)-1)))

Submission status: Wrong Answer

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

def f(b):
  return sum([abs(A[i]-(b+i+1)) for i in range(N)])

def ternary_search(f, x_min, x_max, epsilon=1e-7):
    while True:
        x1,x2 = 1/3*(x_max-x_min)+x_min,2/3*(x_max-x_min)+x_min
        gap = f(x1)-f(x2)
        if gap < 0: x_max=x2
        else: x_min=x1
        if abs(gap) <= epsilon:break
    return (x_max+x_min)/2
  
x_opt = ternary_search(f,-10**9,10**9)

print(min(f(int(x_opt)), f(int(x_opt)+1),  f(int(x_opt)-1)))

Submission status: Wrong Answer

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

def f(b):
  return sum([abs(A[i]-(b+i+1)) for i in range(N)])

def ternary_search(f, x_min, x_max, epsilon=1e-3):
    while True:
        x1,x2 = 1/3*(x_max-x_min)+x_min,2/3*(x_max-x_min)+x_min
        gap = f(x1)-f(x2)
        if gap < 0: x_max=x2
        else: x_min=x1
        if abs(gap) <= epsilon:break
    return (x_max+x_min)/2
  
x_opt = ternary_search(f,-10**9,10**9)

print(min(f(int(x_opt)), f(int(x_opt)+1),  f(int(x_opt)-1)))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    a = list(map(int,input().split()))
    for i in range(n):
        a[i] = a[i]-1-i
    dic = {}
    for i in range(n):
        if a[i] in dic.keys():
            dic[a[i]] += 1
        else:
            dic[a[i]] = 1
    def f(x,dic):
        ans = 0
        for k in dic.keys():
            ans += abs(k-x) * dic[k]
        return ans
    l,r = min(dic.keys()),max(dic.keys())
    while l!=r:
        if f(l,dic)>f(r,dic):
            l = (r+l)//2
        else:
            r = (r+l)//2
        if r-l==1:
            print(min(f(l,dic),f(r,dic)))
            return
    print(f(l,dic))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
a = [int(i)- k-1 for k,i in enumerate(input().split())]
ans = 10**9
a = np.array(a,dtype = 'int64')
sum_a = np.sum(a)
var= np.round(sum_a / n)
for i in range(10**4+1):
    c = a -i + var
    e = a + i + var
    ans = min(ans, min(np.sum(np.abs(c)),np.sum(np.abs(e))))
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
a = [int(i)- k-1 for k,i in enumerate(input().split())]
ans = 10**9
a = np.array(a,dtype = 'int64')
for i in range(10**5+1):
    c = a -i
    e = a + i
    ans = min(ans, min(np.sum(np.abs(c)),np.sum(np.abs(e))))
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
a = [int(i)- k-1 for k,i in enumerate(input().split())]
ans = 10**9
a = np.array(a,dtype = 'int64')
sum_a = np.sum(a)
var_f = np.floor(sum_a / n)
var_c = np.ceil(sum_a / n)
b = a - int(var_f)
d = a - int(var_c)
c = np.abs(b)
e = np.abs(d)

print(min(np.sum(c),np.sum(e)))

Submission status: Wrong Answer

Solution code:
import statistics
n = int(input())
a = list(int(x)-i-1 for i,x in enumerate(input().split()))
b = statistics.median(a)
print(sum(abs(j-b) for j in a))

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
from statistics import median
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    B = []
    for i, a in enumerate(A):
        B.append(a-(i+1))
    med = median(B)
    ans = 0
    for b in B:
        ans += abs(b-med)
    print(ans)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
ls = list(map(int,input().split()))
for i in range(n):
    ls[i] -= i+1
mn = int(sum(ls)/n)
if sum(ls)/n> 0:
    mx = int(sum(ls)/n) +1
elif sum(ls)/n< 0:
    mx = int(sum(ls)/n)-1
else:
    mx = float("inf")
lsmn = [abs(e-mn) for e in ls]
lsmx = [abs(e-mx) for e in ls]
print(min(sum(lsmn),sum(lsmx)))

Submission status: Wrong Answer

Solution code:

import statistics
N = int(input())

nums = list(map(int, input().split()))
nums = [num - (i + 1) for i, num in enumerate(nums)]

# print(nums)


def compute_sour(num, b):
    return abs(num - b)


middle_num = statistics.median(nums)

# print(middle_num)
ans = 0
for num in nums:
    ans += compute_sour(num, middle_num)
print(ans)

Submission status: Wrong Answer

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

nums = list(map(int, input().split()))
nums = [num - (i + 1) for i, num in enumerate(nums)]

# print(nums)


def compute_sour(num, b):
    return abs(num - b)


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

# print(middle_num)
ans = 0
for num in nums:
    ans += compute_sour(num, middle_num)
print(ans)

Submission status: Wrong Answer

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

nums = list(map(int, input().split()))
nums = sorted([num - (i + 1) for i, num in enumerate(nums)])

# print(nums)


def compute_sour(num, b):
    return abs(num - b)


if N % 2 == 0:
    middle_num = nums[(N // 2) + 1]
else:
    middle_num = nums[N // 2]


ans = 0
for num in nums:
    ans += compute_sour(num, middle_num)
print(ans)

Submission status: Wrong Answer

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

nums = list(map(int, input().split()))
nums = [num - (i + 1) for i, num in enumerate(nums)]

# print(nums)


def compute_sour(num, b):
    return abs(num - b)


# print(sum(nums), len(nums))
middle_num = math.floor(sum(nums) / len(nums))
# print(middle_num)
ans = 0
for num in nums:
    ans += compute_sour(num, middle_num)
print(ans)

Submission status: Wrong Answer

Solution code:
from math import ceil
n = int(input())
arr = list(map(int, input().split()))
s = 0
for i in range(n):
    s += arr[i] - (i+1)

m1 = s // n
m2 = int(ceil(s / n))
ans1, ans2 = 0, 0
for i in range(n):
    ans1 += abs(arr[i]-(m1+i+1))
    ans2 += abs(arr[i]-(m2+i+1))
print (min(ans1, ans2))