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:
import math, sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import lru_cache
from heapq import heapify, heappop, heappush
from itertools import accumulate, combinations, permutations
input = sys.stdin.readline
mod = 10**9 + 7
ns = lambda: input().strip()
ni = lambda: int(input().strip())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n = ni()
a = nl()

def calculate(a, med):
    ans = []
    start = med - len(a) // 2
    for i in range(len(a)):
        ans.append(abs(a[i] - start - i))
    #print(ans)
    return sum(ans)

if n % 2 == 1:
    med = sorted(a)[n//2]
    print(calculate(a, med))
else:
    med1 = sorted(a)[n//2]
    med2 = sorted(a)[n//2 - 1]
    print(min(calculate(a, med1), calculate(a, med2)))

Submission status: Wrong Answer

Solution code:
import math, sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import lru_cache
from heapq import heapify, heappop, heappush
from itertools import accumulate, combinations, permutations
input = sys.stdin.readline
mod = 10**9 + 7
ns = lambda: input().strip()
ni = lambda: int(input().strip())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n = ni()
a = nl()

avr = sum(a) // n
left = avr
right = avr + 1
if n % 2 == 1:
    ans1, ans2 = [], []
    center1, center2 = left, right
    start1, start2 = center1 - (n//2), center2 - (n//2)
    for i in range(n):
        ans1.append(abs(a[i] - start1 - i))
        ans2.append(abs(a[i] - start2 - i))
    print(min(sum(ans1), sum(ans2)))
else:
    ans1, ans2, ans3, ans4 = [], [], [], []
    center1, center2 = left, right
    start1, start2 = center1 - (n//2), center2 - (n//2)
    start3, start4 = start1 + 1, start2 + 1
    for i in range(n):
        ans1.append(abs(a[i] - start1 - i))
        ans2.append(abs(a[i] - start2 - i))
        ans3.append(abs(a[i] - start3 - i))
        ans4.append(abs(a[i] - start4 - i))
    print(min([sum(ans1), sum(ans2), sum(ans3), sum(ans4)]))

Submission status: Wrong Answer

Solution code:
import math, sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import lru_cache
from heapq import heapify, heappop, heappush
from itertools import accumulate, combinations, permutations
input = sys.stdin.readline
mod = 10**9 + 7
ns = lambda: input().strip()
ni = lambda: int(input().strip())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n = ni()
a = nl()

avr = sum(a) // n
left = avr
right = avr + 1
if n % 2 == 1:
    ans1, ans2 = [], []
    center1, center2 = left, right
    start1, start2 = center1 - (n//2), center2 - (n//2)
    for i in range(n):
        ans1.append(abs(a[i] - start1 - i))
        ans2.append(abs(a[i] - start2 - i))
    print(min(sum(ans1), sum(ans2)))
else:
    ans1, ans2, ans3, ans4 = [], [], [], []
    center1, center2 = left, right
    start1, start2 = center1 - (n//2), center2 - (n//2)
    start3, start4 = start1 - 1, start2 - 1
    for i in range(n):
        ans1.append(abs(a[i] - start1 - i))
        ans2.append(abs(a[i] - start2 - i))
        ans3.append(abs(a[i] - start3 - i))
        ans4.append(abs(a[i] - start4 - i))
    print(min([sum(ans1), sum(ans2), sum(ans3), sum(ans4)]))

Submission status: Wrong Answer

Solution code:
#import collections
#aa = collections.Counter(a) # list to list
#from itertools import combinations # (string,3) 3回

mod = 10**9 + 7

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

    n = int(input())
    A = readInts()
    sumA = sum(A)
    facA = (n * (n+1))//2
    na = sumA - facA

    if na / n < 0:
        p = na/n
        if abs(p) % 10 != 0:
            b = int(p) - 1
        else:
            b = int(p)
    else:
        b = round(na/n)
    #print(b)
    ans = 0
    for i in range(n):
        #print(A[i],b,i+1)
        ans += abs(A[i] - (b + (i+1)))
    print(ans)



if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
import statistics

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

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

b = statistics.median(bi)

ans = 0
for i in range(n):
    ans += int(abs(bi[i] - b))

print(ans)

Submission status: Wrong Answer

Solution code:
import statistics

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

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

b = statistics.median(bi)

ans = 0
for i in range(n):
    ans += int(abs(bi[i] - b))

print(ans)

Submission status: Wrong Answer

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

for i in range(N):
  A[i]-=(i+1)
  #mean+=A[i]/(N)
A=np.array(A)
mean=np.mean(A)

#平均を０に近づけるようにする
mean=round(mean)
def sudness(A):
  sad=0
  for a in A:
    sad+=abs(a)
  return int(sad)

print(sudness(A-mean))

Submission status: Wrong Answer

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

for i in range(N):
  A[i]-=(i+1)
  #mean+=A[i]/(N)
A=np.array(A)
mean=np.mean(A)

#平均を０に近づけるようにする
mean=round(mean)
def sudness(A):
  sad=0
  for a in A:
    sad+=abs(a)
  return sad

print(sudness(A-mean))

Submission status: Wrong Answer

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

#平均を０に近づけるようにする
mean=round(mean)
def sudness(A):
  sad=0
  for a in A:
    sad+=abs(a)
  return sad

print(sudness(A-mean))

Submission status: Wrong Answer

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

#平均を０に近づけるようにする
mean=round(mean)
def sudness(A):
  sad=0
  for a in A:
    sad+=abs(a)
  return sad

print(sudness(A-mean))

Submission status: Wrong Answer

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

mean=sum(A)//N
def sudness(A):
  sad=0
  for a in A:
    sad+=abs(a)
  return sad

print(min( sudness(A-mean), sudness(A-(mean+1)),sudness(A-(mean-1)) ))

Submission status: Wrong Answer

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

mean=sum(A)//N
def sudness(A):
  sad=0
  for a in A:
    sad+=abs(a)
  return sad

print(min( sudness(A-mean), sudness(A-(mean+1)) ))

Submission status: Wrong Answer

Solution code:
n = int(input())
a_lst = [int(elem) for elem in input().split()]
b_lst = [(a - i - 1) for i, a in enumerate(a_lst)]
b_lst = sorted(b_lst)

if n % 2 == 0:
  med = b_lst[n // 2] + b_lst[(n // 2) - 1] // 2
else:
  med = b_lst[n // 2]

res = 0
for i in range(n):
    res += abs(b_lst[i] - med)
print(res)

Submission status: Wrong Answer

Solution code:
n = int(input())
a_lst = [int(elem) for elem in input().split()]

res = [0] * n
for b in range(n):
  for i in range(n):
    res[b] += abs(a_lst[i] - b - i - 1)
print(min(res))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int ,input().split()))
d = min(a)-len(a) - len(a)
u = max(a) * 2

while u-d > 1:
    mid = (d + u) // 2
    val = 0
    for i in range(n):
        val += a[i] - (mid + i)
    if val <= 0:
        u = mid
    else:
        d = mid
ans1 = 0
ans2 = 0
#print(u,d)
for i in range(n):
    ans1 += abs(a[i] - (u + i))
    ans2 += abs(a[i] - (d + i))
print(min(ans1,ans2))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int ,input().split()))
d = min(a)-len(a) - len(a)
u = max(a) * 2

while u-d > 1:
    mid = (d + u) // 2
    val = 0
    for i in range(n):
        val += a[i] - (mid + i+1)
    if val <= 0:
        u = mid
    else:
        d = mid
ans1 = 0
ans2 = 0
#print(u,d)
for i in range(n):
    ans1 += abs(a[i] - (u + i+1))
    ans2 += abs(a[i] - (d + i+1))
print(min(ans1,ans2))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int ,input().split()))
d = min(a)-len(a) - len(a)
u = max(a) * 2

while u-d > 1:
    mid = (d + u) // 2
    val = 0
    for i in range(n):
        val += a[i] - (mid + i+1)
    if val < 0:
        u = mid
    else:
        d = mid
ans1 = 0
ans2 = 0
#print(u,d)
for i in range(n):
    ans1 += abs(a[i] - (u + i+1))
    ans2 += abs(a[i] - (d + i+1))
print(min(ans1,ans2))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int ,input().split()))
d = min(a)-len(a) - len(a)
u = max(a) * 2

while abs(u-d) > 1:
    mid = (d + u) // 2
    val = 0
    for i in range(n):
        val += a[i] - (mid + i+1)
    if val < 0:
        u = mid
    else:
        d = mid
ans1 = 0
ans2 = 0
#print(u,d)
for i in range(n):
    ans1 += abs(a[i] - (u + i+1))
    ans2 += abs(a[i] - (d + i+1))
print(min(ans1,ans2))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int ,input().split()))
d = min(a)-len(a)-1
u = max(a)+1

while abs(u-d) > 1:
    mid = (d + u) // 2
    val = 0
    for i in range(n):
        val += a[i] - (mid + i+1)
    if val < 0:
        u = mid
    else:
        d = mid
ans1 = 0
ans2 = 0
#print(u,d)
for i in range(n):
    ans1 += abs(a[i] - (u + i+1))
    ans2 += abs(a[i] - (d + i+1))
print(min(ans1,ans2))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int ,input().split()))
d = min(a)-len(a)
u = max(a)

while abs(u-d) > 1:
    mid = (d + u) // 2
    val = 0
    for i in range(n):
        val += a[i] - (mid + i+1)
    if val < 0:
        u = mid
    else:
        d = mid
ans1 = 0
ans2 = 0
#print(u,d)
for i in range(n):
    ans1 += abs(a[i] - (u + i+1))
    ans2 += abs(a[i] - (d + i+1))
print(min(ans1,ans2))

Submission status: Wrong Answer

Solution code:

from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
import numpy as np
from functools import reduce

from collections import deque, Counter, defaultdict
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
import statistics
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
def lcm(a, b):
  return a*b//gcd(a, b)

def main():
  n = int(readline())
  a = np.array(readline().split(), dtype='int64')
  for i in range(n):
    a[i] -= i+1
  median = np.median(a)
  a -= median
  print(np.abs(a).sum())
  
  
  
  
  
if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
a = np.array([int(x) for x in input().split()])
for i in range(n):
  a[i] -= i+1

key = np.sum(a)//n
p = np.sum(np.abs(a-key))
q = np.sum(np.abs(a-key-1))
r = q = np.sum(np.abs(a-key+1))
print(min([p, q, r]))

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
a = np.array([int(x) for x in input().split()])
for i in range(n):
  a[i] -= i+1

key = np.sum(a)//n
p = np.sum(np.abs(a-key))
q = np.sum(np.abs(a-(key-1)))
print(min([p, q]))

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    a = list(map(int, input().split()))
    left = 0
    right = sum(a)
    res = 10**30
    a.sort()
    for i in range(n):
        if i==0:
            right -= a[i]
            res = min(res, abs((right-a[i]*(n-i-1))-(n-i)*(n-i-1)//2))
        elif 0<i<n-1:
            left += a[i-1]
            right -= a[i]
            res = min(res, abs((right-a[i]*(n-i-1))-(n-i)*(n-i-1)//2)+abs((left-a[i]*i)+i*(i+1)//2))
        else:
            left += a[i-1]
            res = min(res, abs((left-a[i]*i)+i*(i+1)//2))
    print(res)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    a = list(map(int, input().split()))
    b = []
    for i in range(n):
        b.append(a[i]-i-1)
    if n%2==0:
        c = b[n//2]
        d = b[n//2-1]
        res1 = 0
        res2 = 0
        for i in b:
            res1 += abs(i-c)
            res2 += abs(i-d)
        print(min(res1, res2))
        exit()
    else:
        c = b[n//2]
        res = 0
        for i in b:
            res += abs(i-c)
        print(res)
        exit()
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    a = list(map(int, input().split()))
    left = 0
    right = sum(a)
    res = 10**30
    for i in range(n):
        if i==0:
            right -= a[i]
            res = min(res, abs((right-a[i]*(n-i-1))-(n-i)*(n-i-1)//2))
        elif 0<i<n-1:
            left += a[i-1]
            right -= a[i]
            res = min(res, abs((right-a[i]*(n-i-1))-(n-i)*(n-i-1)//2)+abs((left-a[i]*i)+i*(i+1)//2))
        else:
            left += a[i-1]
            res = min(res, abs((left-a[i]*i)+i*(i+1)//2))
    print(res)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    a = list(map(int, input().split()))
    left = 0
    right = sum(a)
    res = 10**20
    for i in range(n):
        if i==0:
            right -= a[i]
            res = min(res, abs((right-a[i]*(n-i-1))-(n-i)*(n-i-1)//2))
        elif 0<i<n-1:
            left += a[i-1]
            right -= a[i]
            res = min(res, abs((right-a[i]*(n-i-1))-(n-i)*(n-i-1)//2)+abs((left-a[i]*i)+i*(i+1)//2))
        else:
            left += a[i-1]
            res = min(res, abs((left-a[i]*i)+i*(i+1)//2))
    print(res)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def resolve():
    N = int(input())
    A = list(map(int, input().split(" ")))
    Adiff = sorted([a - i for i, a in enumerate(A)])
    if N % 2 == 0:
        print(min((sum([abs(ad - Adiff[N//2]) for ad in Adiff])), sum([abs(ad - Adiff[N//2+1]) for ad in Adiff])))
    else:
        print(sum([ad - Adiff[N//2] for ad in Adiff]))

if '__main__' == __name__:
    resolve()

Submission status: Wrong Answer

Solution code:
from statistics import median

N = int(input())
items = list(map(int, input().split()))
items = [item - (k+1) for k, item in enumerate(items)]
medi = median(items)
ans_m  = [int(abs(item - medi)) for item in items]
print(sum(ans_m))

Submission status: Wrong Answer

Solution code:
from statistics import median

N = int(input())
items = list(map(int, input().split()))
items = [item - (k+1) for k, item in enumerate(items)]
medi = median(items)
ans_m  = [abs(item - medi) for item in items]
print(sum(ans_m))

Submission status: Wrong Answer

Solution code:
from statistics import mean

N = int(input())
items = list(map(int, input().split()))
items = [item - (k+1) for k, item in enumerate(items)]
m = int(mean(items))
ans_m  = [abs(item - m) for item in items]
ans_m1 = [abs(item - (m+1)) for item in items]
ans_mm1 = [abs(item - (m-1)) for item in items]
print(min(sum(ans_m), sum(ans_m1), sum(ans_mm1)))

Submission status: Wrong Answer

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

sad = 0
for i in range(n):
    sad += a[i]
b = sad // n

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

print(res)

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=sum(B)//N
ans1=0
for i in range(N):
  ans1+=abs(B[i]-b)

b+=1
ans2=0
for i in range(N):
  ans2+=abs(B[i]-b)
ans=min(ans1,ans2)
print(ans)

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=sum(B)//N
ans=0
for i in range(N):
  ans+=abs(B[i]-b)
print(ans)

Submission status: Wrong Answer

Solution code:
#!python3

import numpy as np


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


def main():
    w = np.array(A) - np.arange(1, N + 1)
    w.sort()
    s = w.sum()
    x = s // N
    ans = min(abs(w - x).sum(), abs(w - x - 1).sum())
    print(ans)
        

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
Alist = list(map(int,input().split()))
Blist = []
p = 0
q = 0
r = 0
for i in range(N):
    Blist.append(Alist[i] - i- 1)
for i in range(N):
    p = p + Blist[i]
s = [p//N,p//N+1]
for j in range(N):
    q = q + abs(Blist[j] - s[0])
for j in range(N):
    r = r + abs(Blist[j] - s[0])
g = [q,r]
print(min(g))

Submission status: Wrong Answer

Solution code:

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

mean = 0

for i in range(n):
    mean += a[i] - (i + 1)
if mean < 0:
    b = int(mean // n)
else:
    b = int(mean / n + 0.5)
ans = 0
for i in range(n):
    ans += abs(a[i] - (b + i + 1))

print(ans)

Submission status: Wrong Answer

Solution code:

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

mean = 0

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

b = int(mean / n + 0.5)
ans = 0
for i in range(n):
    ans += abs(a[i] - (b + i + 1))

print(ans)

Submission status: Wrong Answer

Solution code:

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

mean = 0

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = [int(x) - int(i) for i, x in enumerate(input().split(), 1)]
b = sum(A)//n
res1 = 0
for a in A:
  res1 += abs(a - b)
b += 1
res2 = 0
for a in A:
  res2 += abs(a - b)
print(min(res1, res2))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

#y seppen wo motomeru

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

m=min(I)
M=max(I)

opp=10**100
for i in range(m, M+1):
    #print(i)
    temp=sum([abs(val-i) for val in I])
    if temp<opp:
        opp=temp
print(1, opp)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
for i in range(n):
    a[i]-=(i+1)
median=-1
if n%2==0:
    median=(a[n//2]+a[n//2-1])//2
else:
    median=a[n//2]
def comp(x):
    su=0
    for i in a:
        su+=abs(i-x)
    return su
print(min(comp(median-1),comp(median),comp(median+1)))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
for i in range(n):
    a[i]-=(i+1)
median=-1
if n%2==0:
    median=(a[n//2]+a[n//2-1])//2
else:
    median=a[n//2]
def comp(x):
    su=0
    for i in a:
        su+=abs(i-x)
    return su
print(min(comp(median),comp(median+1)))

Submission status: Wrong Answer

Solution code:


def solve():
    N = int(input())
    As = list(map(int, input().split()))

    Bs = []

    for i in range(N):
        Bs.append(As[i]-i-1)

    Bs.sort()
    b = Bs[N//2]

    ans = 0

    for i in range(N):
        ans += Bs[i]-b

    print(ans)


# Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

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

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

print(s)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
ans1 = 0
ans2 = 0
ans3 = 0
for i in range(n):
    a[i] -= i-1
b = sum(a) // n
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:
n = int(input())
a = list(map(int, input().split()))
s = 0
ans1 = 0
ans2 = 0
for i in range(n):
    a[i] -= i
b = sum(a) // n
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:
n = int(input())
a = list(map(int, input().split()))
s = 0
ans = 0
for i in range(n):
    a[i] -= i
b = round(sum(a)/n)
for i in range(n):
    ans += abs(a[i]-b)

print(ans)

Submission status: Wrong Answer

Solution code:
# import bisect
# from collections import Counter, deque
# import copy
# from fractions import gcd
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
import numpy as np
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline

def resolve():
    N=int(input())
    A=np.array(list(map(int,input().split())))

    B=np.array([i for i in range(1,N+1)])

    A=A-B


    val1 = 0
    val2=0
    for i in A:
        val1 += abs(i - 1)
        val2+=abs(i+1)
    if val1<val2:

        minval = 10 ** 50
        temp = 10**50
        for j in range(abs(sum(A))):
            val=0
            for i in A:
                val+=abs(i-j)
            if val>=temp:
                break
            else:
                temp=val
                minval=min(minval,val)

    else:

        minval = 10 ** 50
        temp = 10**50
        for j in range(abs(sum(A))):
            val=0
            for i in A:
                val+=abs(i+j)
            if val>=temp:
                break
            else:
                temp=val
                minval=min(minval,val)
    print(minval)
resolve()

Submission status: Wrong Answer

Solution code:
# import bisect
# from collections import Counter, deque
# import copy
# from fractions import gcd
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
import numpy as np
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline

def resolve():
    N=int(input())
    A=np.array(list(map(int,input().split())))

    B=np.array([i for i in range(1,N+1)])

    A=A-B


    val1 = 0
    val2=0
    for i in A:
        val1 += abs(i - 1)
        val2+=abs(i+1)
    if val1<val2:

        minval = 10 ** 50
        temp = 10**50
        for j in range(sum(A)):
            val=0
            for i in A:
                val+=abs(i-j)
            if val>=temp:
                break
            else:
                temp=val
                minval=min(minval,val)

    else:

        minval = 10 ** 50
        temp = 10**50
        for j in range(sum(A)):
            val=0
            for i in A:
                val+=abs(i+j)
            if val>=temp:
                break
            else:
                temp=val
                minval=min(minval,val)
    print(minval)
resolve()

Submission status: Wrong Answer

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

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

    minval = 10 ** 10
    j=0
    temp = 10**10
    while True:
        val=0
        for i in A:
            val+=abs(i-j)
        if val>=temp:
            break
        else:
            temp=val
            minval=min(minval,val)
            j+=1

    minval = 10 ** 10
    j=0
    temp = 10**10
    while True:
        val=0
        for i in A:
            val+=abs(i+j)
        if val>=temp:
            break
        else:
            temp=val
            minval=min(minval,val)
            j+=1
    print(minval)
resolve()

Submission status: Wrong Answer

Solution code:
# import bisect
# from collections import Counter, deque
# import copy
# from fractions import gcd
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
import numpy as np
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline

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

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

    minval = 10 ** 10
    j=0
    temp = 10**10
    while True:
        val=0
        for i in A:
            val+=abs(i-j)
        if val>=temp:
            break
        else:
            temp=val
            minval=min(minval,val)
            j+=1

    minval = 10 ** 10
    j=0
    temp = 10**10
    while True:
        val=0
        for i in A:
            val+=abs(i+j)
        if val>=temp:
            break
        else:
            temp=val
            minval=min(minval,val)
            j+=1
    print(minval)
resolve()

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)

m1 = sum(a)//n
m2 = -(-sum(a)//n)

ans1 = 0
ans2 = 0

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

print(min(ans1,ans2))

Submission status: Wrong Answer

Solution code:
import numpy as np

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

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

b = sum(ind_B) // len(ind_B)

ABS = []
for j in ind_B:
  abs = np.abs(j - b)
  ABS.append(abs)

sum = sum(ABS)
print(sum)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter
def input(): return sys.stdin.readline().rstrip()

def main():
    N = int(input())
    A = map(int, input().split())
    A = [a - i - 1 for i, a in enumerate(A)]
    A_plus = [a for a in A if a >= 0]
    A_minus = [a for a in A if a < 0]

    ans = 10 ** 9
    if len(A_plus):
        A_plus_counter = Counter(A_plus).most_common()[0]
        if A_plus_counter[1] == 1:
            ans = sum([abs(i) for i in A])
        else:
            most_v = A_plus_counter[0]
            ans = sum([abs(i - most_v) for i in A])
    if len(A_minus):
        A_minus_Counter = Counter(A_minus).most_common()[0]
        if A_minus_Counter[1] == 1:
            ans = min(ans, sum([abs(i) for i in A]))
        else:
            most_v = A_minus_Counter[0]
            ans = min(ans, sum([abs(i - most_v) for i in A]))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter
def input(): return sys.stdin.readline().rstrip()

def main():
    N = int(input())
    A = map(int, input().split())
    A = [v - i - 1 for i, v in enumerate(A)]
    A_counter = Counter(A).most_common()[0]
    if A_counter[1] == 1:
        print(sum([abs(i) for i in A]))
    else:
        most_v = A_counter[0]
        print(sum([abs(i - most_v) for i in A]))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
import statistics
N = int(input())
L = [i for i in map(int,input().split())]
Q = []
for i in range(len(L)):
  Q.append(L[i] - (i+1))
b = statistics.median(Q)
a = b - 1
c = b + 1
res = 0
res2 = 0
res3 = 0
for i in range(N):
  res += abs(L[i] - (i+1) - b)
  res2 += abs(L[i] - (i+1) - a)
  res3 += abs(L[i] - (i+1) - c)
print(min(res,res2,res3))

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
L = [i for i in map(int,input().split())]
b = 0
res = 0
res2 = 0
res3 = 0
for i in range(N):
  b += L[i] - (i+1)
b = math.floor(b/N)
a = b-1
c = b+1
for i in range(N):
  res += abs(L[i] - (i+1) - a)
  res2 += abs(L[i] - (i+1) - b)
  res3 += abs(L[i] - (i+1) - c)
print(min(res,res2,res3))

Submission status: Wrong Answer

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

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

ave = sum(A) // N
ans = float('inf')
for i in range(-5, 6):
    cnt = 0
    for a in A:
        cnt += abs(a - (ave + i))
    ans = min(cnt, ans)

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

ave = sum(A) // N
ans1 = 0
ans2 = 0
ans3 = 0
for a in A:
    ans1 += abs(a - ave)
    ans2 += abs(a - (ave + 1))
    ans3 += abs(a - (ave - 1))

print(min(ans1, min(ans2, ans3)))