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 collections
import numpy
n=int(input())
a=numpy.array([int(x)-i for (x,i) in zip(input().split(), range(1,n+1))])
c = collections.Counter(a)
b =c.most_common()[0][0]
a-=b
print(a.sum())

Submission status: Wrong Answer

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

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

b.sort()
s = 0
co = 0
ss = 0
coco = 0
cococo = 0
summ = 0
for i in range(a):
	if b[i] < 0:
		s += b[i]
		co += 1
	elif b[i] > 0:
		ss += b[i]
		coco += 1
	else:
		cococo += 1


if cococo == a:
	summ = 0

elif co == coco and abs(s) == abs(ss):
	for i in range(a):
		summ += abs(b[i])

elif co > coco:
	for i in range(a):
		if s != 0:
			summ += abs(b[i] - (s//(co+cococo)))
elif co < coco:
	for i in range(a):
		if ss != 0:
			summ += abs(b[i] - (ss//(coco+cococo)))

print(summ)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):

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

    
    def sk(b):
        s = 0
        for i, a in enumerate(A):
            s += abs(a-(b+i+1))
        return s

    # for i in range(-10, 10):
    #     print(i, sk(i))

    s = -int(1e+9)
    e = int(1e+9)
    ssk = sk(s)
    esk = sk(e)
    # print(s, ssk)
    # print(e, esk)
    while abs(s - e) > 1:
        m = (s+e)//2
        msk = sk(m)
        # print(m, msk)
        if ssk < esk:
            esk = msk
            e = m
        else:
            ssk = msk
            s = m
    
    return min(sk(s), sk(e))


def main():
    N = read_int()
    A = read_int_n() 
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N= map(int, raw_input().split())
 
num = N[0]
a = []
a.append(map(int, raw_input().split()))
 
A = a[0]

B = [i+1 for i in range(num)]

sum =0
for i in range(num):
  sum = sum + A[i]-B[i]

ave = sum/7

total = 0
for i in range(num):
    total = total + abs(A[i]-B[i]-ave)

ans = total
    
total1 = 0
total2 = 0
for i in range(num):
  ave1 = ave +i
  ave2 = ave -i
  for i in range(num):
    total1 = total1 + abs(A[i]-B[i]-ave1)
    total2 = total2 + abs(A[i]-B[i]-ave2)
    
    if total<= total1 and total<= total2:
      ans = total
    
    if total1 <= total and total1 <= total2:
      ans = total1
    if total2 <= total and total2 <= total1:
      ans = total2

    



print ans

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):

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

    
    def sk(b):
        s = 0
        for i, a in enumerate(A):
            s += abs(a-(b+i+1))
        return s

    # for i in range(-10, 10):
    #     print(i, sk(i))

    s = -max(map(abs, A))
    e = max(map(abs, A))
    ssk = sk(s)
    esk = sk(e)
    # print(s, ssk)
    # print(e, esk)
    while abs(s - e) > 1:
        m = (s+e)//2
        msk = sk(m)
        # print(m, msk)
        if ssk < esk:
            esk = msk
            e = m
        else:
            ssk = msk
            s = m
    
    return min(sk(s), sk(e))


def main():
    N = read_int()
    A = read_int_n() 
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

def f(a, n):
    res = 9999999999999999999
    for b in range(-n-1, n+1):
        s = (b+i for i in range(1, n+1))
        sadness = sum(abs(ai - xi) for (ai, xi) in zip(a, s))
        res = min(res, sadness)
    
    return res
    
n = int(input())
a = [int(i) for i in input().split()]
print(f(a, n))

Submission status: Wrong Answer

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

mn = round((sum(A) + 1) / len(A) - N / 2)
bb = 0
for b in range(0, N):
    bb = bb + abs((b + mn) - A[b])

print(bb)

Submission status: Wrong Answer

Solution code:

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

aa = []

for i in range(n):
    aa.append(A[i] - 1 - i)
print(aa)
b = int(statistics.median(aa))

ans = 0

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

print(ans)

Submission status: Wrong Answer

Solution code:
def mi():
	return map(int, input().split())

n = list(mi())[0]
a = list(mi())
for i in range(len(a)):
	a[i]-=i+1
s = 0

low = int(-4e9)
high = int(4e9)

mins = 1e20
while low<high:
	mid = (low+high)//2
	s = 0
	for i in range(len(a)):
		s+=abs(a[i]-mid)
	mins = min(s,mins)
	if s<=mins:
		high = mid
	else:
		low = mid+1

print (mins)

Submission status: Wrong Answer

Solution code:
# encoding:utf-8

def main():
	n = int(input())
	nums_raw = list(map(int, input().split()))
	nums = [nums_raw[i] - i for i in range(n)]
	nums.sort()
	ans = search(nums)
	print(sum([abs(nums_raw[i] - (nums[ans] + i)) for i in range(n)]))

def search(nums):
	left = 0
	right = len(nums) - 1
	tmp = 10 ** 10
	while True:
		if calc(nums, left) >= calc(nums, right):
			new = int((left + right)/2)
			left = new
		else:
			new = int((left + right)/2)
			right = new
		if new == tmp:
			return new
		else:
			tmp = new

def calc(nums, i):
	return sum([abs(x - nums[i]) for x in nums])

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

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


def solve(xs):
    ys = [x - i for i, x in enumerate(xs, start=1)]

    def f(z):
        return sum(abs(y - z) for y in ys)

    lb, ub = min(ys), max(ys)
    mid = (lb + ub) // 2
    while ub - lb > 1:
        mid = (lb + ub) // 2
        if f(lb) > f(ub):
            lb = mid
        else:
            ub = mid
    return f(lb)


def main():
    _ = int(input())
    xs = [int(x) for x in input().split()]
    print(solve(xs))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

import array
from bisect import *
from collections import *
import fractions
import heapq 
from itertools import *
import math
import random
import re
import string
import sys

N = int(input())
As = map(int, input().split())

A2s = []
for i, a in enumerate(As):
    A2s.append(a - (i + 1))
A2s.sort()

bigger = []
smaller = []
zero = []

ans = 0
for a2 in A2s:
    ans += abs(a2)
    if a2 > 0:
        bigger.append(a2)
    elif a2 == 0:
        zero.append(a2)
    else:
        smaller.append(-a2)

smaller.sort()

def find_ans(smaller_, zero_num, bigger_num, ans):
    smaller = smaller_[:]
    prev = 0
    while bigger_num + zero_num < len(smaller):
        ans2 = ans + (bigger_num + zero_num) * (smaller[0] - prev) \
             - len(smaller) * (smaller[0] - prev)
        # print("smaller:", smaller)
        # print("ans2:", ans2)
        bigger_num += zero_num
        zero_num = 1
        prev = smaller[0]
        smaller = smaller[1:]
        if ans2 < ans:
            ans = ans2
        else:
            break
    return ans

ans = find_ans(smaller, len(zero), len(bigger), ans)
ans = find_ans(bigger, len(zero), len(bigger), ans)


print(ans)

Submission status: Wrong Answer

Solution code:
N= map(int, raw_input().split())
 
num = N[0]
a = []
a.append(map(int, raw_input().split()))
 
A = a[0]

B = [i+1 for i in range(num)]

sum =0
for i in range(num):
    sum = sum + A[i]-B[i]

ave = sum/7
ave1 = ave +1
ave2 = ave -1


total = 0
for i in range(num):
    total = total + abs(A[i]-B[i]-ave)

total1 = 0
for i in range(num):
    total1 = total1 + abs(A[i]-B[i]-ave1)

total2 = 0
for i in range(num):
    total2 = total2 + abs(A[i]-B[i]-ave2)
    
ans = total
    
if total<= total1 and total<= total2:
    ans = total
    
if total1 <= total and total1 <= total2:
    ans = total1
    
if total2 <= total and total2 <= total1:
    ans = total2


print ans

Submission status: Wrong Answer

Solution code:
import math

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

s_cand = []
b_cand = [math.floor(sum(a_list2) / n), math.ceil(sum(a_list2) / n)]

for b in b_cand:
    s = 0
    for a in a_list2:
        s += abs(a - b)
    s_cand.append(s)
    
print(min(s_cand))

Submission status: Wrong Answer

Solution code:
import statistics
import math

n = int(input())
a = [int(i) - (index+1) for index, i in enumerate(input().split())]

median = statistics.median(a)

abs_total = 0
for i in a:
  abs_total += abs(i)

print(int(abs(abs_total - (abs(median)*n))))

Submission status: Wrong Answer

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

minv = -1
for b in range(min(a) - n + 1, max(a) + 1):
    v = 0
    for j in range(len(a)):
        v += abs(a[j] - (b + j + 1))
    if minv == -1 or minv > v:
        minv = v

print(minv)

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
A = np.array(list(map(int,input().split())))
n = np.array([i for i in range(A.size)])
A = A-n
ave = A.mean()
round = lambda x:int(x*2+1)//2
ave = round(ave)
A = A-ave
A = np.abs(A)
print(A.sum())

Submission status: Wrong Answer

Solution code:
import functools
N = int(input())
A = [int(x) for x in input().split()]
for i,a in enumerate(A):
  A[i] = a - i - 1
ave = functools.reduce(lambda x, y: x + y, A) // N
B0 = functools.reduce(lambda x, y: x + y, [abs(a - ave) for a in A])
B1 = functools.reduce(lambda x, y: x + y, [abs(a - ave - 1) for a in A])
B2 = functools.reduce(lambda x, y: x + y, [abs(a - ave + 1) for a in A])
print(min(B0, B1, B2))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = []
s = 0
for i in range(n):
    b.append(a[i] - (i + 1))
    s += abs(a[i] - (i + 1))
#print(b)
#print(sum(b), round(sum(b)/n))
q = s//n
s_ = 0
s__ = 0
for i in b:
    s_ += abs(i-q)
    s__ += abs(i+q)
print(min(s_, s__))

Submission status: Wrong Answer

Solution code:
import math

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

s = 0
b = math.floor(sum(a_list2) / n)

for a in a_list2:
    s += abs(a - b)
print(s)

Submission status: Wrong Answer

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

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

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

result = 0

for i in b:
    result += abs(num - i)

print(result)

Submission status: Wrong Answer

Solution code:
a=int(input())
b=list(map(int, input().split()))
c=list(range(1,a+1))
d=(sum(b)-sum(c))//a
c2=[i+d for i in c]
c3=[i+d-1 for i in c]
c4=[i+d+1 for i in c]

b2=[abs(b[i]-c2[i]) for i in range(a)]
b3=[abs(b[i]-c2[i]) for i in range(a)]
b4=[abs(b[i]-c2[i]) for i in range(a)]

print(min(sum(b2),sum(b3),sum(b4)))

Submission status: Wrong Answer

Solution code:

def mi():
	return map(int, input().split())

n = list(mi())[0]
a = list(mi())
for i in range(len(a)):
	a[i]-=i+1
s = 0

low = 0
high = int(2e9)

mins = 1e10
while low<high:
	mid = (low+high)//2
	s = 0
	for i in range(len(a)):
		s+=abs(a[i]-mid)
	mins = min(s,mins)
	if s<=mins:
		high = mid
	else:
		low = mid+1
mins1 = 1e10
low = 0
high = int(2e9)
while low<high:
	mid = (low+high)//2
	s = 0
	for i in range(len(a)):
		s+=abs(a[i]+mid)
	mins1 = min(s,mins1)
	if s<=mins1:
		high = mid
	else:
		low = mid+1

print (min(mins, mins1))

Submission status: Wrong Answer

Solution code:
'''input
7
1 1 1 1 2 3 4
'''
n = input()
arr = map(int,raw_input().split())
for i in range(n):
	arr[i] = (arr[i]-(i+1))
mean = float(sum(arr))/n
ans = 10**30
for i in range(int(mean)-30,int(mean)+30):
	q = 0
	for j in range(n):
		q += abs(arr[j]-i)
	ans = min(q,ans)
print ans

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
sum_ = 0
t = 0
for i in range(n):
  sum_+=abs(a[i]-(i+1))
  t+=a[i]-(i+1)
if t>=0:
  print(sum_)
else:
  print(t%len(a))

Submission status: Wrong Answer

Solution code:
from math import ceil,floor
n=int(input())
a=[int(i) for i in input().split()]
for i in range(n):
  a[i]-=(i+1)

b1=ceil(sum(a)/n)
b2=floor(sum(a)/n)

def c1(x):
    return abs(x-b1)
def c2(x):
    return abs(x-b2)
print(min(sum(list(map(c1,a))), sum(list(map(c2,a)))))

Submission status: Wrong Answer

Solution code:
n = int(input())
aaa = list(map(int, input().split()))
aam = [a - i - 1 for i, a in enumerate(aaa)]
aas = sum(aam)
b = aas // n
ans = min(sum(abs(am - b) for am in aam), sum(abs(am - b - 1) for am in aam))
print(ans)

Submission status: Wrong Answer

Solution code:
import math 
N=int(input())
A=[int(i) for i in input().split()]
for i in range(N):
    A[i]=A[i]-i-1
#A.sort()
a=math.ceil(sum(A)/N)
ans=0
ans_1=0
ans_2=0
ans_3=0
for i in range(N):
    ans+=abs(A[i]-a)
for i in range(N):
    ans_1+=abs(A[i]-a-1)
for i in range(N):
    ans_2+=abs(A[i]-a+1)
for i in range(N):
    ans_3+=abs(A[i]-a+2)
print(min(ans,ans_1,ans_2,ans_3))

Submission status: Wrong Answer

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

mem = [a-i-1 for i,a in enumerate(src)]
sm = sum(mem)
tmp = (sm - sm%N)//N

ans = 0
for a in mem:
    ans += abs(tmp - a)
print(ans)

Submission status: Wrong Answer

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

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

a_sum = 0
for i in range(n):
    a_sum += a[i]

a_ave1 = a_sum // n
a_ave2 = a_ave1 + 1
a_ave3 = a_ave1 - 1

ans1 = 0
for i in range(n):
    ans1 = ans1 + abs(a[i] - a_ave1)
ans2 = 0
for i in range(n):
    ans2 = ans2 + abs(a[i] - a_ave2)
ans3 = 0
for i in range(n):
    ans3 = ans3 + abs(a[i] - a_ave3)
print(min(ans1, ans2, ans3))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd
from pprint import pprint as pp
import itertools as it
from functools import lru_cache

YN = {True: 'Yes', False: 'No'}
ri = lambda: int(input())
ria = lambda: list(map(int, input().split()))
rian = lambda n: [ria() for _ in range(n)]
rs = lambda: input()
rsa = lambda: input().split()
rsn = lambda n: [rs() for _ in range(n)]

N = ri()
A = ria()

ret = sum(abs(a-i-1) for i,a in enumerate(A))
for d in set(A):
  x = sum(abs(a-i-1+d) for i,a in enumerate(A))
  ret = min(ret,x)
print(ret)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd
from pprint import pprint as pp
import itertools as it
from functools import lru_cache

YN = {True: 'Yes', False: 'No'}
ri = lambda: int(input())
ria = lambda: list(map(int, input().split()))
rian = lambda n: [ria() for _ in range(n)]
rs = lambda: input()
rsa = lambda: input().split()
rsn = lambda n: [rs() for _ in range(n)]

N = ri()
A = ria()

ret = sum(abs(a-i-1) for i,a in enumerate(A))
for d in set(A):
  x = sum(abs(a-i-1+d) for i,a in enumerate(A))
  if ret == None:
    ret = x
  elif ret < x:
    break
  ret = min(ret,x)
print(ret)

Submission status: Wrong Answer

Solution code:

def mi():
	return map(int, input().split())

n = list(mi())[0]
a = list(mi())
for i in range(len(a)):
	a[i]-=i+1
s = 0

low = 0
high = int(2e9)

mins = 1e10
while low<high:
	mid = (low+high)//2
	s = 0
	for i in range(len(a)):
		s+=abs(a[i]+mid)
	mins = min(s,mins)
	if s<=mins:
		high = mid
	else:
		low = mid+1
print (mins)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
for i in range(N):
  A[i] -= i + 1
ct = Counter(A)
mean, c = ct.most_common(1)[0]
print(sum([abs(a - mean) for a in A]))

Submission status: Wrong Answer

Solution code:
n = int(input())
aaa = list(map(int, input().split()))
aam = [a - i - 1 for i, a in enumerate(aaa)]
aas = sum(aam)
b = round(aas / n)
print(sum(abs(am - b) for am in aam))

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)

a_sum = 0
for i in range(n):
    a_sum += a[i]

a_ave1 = a_sum // n
a_ave2 = a_ave1 + 1

ans1 = 0
for i in range(n):
    ans1 = ans1 + abs(a[i] - a_ave1)
ans2 = 0
for i in range(n):
    ans2 = ans2 + abs(a[i] - a_ave2)
print(min(ans1, ans2))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):

    tmp = [a-(i+1) for i, a in enumerate(A)]
    b1 = sum(tmp)//N
        
    def sk(b):
        s = 0
        for i, a in enumerate(A):
            s += abs(a-(b+i+1))
        return s

    
    return min(sk(b1), sk(b1+1), sk(b1-1))


def main():
    N = read_int()
    A = read_int_n() 
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

b = c//n
ret0 = 0
ret1 = 0
ret2 = 0
for i in range(n):
    ret0 += abs(a[i] - b - i)
    ret1 += abs(a[i] - b - i - 1)
    ret2 += abs(a[i] - b - i - 2)

print(min(ret0, ret1,ret2))

Submission status: Wrong Answer

Solution code:
'''input
9
1 2 3 4 5 6 7 8 9
'''
n = input()
arr = map(int,raw_input().split())
for i in range(n):
	arr[i] = (arr[i]-(i+1))
mean = float(sum(arr))/n
q = 0
for i in range(n):
	q += abs(arr[i]-int(mean))
q1 = 0
for i in range(n):
	q1 += abs(arr[i]-int(mean)-1)
q2 = 0
for i in range(n):
	q2 += abs(arr[i]-int(mean)+1)
print min(q1,q2,q)

Submission status: Wrong Answer

Solution code:
N = int(input())
data = list(map(int, input().split()))
for i in range(N):
    data[i] -= (i + 1)
ave = sum(data) / N
if ave > 0:
    key = int(ave + 1)
    key1 = int(ave)
else:
    key = int(ave - 1)
    key1 = int(ave)
data.sort()
sumdata = 0
sumdata1 = 0
for i in data:
    sumdata += abs(i - key)
    sumdata1 += abs(i - key1)
print(min([sumdata, sumdata1]))

Submission status: Wrong Answer

Solution code:
a=int(input())
b=list(map(int, input().split()))
c=list(range(1,a+1))
d=(sum(b)-sum(c))//a
c2=[i+d for i in c]
b2=[abs(b[i]-c2[i]) for i in range(a)]
print(sum(b2))

Submission status: Wrong Answer

Solution code:
# encoding:utf-8

def main():
	n = int(input())
	nums_raw = list(map(int, input().split()))
	nums = [nums_raw[i] - i for i in range(n)]
	ans = search(nums)
	print(sum([abs(nums_raw[i] - (ans + i)) for i in range(n)]))

def search(nums):
	left = min(nums)
	right = max(nums)
	tmp = 10 ** 10
	while True:
		if calc(nums, left) >= calc(nums, right):
			new = int((left + right)/2)
			left = new
		else:
			new = int((left + right)/2)
			right = new
		if new == tmp:
			if min(calc(nums, new), calc(nums, new + 1), calc(nums, new - 1)) == calc(nums, new):
				return new
			elif min(calc(nums, new), calc(nums, new + 1), calc(nums, new - 1)) == calc(nums, new + 1):
				return new + 1
			else:
				return new - 1
		else:
			tmp = new

def calc(nums, i):
	return sum([abs(x - i) for x in nums])

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int ,input().split()))
s = sum(a)
mean = s / N
cnt = 10**14
for j in range(s//N-10,s//N+10):
    tmp = 0
    for i in range(N):
        tmp += abs(a[i]-i-j-1)
    cnt = min(tmp,cnt)
print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A2 = []
for i, a in enumerate(A):
    A2.append(a-i)
m = sum(A2)//N
an = 0
for a in A2:
    an += abs(m-a)
ans = an
an = 0
for a in A2:
    an += abs(m+1-a)
ans = min(ans, an)
an = 0
for a in A2:
    an += abs(m-1-a)
ans = min(ans, an)
an = 0
for a in A2:
    an += abs(m*2-a)
ans = min(ans, an)
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):

    tmp = [a-(i+1) for i, a in enumerate(A)]
    b1 = sum(tmp)//N
        
    def sk(b):
        s = 0
        for i, a in enumerate(A):
            s += abs(a-(b+i+1))
        return s

    
    return min(sk(b1), sk(b1+1))


def main():
    N = read_int()
    A = read_int_n() 
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import functools
N = int(input())
A = [int(x) for x in input().split()]
for i,a in enumerate(A):
  A[i] = a - i - 1
ave = functools.reduce(lambda x, y: x + y, A) // N
B0 = functools.reduce(lambda x, y: x + y, [abs(a - ave) for a in A])
B1 = functools.reduce(lambda x, y: x + y, [abs(a - ave - 1) for a in A])
print(min(B0, B1))

Submission status: Wrong Answer

Solution code:
import statistics

N = int(input())
A_suc = [int(a) for a in input().split()]
B_suc = [i + 1 for i in range(len(A_suc))]
C_suc = [i - j for i, j in zip(A_suc, B_suc)]
median = statistics.median(C_suc)
D_suc = [abs(i - median) for i in C_suc]
print(sum(D_suc))

Submission status: Wrong Answer

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

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

b = c//n
ret1 = 0
ret2 = 0
for i in range(n):
    ret1 += abs(a[i] - b - i - 1)
    ret2 += abs(a[i] - b - 1 - i - 1)

print(min(ret1,ret2))

Submission status: Wrong Answer

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

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

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

result = 0

for i in b:
    result += abs(num - i)

print(result)

Submission status: Wrong Answer

Solution code:
import math 
N=int(input())
A=[int(i) for i in input().split()]
for i in range(N):
    A[i]=A[i]-i-1
#A.sort()
a=math.ceil(sum(A)/N)
ans=0
ans_1=0
ans_2=0
for i in range(N):
    ans+=abs(A[i]-a)
for i in range(N):
    ans_1+=abs(A[i]-a-1)
for i in range(N):
    ans_2+=abs(A[i]-a+1)
print(min(ans,ans_1,ans_2))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
import numpy as np
N = int(input())
A = list(map(int, input().split()))
A = [a-(i+1) for i, a in enumerate(A)]
m1 = int(np.floor(np.mean(A)))
m2 = int(np.ceil(np.mean(A)))
ans1 = 0
ans2 = 0
for a in A:
    ans1 += abs(a-m1)
    ans2 += abs(a-m2)
print(min(ans1, ans2))

Submission status: Wrong Answer

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

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

b = a[int(n / 2)]
print(sum(map(lambda x: abs(x - b), a)))

Submission status: Wrong Answer

Solution code:
from math import ceil,floor
n=int(input())
a=[int(i) for i in input().split()]
for i in range(n):
  a[i]=a[i]-(i+1)

b1=ceil(sum(a)/n)
b2=floor(sum(a)/n)

def c1(x):
    return abs(x-b1)
def c2(x):
    return abs(x-b2)
print(min(sum(list(map(c1,a))),sum(list(map(c2,a)))))

Submission status: Wrong Answer

Solution code:

def mi():
	return map(int, input().split())

n = list(mi())[0]
a = list(mi())
for i in range(len(a)):
	a[i]-=i+1
s = 0
s1=0
b = a.copy()
for i in range(n):
	b[i] = abs(a[i])
x = min(b)
x1 = -1*min(a)
for i in range(len(a)):
	s+=abs(a[i]+x)
	s1+=abs(a[i]+x1)
print (min(s,s1))

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))
#print(b)
#print(sum(b), round(sum(b)/n))
q = round(sum(b)/n)
q = sum(b)//n
s = 0
for i in b:
    s += abs(i-q)
print(s)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A2 = []
for i, a in enumerate(A):
    A2.append(a-i)
m = sum(A2)//N
an = 0
for a in A2:
    an += abs(m-a)
ans = an
an = 0
for a in A2:
    an += abs(m+1-a)
ans = min(ans, an)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
minb=min(min(A),max(A)-N)
maxb=max(max(A),min(A)+N)
ans=float('inf')
for b in range(minb,maxb+1):
  d=0
  for i in range(N):
    d+=abs(A[i]-(b+i))
  ans=min(ans,d)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
A = [A[i]-(i+1) for i in range(N)]
A = sorted(A)
C = {}
for i in range(N):
    a = A[i]
    if a not in C:
        C[a] = 0
    C[a] += 1
def f(x):
    cnt = 0
    for a in C:
        cnt += abs(x-a)*C[a]
    return cnt
l = A[0]
r = A[-1]
y1 = f(l)
while r>l:
    midl = (2*l+r)//3
    midr = (l+2*r)//3
    B = sorted([(l,f(l)),(midl,f(midl)),(midr,f(midr)),(r,f(r))],key=lambda x:x[1])
    x1,y1 = B[0]
    x2,y2 = B[1]
    if x1>x2:
        r = x1
        l = x2
    else:
        r = x2
        l = x1
print(y1)

Submission status: Time Limit Exceeded

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 < 100:
    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: Time Limit Exceeded

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 ng - ok > 1 and c < 1000:
    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: Time Limit Exceeded

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 ng - ok > 1 and c < 10000:
    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))