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:
#!/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, 200_000
    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))
    lb, ub = -200_000, 200_000
    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:
N = int(input())
A = list(map(int, input().split()))
B = []
for i in range(N):
    B.append(abs(A[i] - (i + 1)))
B.sort()
if N % 2:
    median = B[N // 2]
    print(sum(abs(b - median) for b in B))
else:
    median1 = B[N // 2 - 1]
    median2 = B[N // 2]
    print(min(sum(abs(b - median1) for b in B), sum(abs(b - median2) for b in B)))

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(sum(a[-(n//2):])-sum(a[:n//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
s=sum(a)//n
ans_1=0
ans_2=0
for i in range(n):
    ans_1+=abs(a[i]-s)
    ans_2+=abs(a[i]-s-1)
ans=min(ans_1,ans_2)
print(ans)

Submission status: Wrong Answer

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""
def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# a^n
def power(a,n,mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod

# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n-1
    while(tmp >= l):
        a = a*tmp%mod
        tmp -= 1
    return a

inf = 10**18
mod = 10**9+7

n = ir()
a = lr()
total = 0
for i,num in enumerate(a):
    a[i]=(num-(i+1))
if n%2 == 0:
    mean = (a[n//2-1]+a[n//2])//2
else:
    mean = a[n//2]
ans = [0,0]
for i in range(mean, mean+2):
    tmp = i%2
    for num in a:
        ans[tmp]+=abs(num-i)
print(min(ans))

Submission status: Wrong Answer

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""
def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# a^n
def power(a,n,mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod

# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n-1
    while(tmp >= l):
        a = a*tmp%mod
        tmp -= 1
    return a

inf = 10**18
mod = 10**9+7

n = ir()
a = lr()
total = 0
for i,num in enumerate(a):
    a[i]=(num-(i+1))
mean = sum(a)//n-1
ans = [0,0,0]
for i in range(mean, mean+3):
    tmp = i%3
    for num in a:
        ans[tmp]+=abs(num-i)
print(min(ans))

Submission status: Wrong Answer

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""
def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# a^n
def power(a,n,mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod

# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n-1
    while(tmp >= l):
        a = a*tmp%mod
        tmp -= 1
    return a

inf = 10**18
mod = 10**9+7

n = ir()
a = lr()
total = 0
for i,num in enumerate(a):
    total+=(num-(i+1))
mean = total//n-1
ans = [0,0,0]
for i in range(mean, mean+3):
    tmp = i%3
    for j,num in enumerate(a):
        ans[tmp]+=abs((num-(j+1))-i)
print(min(ans))

Submission status: Wrong Answer

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""
def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# a^n
def power(a,n,mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod

# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n-1
    while(tmp >= l):
        a = a*tmp%mod
        tmp -= 1
    return a

inf = 10**18
mod = 10**9+7

n = ir()
a = lr()
total = 0
for i,num in enumerate(a):
    total+=(num-(i+1))
mean = total//n
ans = [0,0]
for i in range(mean, mean+2):
    tmp = i%2
    for j,num in enumerate(a):
        ans[tmp]+=abs((num-(j+1))-i)
print(min(ans))

Submission status: Wrong Answer

Solution code:
import math

def isinteger(n):
    if isinstance(n, int):
        return True
    elif isinstance(n,float):
        return n.is_integer()
    return False

n = int(input())
A = list(map(int,input().split()))
for i in range(1,n+1):
    A[i-1] = A[i-1]-i
A.sort()
if n == 1:
    print(0)
    exit()
if n % 2 == 1:
    b = A[(n-1)//2]
else:
    b = (A[n//2]+A[n//2-1])/2
if isinteger(b):
    ans = 0
    for i in A:
        ans += abs(i-b)
    print(ans)
else:
    ans1=0
    ans2=0
    b1= math.floor(b)
    b2=b1+1
    for i in A:
        ans1 += abs(i-b1)
        ans2 += abs(i-b2)
    print(min(ans1,ans2))

Submission status: Wrong Answer

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

A = [a-i-1 for i, a in enumerate(A)]
i = len(A)//2
b = A[i]

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

Submission status: Wrong Answer

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

A = [a-i-1 for i, a in enumerate(A)]
i = int(len(A)/2)
b = A[i]

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

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
n = int(input())
arr = np.array(list(map(int, input().split())))

comp = np.arange(n) + 1

diff = arr - comp

if np.all(diff >= 0):
    print(diff.sum())
    sys.exit()

sei = diff[np.where(diff >= 0)]
fu = diff[np.where(diff < 0)]

while sei.shape[0] < fu.shape[0]:
    add = fu.max()
    diff -= add
    sei = diff[np.where(diff >= 0)]
    fu = diff[np.where(diff < 0)]

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

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
n = int(input())
arr = np.array(list(map(int, input().split())))

comp = np.arange(n) + 1

diff = arr - comp

if np.all(diff >= 0):
    print(diff.sum())
    sys.exit()

sei = diff[np.where(diff >= 0)]
fu = diff[np.where(diff < 0)]

if sei.sum() >= np.abs(fu).sum():
    print(sei.sum() + np.abs(fu).sum())
    sys.exit()

while sei.shape[0] < fu.shape[0]:
    add = fu.max()
    diff -= add
    sei = diff[np.where(diff >= 0)]
    fu = diff[np.where(diff < 0)]

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

Submission status: Wrong Answer

Solution code:
n=int(input())
*a, =map(int,input().split())
a=[a[i]-(i+1) for i in range(n)]
a=sorted(a)
c1=sum(a)//n
c2=c1+1
ans=float('inf')

for c in [c1,c2]:
    tmp=0
    for i in range(n):
        tmp+=abs(a[i]-c)
    ans=min(ans, tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
#import sys
#import numpy as np
#import math
#import itertools
#from fractions import Fraction
#import itertools
from collections import deque
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
import bisect

n=int(input())
a=list(map(int,input().split()))
c=[0]*n
for i in range(n):
    c[i]=a[i]-(i+1)
s=sum(c)
b=s//n
ans1=ans2=0
for i in range(n):
    ans1+=abs(c[i]-b)
b+=1
for i in range(n):
    ans2+=abs(c[i]-b)
print(min(ans1,ans2))

Submission status: Wrong Answer

Solution code:
#import sys
#import numpy as np
#import math
#import itertools
#from fractions import Fraction
#import itertools
from collections import deque
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
import bisect

n=int(input())
a=list(map(int,input().split()))
c=[0]*n
for i in range(n):
    c[i]=a[i]-(i+1)
s=sum(c)
b=s//n
print(b,c)
ans1=ans2=0
for i in range(n):
    ans1+=abs(c[i]-b)
b+=1
for i in range(n):
    ans2+=abs(c[i]-b)
print(min(ans1,ans2))

Submission status: Wrong Answer

Solution code:
#import sys
#import numpy as np
#import math
#import itertools
#from fractions import Fraction
#import itertools
from collections import deque
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
import bisect

n=int(input())
a=list(map(int,input().split()))
c=[0]*n
for i in range(n):
    c[i]=a[i]-(i+1)
s=sum(c)
b=s//n
ans1=ans2=0
for i in range(n):
    ans1+=abs(c[i]-b)
b=+1
for i in range(n):
    ans2+=abs(c[i]-b)
print(min(ans1,ans2))

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:
    ans1=0
    ans2=0
    b=(B[N//2-1]+B[N//2])//2
    for i in range(N):
        ans1+=abs(A[i]-b)
        ans2+=abs(A[i]-b-i-1)
    ans=min(ans1,ans2)
else:
    ans=0
    b=B[N//2]
    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()))

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

b = [sum(c)//n, sum(c)//n+1]

ans = float("inf")
for i in b:
    res = 0
    for j in range(n):
        res += abs(c[j] - i)
    ans = min(ans, res)

print(ans)

Submission status: Wrong Answer

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

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

b = sum(c) // n
ans = 0
for i in range(n):
    ans += abs(c[i] - b)

print(ans)

Submission status: Wrong Answer

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

g=[0,0]
for i in range(N):
    g[0]+=i+1
    g[1]+=A[i]
g[0]/=N
g[1]/=N

B=int(g[1]-g[0])
b=[]
for n in range(21):
    b.append(B-10+n)

ans=[0 for _ in range(21)]
for j in range(N):
    for k in range(21):
        ans[k]+=abs(A[j]-j-1-b[k])
print(min(ans))

Submission status: Wrong Answer

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

g=[0,0]
for i in range(N):
    g[0]+=i+1
    g[1]+=A[i]
g[0]/=N
g[1]/=N

B=int(g[1]-g[0])
b=[B-1,B,B+1]

ans=[0,0,0]
for j in range(N):
    for k in range(3):
        ans[k]+=abs(A[j]-j-1-b[k])
print(min(ans))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
import itertools
import math
# import networkx as nx
from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop
n=n0()
A=n1()

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

avg=sum(A2)/n
x=int(avg)

y=x+1
z=x-1
ans=min(sum([abs(A[i-1]-i-x) for i in range(1,n+1)]),sum([abs(A[i-1]-i-y) for i in range(1,n+1)]),
        sum([abs(A[i-1]-i-z) for i in range(1,n+1)]))

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

b.sort()

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

c = []
for i in range(n):
    c.append(abs(b[i] - median))

print(sum(c))

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/arc100/tasks/arc100_a

n = int(input())
nums = [int(i) for i in input().split()]




def sadness(nums, b):
    s = 0
    for i in range(len(nums)):
        s += abs(nums[i] - (b + i + 1))
    return s

ans = float('inf')
l = 0
r = 10 ** 9
while l <= r:
    mid = (l + r) // 2
    t = sadness(nums, mid)
    if t <= ans:
        ans = t
        r = mid - 1
    else:
        l = mid + 1

l = -1 * 10 ** 9
r = 0
while l <= r:
    mid = (l + r) // 2
    t = sadness(nums, mid)
    if t <= ans:
        ans = t
        r = mid - 1
    else:
        l = mid + 1
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N, A = int(input()), list(map(int, input().split()))
    for i in range(N):
        A[i] -= i + 1
    ave = sum(A) // N
    a, b = ave, ave + 1
    c, d = 0, 0
    _abs = abs
    for el in A:
        c += _abs(el-a)
        d += _abs(el-b)
    print(min(c, d))
main()

Submission status: Wrong Answer

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

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

su = sum(s)
a, b = divmod(su, n)

res = 0
for ss in s:
    res += abs(ss - a)
print(res)

Submission status: Wrong Answer

Solution code:
N=int(input())
L=list(map(int,input().split()))
L=[j-i for i,j in enumerate(L,1)]
L.sort()
A=(L[N//2]+L[(N-1)//2])//2
print(sum([i-A for i in L]))

Submission status: Wrong Answer

Solution code:
N=int(input())
L=list(map(int,input().split()))
L=[j-i for i,j in enumerate(L,1)]
L_a=sorted(L)
if len(L)%2==1:
   C=L_a[len(L)//2]
   L=[i-C for i in L]
   print(sum(L))
else:
   C=L_a[len(L)//2-1]
   C2=L_a[len(L)//2]
   C=sum([abs(i-C) for i in L])
   C2=sum([abs(i-C2) for i in L])
   print(min(C,C2))

Submission status: Wrong Answer

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

sum = 0
for i in A:
    sum += abs(i-median)
print(sum)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
a = sum(A) // N
b1 = a - N // 2
b2 = a + 1 - N // 2
b3 = a - 1 - N // 2

ans1 = 0
ans2 = 0
ans3 = 0

for i in range(N):
    ans1 += abs(A[i] - (b1 + 1 + i))
    ans2 += abs(A[i] - (b2 + 1 + i))
    ans3 += abs(A[i] - (b3 + 1 + i))
print(min(ans1, ans2, ans3))

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

n = INT()
a = LIST()
c = [a[i] - i - 1 for i in range(n)]
tmp = sum(c)
mn = tmp // n
ans = inf
for j in range(mn - 10, mn + 10):
    ans = min(ans, sum([abs(c[i] - j) for i in range(n)]))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

n = INT()
a = LIST()
c = [a[i] - i - 1 for i in range(n)]
tmp = sum(c)
mn = tmp // n
mx = mn + 1
ans1 = [abs(c[i] - mn) for i in range(n)]
ans2 = [abs(c[i] - mx) for i in range(n)]
print(min(sum(ans1), sum(ans2)))

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_ave = sum(a) / n
if b_ave - int(b_ave) > 0.5:
    b = int(b_ave) + 1
else:
    b = int(b_ave)
ans = 10 ** 18
# print(b_ave, b)
for k in range(b - 2, b + 3):
    tmp = 0
    for i in range(n):
        tmp += abs(a[i] - k)
    ans = min(ans, tmp)
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
b_ave = sum(a) / n
if b_ave - int(b_ave) > 0.5:
    b = int(b_ave) + 1
else:
    b = int(b_ave)
ans = 10 ** 11
# print(b_ave, b)
for k in range(b - 100, b + 100):
    tmp = 0
    for i in range(n):
        tmp += abs(a[i] - k)
    ans = min(ans, tmp)
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
b_ave = sum(a) / n
if b_ave - int(b_ave) > 0.5:
    b = int(b_ave) + 1
else:
    b = int(b_ave)
ans = 10 ** 9
# print(b_ave, b)
for k in range(b - 3, b + 3):
    tmp = 0
    for i in range(n):
        tmp += abs(a[i] - k)
    ans = min(ans, tmp)
print(ans)

Submission status: Wrong Answer

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

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

SUM = sum(B)
J = [SUM//N,SUM//N+1]
MIN = 10**18
for j in J:
    ans = 0
    for i in B:
        ans += abs(i-j)

    MIN = min(ans,MIN)

print(MIN)

Submission status: Wrong Answer

Solution code:
import math

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

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

m = 100000000000

Average = math.floor(sum(A)/len(A))

min = Average-100 
max = Average+100

for i in range (min, max):
	b=0
	for j in range (0, N):
		b+=abs(A[j]-i)
	if b < m:
		m = b

print(m)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    for i in range(N):
        A[i] -= i+1
    avg = sum(A)//N
    print(sum(abs(a-avg) for a in A))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())

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

v1 = []

v2 = []

q = 0

for i in v:
    if q == 0:
        v1.append(i)
        q = 1
    else:
        v2.append(i)
        q = 0
        
maxv1 = 0

maxv2 = 0

for i in set(v1):
    a = tuple(v1).count(i)
    if a>maxv1:
        maxv1 = a
        
for i in set(v2):
    b = tuple(v2).count(i)
    if b>maxv2:
        maxv2 = b
        
if v1 == v2:
    print(n//2)
else:
    print(n-maxv1-maxv2)

Submission status: Wrong Answer

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

ave = sum(B)//N
ans1,ans2,ans3 = 0,0,0
for i in range(N):
    ans1 += abs(B[i]-ave)
    ans2 += abs(B[i]-ave-1)
    ans3 += abs(B[i]-ave+1)
print(min(ans1,ans2,ans3))

Submission status: Wrong Answer

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

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

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)
c=sum(b)//n

ans=1000000000000000000000
for i in range(c-50,c+50):
  temp=0
  for j in range(n):
    temp+=abs(b[j]-i)
  if temp<ans:
    ans=temp
print(ans)

Submission status: Wrong Answer

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

sad = float("inf")
for b in lb:
  c = 0
  for j in range(N):
    c += abs( A[j]-(b+j+1) )
  sad = min(sad,c)
print(sad)

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)
c=sum(b)//n

ans=1000000000000000000000
for i in range(c-3,c+3):
  temp=0
  for j in range(n):
    temp+=abs(b[j]-i)
  if temp<ans:
    ans=temp
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
#%%code
def resolve():
    N,=pin()
    A=tupin()
    B=[A[i]-i-1 for i in range(N)]
    #print(B)
    
    d=range(B[N//2]-10**3,B[N//2]+10**3)

    
    c=10**10
    point=-1
    for b in d:
        temp=0
        for x in B:
            temp+=abs(x-b)
        if temp<c:
            point=b
            c=temp
            #print(b,temp)
    print(c)
    
    """
    c=10**10
    point=-1
    for b in range(min(B),max(B)+1):
        temp=0
        for x in B:
            temp+=abs(x-b)
        if temp<c:
            point=b
            c=temp
            print(b,temp)
    """
    
#%%submit!
resolve()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
#%%code
def resolve():
    N,=pin()
    A=tupin()
    B=[A[i]-i-1 for i in range(N)]
    B.sort()
    if N%2:
        d=[B[N//2]]
    else:d=[B[N//2-1],B[N//2]]

    
    c=10**10
    point=-1
    for b in d:
        temp=0
        for x in B:
            temp+=abs(x-b)
        if temp<c:
            point=b
            c=temp
            #print(b,temp)
    print(c)
    """
    c=10**10
    point=-1
    for b in range(min(B),max(B)+1):
        temp=0
        for x in B:
            temp+=abs(x-b)
        if temp<c:
            point=b
            c=temp
            print(b,temp)
    """
#%%submit!
resolve()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
#%%code
def resolve():
    N,=pin()
    A=tupin()
    B=[A[i]-i-1 for i in range(N)]
    
    if N%2:
        d=[B[N//2]]
    else:d=[B[N//2-1],B[N//2]]

    
    c=10**10
    point=-1
    for b in d:
        temp=0
        for x in B:
            temp+=abs(x-b)
        if temp<c:
            point=b
            c=temp
            #print(b,temp)
    print(c)
    """
    c=10**10
    point=-1
    for b in range(min(B),max(B)+1):
        temp=0
        for x in B:
            temp+=abs(x-b)
        if temp<c:
            point=b
            c=temp
            print(b,temp)
    """
#%%submit!
resolve()

Submission status: Wrong Answer

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

import bisect
n = inn()
a = inl()
c = [a[i]-i-1 for i in range(n)]
c.sort()
b = sum(c)//n
p = bisect.bisect_left(c,b)
q = bisect.bisect_right(c,b)
s = []
if 0<=p<n:
    s.append(sum([abs(c[i]-c[p]) for i in range(n)]))
if 0<=p-1<n:
    s.append(sum([abs(c[i]-c[p-1]) for i in range(n)]))
if 0<=q<n and p!=q:
    s.append(sum([abs(c[i]-c[q]) for i in range(n)]))
if 0<=q+1<n:
    s.append(sum([abs(c[i]-c[q+1]) for i in range(n)]))
print(min(s))

Submission status: Wrong Answer

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
a = inl()
c = [a[i]-i-1 for i in range(n)]
b = sum(c)//n
x = sum([abs(c[i]-b) for i in range(n)])
y = sum([abs(c[i]-b-1) for i in range(n)])
z = sum([abs(c[i]-b+1) for i in range(n)])
print(min([x,y,z]))

Submission status: Wrong Answer

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
a = inl()
c = [a[i]-i-1 for i in range(n)]
b = sum(c)//n
x = sum([abs(c[i]-b) for i in range(n)])
y = sum([abs(c[i]-b-1) for i in range(n)])
print(min(x,y))

Submission status: Wrong Answer

Solution code:
def main():
    N, *A = map(int, open(0).read().split())
    X, Y = 0, 0
    for i in range(N):
        a = A[i] - i - 1
        X += a
        Y += a**2
    b = X // N
    # print(X, Y, b)
    ans1 = ans2 = 0
    sign = 1 if X >= 0 else -1
    for i in range(N):
        a = A[i] - i - 1
        ans1 += abs(a - b)
        ans2 += abs(a - b - sign)
    print(min(ans1, ans2))

if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
def main():
    N, *A = map(int, open(0).read().split())
    X, Y = 0, 0
    for i in range(N):
        a = A[i] - i - 1
        X += a
        Y += a**2
    b = X // N
    # print(X, Y, b)
    ans1 = ans2 = 0
    for i in range(N):
        a = A[i] - i - 1
        ans1 += abs(a - b)
        ans2 += abs(a - b - 1)
    print(min(ans1, ans2))

if __name__ == '__main__':
  main()