Problem:


Score : 300 points

Problem Statement

Snuke has an integer sequence A of length N.

He will freely choose an integer b.
Here, he will get sad if A_i and b+i are far from each other.
More specifically, the sadness of Snuke is calculated as follows:

abs(A_1 - (b+1)) + abs(A_2 - (b+2)) + ... + abs(A_N - (b+N))

Here, abs(x) is a function that returns the absolute value of x.

Find the minimum possible sadness of Snuke.

Constraints

1 \leq N \leq 2 \times 10^5

1 \leq A_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the minimum possible sadness of Snuke.

Sample Input 1

5
2 2 3 5 5

Sample Output 1

2

If we choose b=0, the sadness of Snuke would be abs(2-(0+1))+abs(2-(0+2))+abs(3-(0+3))+abs(5-(0+4))+abs(5-(0+5))=2.
Any choice of b does not make the sadness of Snuke less than 2, so the answer is 2.

Sample Input 2

9
1 2 3 4 5 6 7 8 9

Sample Output 2

0

Sample Input 3

6
6 5 4 3 2 1

Sample Output 3

18

Sample Input 4

7
1 1 1 1 2 3 4

Sample Output 4

6



Sample input:
5
2 2 3 5 5


Sample output:
2

Submission status: Wrong Answer

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

if len(B)%2:
    ans = 0
    for i in range(n):
        ans += abs(B[i]-B[len(B)//2])
else:
    ans = float("inf")
    tmp = 0
    for i in range(n):
        tmp += abs(B[i]-B[len(B)//2-1])
    ans = min(ans, tmp)
    tmp = 0
    for i in range(n):
        tmp += abs(B[i]-B[len(B)//2])
    ans = min(ans, tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
# sys.setrecursionlimit(100000)


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


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n = input_int()
    A = input_int_list()
    for i in range(n):
        A[i] = A[i] - (i + 1)
    b = sum(A) // n

    tmp0 = 0
    tmp1 = 0
    for a in A:
        tmp0 += abs(a - b)
        tmp1 += abs(a - b - 1)

    print(min(tmp0, tmp1))

    return


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[3]:


from decimal import Decimal,ROUND_HALF_UP


# In[22]:


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


# In[26]:


a_ = [a-i-1 for i,a in enumerate(A)]
my_round_int = lambda x: int((x * 2 + 1) // 2)
b1 = sum(a_)//N
b2 = -(-sum(a_)//N)
ans1 = [abs(a-b1) for a in a_]
ans2 = [abs(a-b2) for a in a_]
print(min(sum(ans1), sum(ans2)))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

A_list_min = 10**9+1
A_list_sum = 0
for i in range(N):
    A_list[i] = A_list[i] - (i+1)
    A_list_min = min(A_list_min, A_list[i])
    A_list_sum += A_list[i]

A_ave_modi = A_list_sum//N - A_list_min
ans1 = 0
ans2 = 0
for i in range(N):
    ans1 += abs(A_list[i] - A_list_min - A_ave_modi)
    ans2 += abs(A_list[i] - A_list_min - (A_ave_modi+1))
ans = min(ans1, ans2)
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
c=sorted(a)
m=c[n//2-1] #偶数の場合右側
ans=0
b=m-n//2
for i in range(n):
    ans+=abs(b-a[i]+i)
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
c=sorted(a)
m=c[n//2] #偶数の場合右側
ans=0
b=m-n//2
for i in range(n):
    ans+=abs(b-a[i]+i)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

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

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

if n%2==1:
  print(a[n//2])
else:
  print((a[n//2] + a[n//2 - 1])//2)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N=int(input())
*A,=map(int,input().split())
B=[A[i]-(i+1) for i in range(N)]
b=sum(B)//N
C=[b+i for i in range(-100,100)]
ans=[sum(abs(b-c)for b in B)for c in C]
print(min(ans))

Submission status: Wrong Answer

Solution code:
N=int(input())
*A,=map(int,input().split())
B=[A[i]-(i+1) for i in range(N)]
b=sum(B)//N
ans1=sum(abs(B[i]-b)for i in range(N))
ans2=sum(abs(B[i]-b+1)for i in range(N))
ans3=sum(abs(B[i]-b-1)for i in range(N))
ans=min([ans1,ans2,ans3])
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import numpy as np

N = int(input())
A = np.array(list(map(int,input().split())))
A -= np.arange(1,N+1)
print(sum(A-int(np.median(A))))

Submission status: Wrong Answer

Solution code:
n = int(input())
a0 = [int(j)-int(i)-1 for i, j in enumerate(input().split())]
a = sum(a0)
num = a/n
if num < 0:
    if not num.is_integer():
        num = int(num)-1
ans = int(sum([abs(x-num) for x in a0]))
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a0 = [int(j)-int(i)-1 for i, j in enumerate(input().split())]
a = sum(a0)
num = a/n
if num > 0:
    ans = int(sum([abs(x-num) for x in a0]))
    print(ans)
else:
    if not num.is_integer():
        num = int(num)-1
    ans = int(sum([abs(x-num) for x in a0]))
    print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a0 = [int(j)-int(i)-1 for i, j in enumerate(input().split())]
a = sum(a0)
num = a/n
if num > 0:
    print(a-n*round(num))
else:
    if not num.is_integer():
        num = int(num)-1
    ans = int(sum([abs(x-num) for x in a0]))
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
def main():
    def nibun(score):
        def isok(num, score_t0):
            score_t = sum([abs(a2e - num) for a2e in a2])
            if score_t < score_t0:
                return True, score_t
            else:
                return False, score_t
        ok = a2max
        ng = a2min
        while (ok - ng) >= 1:
            mid = (ok + ng) // 2
            res = isok(mid, score)
            if res[0]:
                score = res[1]
                if ok == mid:
                    break
                ok = mid
            else:
                if ng == mid:
                    break
                ng = mid
        return score

    n, *a = map(int, read().split())
    a2 = tuple([ea - i - 1 for i, ea in enumerate(a)])

    a2max = max(a2)
    score_tmp = sum([abs(ea2 - a2max) for ea2 in a2])
    a2min = min(a2)
    r = nibun(score_tmp)
    print(r)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter


def LI():
    return list(map(int, input().split()))


N = int(input())
A = LI()
x = []
for i in range(N):
    x.append(A[i]-(i+1))

x = Counter(x)
B = max(x, key=x.get)
ans = 0

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

Submission status: Wrong Answer

Solution code:
import statistics
n,*a=map(int,open(0).read().split())
b=[q-i for i,q in enumerate(a,1)]
c=statistics.median(b)
ans=sum(map(abs,[p-c for p in b]))
print(ans)

Submission status: Wrong Answer

Solution code:
n,*a=map(int,open(0).read().split())
b=[q-j for j,q in enumerate(a,1)]
# print(b)
c=sum(b)//n
ans=10**10
for i in range(c-10,c+11):
  tmp=sum(map(abs,[q-i for q in b]))
  ans=min(ans,tmp)
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(a[i]- (i+1))

from math import ceil ,floor

total = sum(b)

ave_1 = ceil(total/n) 
ave_2 = floor(total/n) 

ans1 = 0
ans2 = 0
for i in range(n):
    ans1 += abs(b[i]-ave_1) 
    ans2 += abs(b[i]-ave_2)

print(min(ans1,ans2))

Submission status: Wrong Answer

Solution code:
'''
Created on 2020/09/03

@author: harurun
'''
def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write
  
  N=int(pin())
  A=list(map(int,pin().split()))
  s=0
  for i in range(N):
    A[i]-=i+1
    s+=A[i]
  t=s/N
  x=int(t)
  y=int(t)+1
  z=int(t)-1
  u=int(t)+2
  h=int(t)-2
  ans1=0
  ans2=0
  ans3=0
  ans4=0
  ans5=0
  for j in range(N):
    ans1+=abs(A[j]-x)
    ans2+=abs(A[j]-y)
    ans3+=abs(A[j]-z)
    ans4+=abs(A[j]-u)
    ans5+=abs(A[j]-h)
  ans=min(ans1,ans2,ans3,ans4,ans5)
  print(ans)
  return 
main()

Submission status: Wrong Answer

Solution code:
'''
Created on 2020/09/03

@author: harurun
'''
def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write
  
  N=int(pin())
  A=list(map(int,pin().split()))
  s=0
  for i in range(N):
    A[i]-=i+1
    s+=A[i]
  t=s/N
  x=int(t)
  y=int(t)+1
  if t<0:
    y=int(t)-1
  ans1=0
  ans2=0
  for j in range(N):
    ans1+=abs(A[j]-x)
    ans2+=abs(A[j]-y)
  ans=min(ans1,ans2)
  print(ans)
  return 
main()

Submission status: Wrong Answer

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

from math import ceil ,floor

total = sum(a) - n*(n+1)//2

ave_1 = ceil(total/n) 
ave_2 = floor(total/n) 

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

print(min(ans1,ans2))

Submission status: Wrong Answer

Solution code:
'''
Created on 2020/09/03

@author: harurun
'''
def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write
  
  N=int(pin())
  A=list(map(int,pin().split()))
  s=0
  for i in range(N):
    A[i]-=i+1
    s+=A[i]
  t=s/N
  x=int(t)
  y=int(t)+1
  z=int(t)-1
  ans1=0
  ans2=0
  ans3=0
  for j in range(N):
    ans1+=abs(A[j]-x)
    ans2+=abs(A[j]-y)
    ans3+=abs(A[j]-z)
  ans=min(ans1,ans2,ans3)
  print(ans)
  return 
main()

Submission status: Wrong Answer

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

from math import ceil ,floor

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

ave_1 = ceil(total/n) 
ave_2 = floor(total/n) 


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

print(min(ans1,ans2))

Submission status: Wrong Answer

Solution code:
import numpy as np

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

arr = np.arange(n) + 1
diff = a - arr

diff.sort()

diff = diff - np.median(diff)
diff = diff.astype(int)

print(np.abs(diff).sum())

Submission status: Wrong Answer

Solution code:
import numpy as np

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

arr = np.arange(n, dtype=np.int64) + 1
diff = a - arr

diff.sort()

diff = diff - np.median(diff)
diff = diff.astype(np.int64)

print(np.abs(diff).sum())

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
ins = lambda: input().rstrip()
ini = lambda: int(input().rstrip())
inm = lambda: map(int, input().rstrip().split())
inl = lambda: list(map(int, input().split()))
out = lambda x, s='\n': print(s.join(map(str, x)))

n = ini()
a = inl()
j = 1
count = 0
pos = {}
neg = {}
for i in range(n):
    a[i] -= j
    j += 1
    count += 1 if a[i] >= 0 else -1
    count -= 1 if a[i] == 0 else 0
    if a[i] > 0:
        if a[i] not in pos:
            pos[a[i]] = 0
        pos[a[i]] += 1
    elif a[i] < 0:
        if a[i] not in neg:
            neg[a[i]] = 0
        neg[a[i]] += 1
zeros = a.count(0)
total = sum([abs(i) for i in a])
if count == 0 or abs(count) < zeros:
    print(total)
elif count > 0:
    ans = 0
    for i, j in pos.items():
        ans = max(i*j - zeros*abs(i), ans)
    print(total - ans)
else:
    ans = 0
    for i, j in neg.items():
        ans = min(i*j + zeros*abs(i), ans)
    print(total + ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from math import floor,ceil
def main():
    n, *a = map(int, read().split())
    a2 = [ea -i - 1 for i, ea in enumerate(a)]
    a2_ave = floor(sum(a2) / n)

    r1 = sum([abs(ea2 - a2_ave) for ea2 in a2])
    r2 = sum([abs(ea2 - a2_ave - 1) for ea2 in a2])
    r3 = sum([abs(ea2 - a2_ave + 1) for ea2 in a2])
    r = min(r1, r2, r3)
    print(r)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from math import floor
def main():
    n, *a = map(int, read().split())
    a2 = [ea -i - 1 for i, ea in enumerate(a)]
    suma2 = sum(a2)
    a2_ave = suma2 / n
    a2_ave_rem = a2_ave % 1
    a2_ave = floor(a2_ave)

    if a2_ave_rem == 0:
        r = sum([abs(a2_ave - ea2) for ea2 in a2])
        print(r)
    else:
        if a2_ave_rem >= 0.5:
            a2_ave += 1
            r = sum([abs(a2_ave - ea2) for ea2 in a2])
            print(r)
        else:
            r = sum([abs(a2_ave - ea2) for ea2 in a2])
            print(r)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
As = list(mapint())

As = [a-i for i, a in enumerate(As, 1)]
mean_r = sum(As)//N
mean_l = -(-sum(As)//N)
print(min(sum([abs(a-mean_r) for a in As]), sum([abs(a-mean_l) for a in As])))

Submission status: Wrong Answer

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

ans = 10**18
for b1 in range(b-10,b+12):
  tmp = 0
  for i in range(N):
    tmp += abs(A[i]-b1)
  ans = min(ans,tmp)
  #print(b1,tmp)
print(ans)

Submission status: Wrong Answer

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

ans = 10**18
for b1 in range(b-10,b+12):
  tmp = 0
  for i in range(N):
    tmp += abs(A[i]-b1)
  ans = min(ans,tmp)
  #print(b1,tmp)
print(ans)

Submission status: Wrong Answer

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

bs = [b-2, b-1, b, b+1, b+2]
ans = 10**18
for b1 in bs:
  tmp = 0
  for i in range(N):
    tmp += abs(A[i]-b1)
  ans = min(ans,tmp)
print(ans)

Submission status: Wrong Answer

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

bs = [b-1, b, b+1]
ans = 1e18
for b1 in bs:
  tmp = 0
  for i in range(N):
    tmp += abs(A[i]-b1)
  ans = min(ans,tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
b = 0
for i in range(N):
    A[i] -= i+1
    b += A[i]
b //= N
bs = [b-1, b, b+1]
ans = 1e10
for b1 in bs:
  tmp = 0
  for i in range(N):
    tmp += abs(A[i]-b1)
  ans = min(ans,tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


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


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


print(min(f(sum(A)//N),f(sum(A)//N+1)))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
B = [0]*N
ans =0 
for i,j in enumerate(A):
    B[i] = j-(i+1)
B=sorted(B)
if(N%2==1):
    b = B[N//2]
else:
    b = (B[N//2]-1+B[(N//2)])//2
for i,j in enumerate(A):
    ans+= abs(j-(b+i+1))
print(ans)

Submission status: Wrong Answer

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

a = [ai - i for i, ai in enumerate(a)]
ave = sum(a) // n
ans1 = sum(abs(ai - ave) for ai in a)
ans2 = sum(abs(ai - ave - 1) for ai in a)
print(min(ans1, ans2))

Submission status: Wrong Answer

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

a = [ai - i for i, ai in enumerate(a)]
ave = sum(a) // n
ans1 = sum(abs(ai - ave) for ai in a)
ans2 = sum(abs(ai - ave + 1) for ai in a)
print(min(ans1, ans2))

Submission status: Wrong Answer

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

a = [ai - i for i, ai in enumerate(a)]
ave = sum(a) // n
print(sum(abs(ai-ave) for ai in a))

Submission status: Wrong Answer

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

def func(b):
    return sum([abs(a[i]-(b+i+1)) for i in range(n)])

# 3分探索を行う
low = -inf
high = inf

while abs(high-low) > 0.01:
    c1 = (low*2 + high)/3
    c2 = (low + high*2)/3

    if func(c1) > func(c2):
        low = c1
    else:
        high = c2
mid = (high+low)/2
ans = min(func(int(mid)), func(int(mid+1)), func(int(mid-1)))
print(ans)

Submission status: Wrong Answer

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

def func(b):
    return sum([abs(a[i]-(b+i+1)) for i in range(n)])

# 3分探索を行う
low = -inf
high = inf

while high-low > 1:
    c1 = (low*2 + high)/3
    c2 = (low + high*2)/3

    if func(c1) > func(c2):
        low = c1
    else:
        high = c2
mid = (high+low)/2
ans = min(func(int(mid)), func(int(mid+1)), func(int(mid-1)))
print(ans)

Submission status: Wrong Answer

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

def func(b):
    return sum([abs(a[i]-(b+i)) for i in range(n)])

# 3分探索を行う
low = -inf
high = inf

while high-low > 1:
    c1 = (low*2 + high)/3
    c2 = (low + high*2)/3

    if func(c1) > func(c2):
        low = c1
    else:
        high = c2
mid = (high+low)/2
ans = min(func(int(mid)), func(int(mid+1)), func(int(mid-1)))
print(ans)

Submission status: Wrong Answer

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

def func(b):
    return sum([abs(a[i]-(b+i)) for i in range(n)])

# 3分探索を行う
low = -inf
high = inf

while high-low < 1:
    c1 = (low*2 + high)/3
    c2 = (low + high*2)/3

    if func(c1) > func(c2):
        low = c1
    else:
        high = c2
mid = (high+low)/2
ans = min(func(int(mid)), func(int(mid+1)), func(int(mid-1)))
print(ans)

Submission status: Wrong Answer

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

a_i=[]
pl=0
mi=0
mi_cnt=0
pl_cnt=0
for i in range(n):
  a_i.append((a[i]-(i+1)))
  if a[i]-(i+1)<0:
    mi+=a[i]-(i+1)
    mi_cnt+=1
  else:
    pl+=a[i]-(i+1)
    pl_cnt+=1

if mi_cnt!=0:
  mi=mi/mi_cnt

if pl_cnt!=0:
  pl=pl/pl_cnt

al=int(mi+pl)
ans1=0
ans2=0
ans3=0
for i in a_i:
  ans1+=abs(i-al-1)
  ans2+=abs(i-al+1)
  ans3+=abs(i-al)
print(min(ans1,ans2,ans3))

Submission status: Wrong Answer

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

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

if n%2==0:
  tmp=(a[n//2]+a[n//2+1])//2
else:
  tmp=(a[n//2])
  
ans=0
for aa in a:
  ans+=abs(aa-tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import math
n = int(input())
#x, y = map(int,input().split())
A = list(map(int,input().split()))
ans = 0
a = n
b = 0
c = 0
for i in range(n):
    t = A[i]-(i+1)
    b += -t * 2
    c += t**2
x = -b/(2*a)
l = math.floor(x)
h = math.ceil(x)
tmp1 = 0
tmp2 = 0
for i in range(n):
    tmp1 += abs(A[i]-(i+1)-l)
    tmp2 += abs(A[i]-(i+1)-h)
print(min(tmp1, tmp2))

Submission status: Wrong Answer

Solution code:
n,*a = map(int,open(0).read().split())
for i in range(n):
  a[i] -= 1+i
asum = sum(a)
aave = int(round(sum(a)/n,0))
ans = min([sum([abs(i - j) for i in a]) for j in range(aave-2,aave+4)])
print(ans)

Submission status: Wrong Answer

Solution code:
n,*a = map(int,open(0).read().split())
for i in range(n):
  a[i] -= 1+i
asum = sum(a)
aave = int(round(sum(a)/n,0))
ans = min([sum([abs(i - j) for i in a]) for j in range(aave-1,aave+3)])
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
num = list(map(int,input().split()))
for i in range(1, N+1):
    num[i-1] -= i
numbers = np.array(num)
b = int(np.median(numbers))
numbers-= b
print(numbers.sum())

Submission status: Wrong Answer

Solution code:
import math
import copy
N = int(input())
num = list(map(int,input().split()))
for i in range(1, N+1):
    num[i-1] -= i
b = math.floor(sum(num)/N)
c = math.ceil(sum(num)/N)
b_ans = 0
c_ans = 0
b_num = copy.copy(num)
c_num = copy.copy(num)
for j in b_num:
    j -= b
    b_ans += abs(j)
for k in c_num:
    k -= c
    c_ans += abs(k)
if b_ans< c_ans:
    print(b_ans)
else:
    print(c_ans)

Submission status: Wrong Answer

Solution code:
# サンプル3
# 6
# 6 5 4 3 2 1
# b=3で2+0+2+4+6+8 = 22 b=4で1+1+3+5+7+9=26
# わからんからコード書いて試す
n = int(input())
a = list(map(int, input().split()))
# for b in range(-10, 10):
#     tmp = 0
#     for i, v in enumerate(a):
#         tmp += abs(v - (b + i + 1))
#     print(f"b={b}, tmp={tmp}")
# でかくても小さくてもダメっぽい
# 三分探索？やったことないしやり方わからんからググる
# めぐる式にこれhttps://qiita.com/ganariya/items/1553ff2bf8d6d7789127をしただけ

ok, ng = -10**9, 10**9 + 1


def calc(b):
    ret = 0
    for i, v in enumerate(a):
        ret += abs(v - (b + i + 1))
    return ret


# なぜかTLEなるのでカウンタを設置してみた
c = 0
while c < 50:
    c += 1
    c1 = (2 * ok + ng) // 3
    c2 = (ok + 2 * ng) // 3
    b1, b2 = calc(c1), calc(c2)
    if b1 > b2:
        ok = c1 + 1  # +1のきもちは不明
    else:
        ng = c2

print(calc(ok))

Submission status: Wrong Answer

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()


def resolve():
    N = I()
    A = LI()

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

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
#coding: utf-8

import math

N = int(input())
A = [int(n) for n in input().split()]
for i in range(len(A)):
    A[i] -= (i+1)

b = sum(A) / N
b1 = math.floor(b)
b2 = math.ceil(b)
sad1 = sum([abs(a-b1) for a in A])
sad2 = sum([abs(a-b2) for a in A])

print(min(sad1, sad2))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=sum([a[i]-i for i in range(n)])
c=b//n if b>0 else -(-b)//n
ans=float("inf")
for j in range(-5,5):
    ans=min(sum([abs(a[i]-c-i+j) for i in range(n)]),ans)
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=sum([a[i]-i for i in range(n)])
c=b//n if b>0 else -(-b)//n
ans=float("inf")
for i in range(-5,5):
    ans=min(sum([abs(a[i]-c-i) for i in range(n)]),ans)
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=sum([a[i]-i for i in range(n)])
c=b//n if b>0 else -(-b)//n
print(sum([abs(a[i]-c-i) for i in range(n)]))
#print(c)

Submission status: Wrong Answer

Solution code:
n=int(input())
print(sum(map(int,input().split())))

Submission status: Wrong Answer

Solution code:
import statistics
n = int(input())
a = []
for i,j in enumerate(map(int,input().split())):
  a.append(j-i-1)
b,s = statistics.median(a),0
for i in a:
  s+=abs(i-b)
print(s)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = []
for i,j in enumerate(map(int,input().split())):
  a.append(j-i-1)
a1,a2 = sum(a)//n,sum(a)//n+1
s1,s2 = 0,0
for i in a:
  s1+=abs(i-a1)
  s2+=abs(i-a2)
print(min(s1,s2))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = list(map(int,input().split()))
    for i in range(N):
        A[i] -= i+1
    
    def f(b):
        res = 0
        for a in A:
            res += abs(a-b)
        return res
    
    l = min(A)
    r = max(A)

    while l < r-2:
        m1 = (r-l)*2//3+l
        m2 = (r-l)//3+l
        tmp1 = f(m1)
        tmp2 = f(m2)

        if tmp2 < tmp1:
            r = m1
        else:
            l = m2
    print(f((l+r)//2))

main()

Submission status: Wrong Answer

Solution code:

def main():
    from math import floor,ceil
    N = int(input())
    A = list(map(int,input().split()))
    for i in range(N):
        A[i] -= i+1
    x = sum(A)/N

    fx = floor(x) 
    cx = ceil(x)
    
    def f(b):
        res = 0
        for a in A:
            res += abs(a-b)
        return res

    print(min(f(cx),f(fx)))

main()

Submission status: Wrong Answer

Solution code:
n = int(input())
A = [int(x) for x in input().split()]
A_ = sorted([a - i for i, a in enumerate(A, 1)])
b = max(A_[len(A) // 2], 0)
print(sum([abs(a - b) for a in A_]))

Submission status: Wrong Answer

Solution code:
n = int(input())
A = [int(x) for x in input().split()]
A_ = sorted([a - i for a, i in enumerate(A, 1)])
b = max(A_[len(A) // 2], 0)
print(sum([abs(a - b) for a in A_]))

Submission status: Wrong Answer

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

def solve(N: int, A: "List[int]"):
    from scipy.optimize import dual_annealing
    A = [a-i for i, a in enumerate(A, 1)]
    def f(b):
        return sum(abs(a-b) for a in A)
    res = dual_annealing(f, [[min(A), max(A)+1]], maxiter=3)
    #print(res)
    b = res.x[0]
    return min(f(int(round(b))), f(int(round(b+1))))

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"    
    print(solve(N, A))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Wrong Answer

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

def solve(N: int, A: "List[int]"):
    from scipy.optimize import dual_annealing
    A = [a-i for i, a in enumerate(A, 1)]
    def f(b):
        return sum(abs(a-b) for a in A)
    res = dual_annealing(f, [[min(A), max(A)+1]], maxiter=10)
    #print(res)
    b = res.x[0]
    return min(f(int(round(b))), f(int(round(b+1))))

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"    
    print(solve(N, A))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Wrong Answer

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

def solve(N: int, A: "List[int]"):
    from scipy.optimize import dual_annealing
    A = [a-i for i, a in enumerate(A, 1)]
    def f(b):
        return sum(abs(a-b) for a in A)
    res = dual_annealing(f, [[min(A), max(A)+1]], maxiter=100)
    print(res)
    b = res.x[0]
    return min(f(int(round(b))), f(int(round(b+1))))

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"    
    print(solve(N, A))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Wrong Answer

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

def solve(N: int, A: "List[int]"):
    A = [a-i for i, a in enumerate(A, 1)]
    def f(b):
        return sum(abs(a-b) for a in A)
    lb, ub = min(A), max(A)+1
    while lb + 1 < ub:
        t1 = (2 * lb + ub) / 3
        t2 = (lb + 2 * ub) / 3
        if f(lb) > f(ub):
            lb = t1
        else:
            ub = t2
    return min(f(round(lb)), f(round(lb+1)))

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"    
    print(solve(N, A))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Wrong Answer

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

def solve(N: int, A: "List[int]"):
    A = [a-i for i, a in enumerate(A, 1)]
    def f(b):
        return sum(abs(a-b) for a in A)
    lb, ub = min(A), max(A)
    while lb + 1 < ub:
        t1 = (2 * lb + ub) / 3
        t2 = (lb + 2 * ub) / 3
        if f(lb) > f(ub):
            lb = t1
        else:
            ub = t2
    return min(f(round(lb)), f(round(lb+1)))

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"    
    print(solve(N, A))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Wrong Answer

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

def solve(N: int, A: "List[int]"):
    def f(b):
        return sum(abs(a-i-b) for i, a in enumerate(A, 1))
    lb, ub = -200_000_000, 200_000_001
    while lb + 1 < ub:
        t1 = (2 * lb + ub) / 3
        t2 = (lb + 2 * ub) / 3
        if f(lb) > f(ub):
            lb = t1
        else:
            ub = t2
    return min(f(round(lb)), f(round(lb+1)))


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"    
    print(solve(N, A))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()