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: Runtime Error

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

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

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

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

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

Submission status: Runtime Error

Solution code:
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: Runtime Error

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

ave = B[N//2]
ans = 0
for i in range(N):
    ans1 += abs(B[i]-ave)
print(ans)

Submission status: Runtime Error

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

V = sorted(A)

if N%2==1:
	median = V[int((N-1)/2)]
else:
	median = (V[int(N/2)-1]+V[int(N/2)])/2

min = median-2 
max = median+2

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: Runtime Error

Solution code:
n=int(input())
b=[int(a-(i+1))  for i,a in enumerate(list(map(int,input().split())))]
bm=b[:]
bm.sort()
mid_1=bm[n//2]
mid_2=bm[(n//2)+1]
ans_1,ans_2=0,0
if n%2==1:
  for bb in b:
    ans_1+=abs(bb-mid_1)
  print(ans_1)
else:
  for bb in b:
    ans_1+=abs(bb-mid_1)
    ans_2+=abs(bb-mid_2)
  print(min(ans_1,ans_2))

Submission status: Runtime Error

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=lispin()
    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: Runtime Error

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=lispin()
    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: Runtime Error

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

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

x.sort()
x_ = []
b = 0
if x.count(0) <= n//2:
    for i in range(n):
        if x[i] != 0:
             x_.append(x[i])

    n_ = len(x_)
    if n_%2 == 0:
        b = x_[n_//2]
    else:
        b = x_[n_//2 + 1]

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

print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
B = sorted(A[i] - i - 1 for i in range(N))
def sad(b):
    return sum(abs(A[i] - i - 1 - b)for i in range(N))
print(min(sad(B[N//2]),sad(B[N//2+1])))

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
s=0
for i in range(n):
    a[i] -= i + 1
    s += a[i]
b1 = a[n // 2]
b2 = a[(n // 2 )+ 1]
r1=0
r2=0
for i in range(n):
    r1+=abs(a[i]-b1)
    r2+=abs(a[i]-b2)
print(min(r1,r2))

Submission status: Runtime Error

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

from math import floor

def main():
  n = int(input())
  la = list(map(int, input().split()))
  la = [a-i for i, a in enumerate(la, 1)]
  ix = len(la) // 2
  print(min([sum(map(lambda x: abs(x-la[ix+i]), la)) for i in range(2)]))

if __name__=='__main__':
  main()

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
b = 0
ans = 10**10

def calabs(n, b, a):
    return abs(a[n] - (b + (n + 1)))

diff1 = [calabs(i, -1, A) for i in range(N)]
diff2 = [calabs(i, 0, A) for i in range(N)]
diff3 = [calabs(i, 1, A) for i in range(N)]

# print(sum(diff1), sum(diff2), sum(diff3))

if sum(diff1) <= sum(diff2) <= sum(diff3):
    tmp = -1
elif sum(diff1) >= sum(diff2) >= sum(diff3):
    tmp = 1

while True:
    diff = [calabs(i, b, A) for i in range(N)]
    
    if ans >= sum(diff):
        ans = sum(diff)
        # print(ans)
        b += tmp
    else:
        print(ans)
        break

Submission status: Runtime Error

Solution code:
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = list(map(int, readline().split()))
    for i in range(n):
        a[i] -= i + 1
    a.sort()
    t1 = 0
    t2 = 0
        t2 += abs(a[i] - a[n//2 - 1])
    print(min(t1, t2))


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
A = [A[i] - i - 1 for i in range(N)]
A.sort()
# for a in [A[N // 2], A[N // 2 + 1]]:
sum_A = [0, 0]
for i in range(N):
    sum_A[0] += abs(A[i] - A[N // 2])
sum_2 = 0
for i in range(N):
    sum_A[1] += abs(A[i] - A[N // 2 + 1])
print(min(sum_A))

Submission status: Runtime Error

Solution code:
def total(inlist,k):
    print(sum([ abs(i-k) for i in inlist ]))
    return
n = int(input())
a_list = [ int(v) for v in input().split() ]
a_list = [ v-i for i, v in enumerate(a_list,1) ]
a_list.sort()

total(a_list,a_list[n//2])ｖ

Submission status: Runtime Error

Solution code:
N=int(input())
lst=list(map(int,input().split()))
lst_=sorted(lst)
def f(b):
  ans=0
  for i in range(1,N+1):
    ans+=abs(lst[i-1]-(b+i))
  return ans

if N%2==1:
  b=lst_[(N-1)//2]-((N-1)//2+1)
  print(f(b))
else:
  b1=lst_[N//2]-(N//2+1)
  b2=lst_[b1-1]-(b1+1)
  print(min(f(b1),f(b2)))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from math import log2
N = int(input())
A = list(map(int, input().split()))
B = [a-i for i, a in enumerate(A)]
m = sum(B)//N
l = int(log2(N))
print(min(sum(abs(b-m-i) for b in B)for i in range(-l,l)))

Submission status: Runtime Error

Solution code:
import collections
import math
N=int(input())
A=list(map(int,input().split()))
diff_dic=collections.defaultdict(int)


B=[A[i]-(i+1) for i in range(N)]
for i in range(N):
  diff_dic[B[i]]+=1
  
diff_list=sorted(list(diff_dic.items()), key=lambda x:x[1],reverse=True)
ans=diff_list[0][0]
temp=0

ans=sum(diff_list) / N
temp=0
for j in range(N):
  temp+= abs(A[j] - (int(ans) + j + 1) )


temp2=0
for j in range(N):
  temp2+= abs(A[j] - (math.ceil(ans) + j + 1) )
print(min(temp,temp2))

Submission status: Runtime Error

Solution code:
import collections
import math
N=int(input())
A=list(map(int,input().split()))
diff_dic=collections.defaultdict(int)


B=[A[i]-(i+1) for i in range(N)]
for i in range(N):
  diff_dic[B[i]]+=1
  
diff_list=sorted(list(diff_dic.items()), key=lambda x:x[1],reverse=True)
ans=diff_list[0][0]
temp=0

ans=sum(diff_list) / N
temp=0
for j in range(N):
  temp+= abs(A[j] - (int(ans) + j + 1) )
print(temp)

temp2=0
for j in range(N):
  temp2+= abs(A[j] - (math.ceil(ans) + j + 1) )
print(temp2)

Submission status: Runtime Error

Solution code:
def slove():
    import sys
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    a = list(map(int, input().rstrip('\n').split()))
    b = []
    for i, v in enumerate(a):
        b.append(v - (i + 1))
    b.sort()
    t = b[len(b) // 2]
    s = 0
    for i, v in enumerate(a):
        s += abs(v - (t + (i + 1)))
    print(s)


if __name__ == '__main__':

Submission status: Runtime Error

Solution code:
from statistics import mean
import math
n = int(input())
a = [int(i) for i in input().split()]
for i in range(n):
    a[i] -= i+1
a_fl = math.floor(median(a))
a_ce = math.ceil(median(a))
ans_fl=ans_ce=0

for i in range(n):
    ans_fl += abs(a[i]-a_fl)
    ans_ce += abs(a[i]-a_ce)
print(int(min(ans_fl,ans_ce)))

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res

def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

n = I()
a = LI()
for i in range(n):
    a[i] -= i+1
a.sort()
b = a[n>>1]
ans = 0
for i in a:
    ans += abs(i-b)
if n%2:
    b = a[(n>>1)+1]
    ans_ = 0
    for i in a:
        ans_ += abs(i-b)
    if ans > ans_:
        ans = ans_
    b = (a[(n>>1)+1]+a[n>>1])>>1
    ans_ = 0
    for i in a:
        ans_ += abs(i-b)
    if ans > ans_:
        ans = ans_
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())

num_list = [ int(v) for v in input().split() ]
num_list = [ num_list[i] - (i+1) for i in range(n) ]
median_u = num_list[(n//2)+1]
median_d = num_list[n//2]

d_list = [i-median_u for i in num_list]
u_list = [i-median_d for i in num_list]

print(min(sum(map(abs,d_list)),sum(map(abs,u_list))))

Submission status: Runtime Error

Solution code:
#平均値に近づけるという考え方が間違い

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

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

A.sort()

center1 = A[N//2]
center2 = A[(N+2)//2]

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

ans2 = 0
for j in range(N):
    ans2 += abs(A[j]-center2)
    
print (min(ans1, ans2))

Submission status: Runtime Error

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

center=B[N//2] if N%2==0 else round((B[(N-1)//2]+B[(N+1)//2])/2)
ans=0
for i in B:
    ans+=abs(i-center)
print(ans)

Submission status: Runtime Error

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

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

aa=sorted(a)
if n%2==0:
  b=(aa[n/2-1]+aa[n/2])/2
else:
  b=aa[int((n-1)/2)]

s=0
for i in aa:
  s+=abs(i-b)
print(s)

Submission status: Runtime Error

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

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

import math
import numpy as np

aa=np.asarray(a)
b=math.floor(np.sum(aa)/n)

def p(b,k):
  s=np.sum(np.abs(aa-b))
  t=np.sum(np.abs(aa-b-1))
  if s>t:
    if k==-1:
      print(t)
    else:
      return p(b+1,1)
  elif s==t:
    print(s)
  else:
    if k==1:
      print(s)
    else:
      return p(b-1,-1)
  
p(b,0)

Submission status: Runtime Error

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

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

import math
#import statistics
#b=statistics.median(a)
b=math.floor(sum(a)/n)

import numpy as np

aa=np.asarray(a)
def p(b,k):
  s=np.sum(np.abs(aa-b))
  t=np.sum(np.abs(aa-b-1))
  if s>t:
    if k==-1:
      print(t)
    else:
      return p(b+1,1)
  elif s==t:
    print(s)
  else:
    if k==1:
      print(s)
    else:
      return p(b-1,-1)
  
p(b,0)

Submission status: Runtime Error

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
diff = [0] * N
for i in range(N):
    diff[i] = A[i] - (i+1)
diff.sort

b1 = diff[len(diff) - 1 // 2]
b2 = diff[(len(diff)) // 2]

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

Submission status: Runtime Error

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
diff = [0] * N
for i in range(N):
    diff[i] = A[i] - (i+1)
diff.sort

b1 = diff[len(diff) // 2]
b2 = diff[(len(diff) + 1) // 2]

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

Submission status: Runtime Error

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
diff = [0] * N
for i in range(N):
    diff[i] = A[i] - (i+1)
diff.sort

b1 = diff[len(diff) // 2]
b2 = diff[len(diff) // 2 + 1]

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

Submission status: Runtime Error

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

aa = [ai - i-1 for i,ai in enumerate(a)]

def tri_search(f:"f(x:float)->float", left, right, iter=100)->float:
    for _ in range(iter):
        ml = (left*2 + right) / 3
        mr = (left + right*2) / 3
        if f(ml) < f(mr):
            right = mr
        else:
            left = ml
    # print(left, right)
    return (right + left) / 2

def f(x):
    ret = 0
    x = int(x+0.5)
    for aai in aa:
        ret += abs(aai - x)
    return ret

b = tri_search(f, -10**9, 10**9)
print(min(f(b), f(b)+1, f(b)-1)

Submission status: Runtime Error

Solution code:
def mm(N, A, x):
  S = 0
  for i in range(N):
    S += abs(A[i] - x)
  return S

N = int(input())
A = []
j = 0
for i in input().split():
  j += 1
  A.append(int(i)-j)
A.sort()
if N % 2 == 0:
  print(mm(N, A, A[N//2]))
else:
  print(min(mm(N, A, A[N//2]), mm(N, A, A[N//2 + 1])))

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split(' ')))
num = 0
X = []
for i,j in enumerate(A):
  B = j-(i+1)
  X.append(B)
X.sort()
median = 0
if N % 2 == 0:
  median = (X[N/2] + X[N/2-1])/2
else:
  median = X[int((N-1)/2)] 

for x in X:
  num += abs(x-median)
print(num)

Submission status: Runtime Error

Solution code:
import sys
import math
input = sys.stdin.readline

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

for i in range(len(l)):
    l[i] = i - l[i] + 1

l.sort()
t = l[math.ceil(len(l) / 2)]

for i in range(len(l)):
    l[i] = abs(l[i] - t)
    
print(sum(l))

Submission status: Runtime Error

Solution code:


def merge(a, b):
    if a[0] > b[0]:
        if a[1] > b[0]:
            return a
        return a[0], b[0]
    if b[1] > a[0]:
        return b
    return b[0], a[0]


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

dp = [(a[i], 0) for i in range(1 << n)]
for j in range(n):
    for mask in range(1, len(dp)):
        if mask & (1 << j):
            dp[mask] = merge(dp[mask], dp[mask ^ (1 << j)])

best = a[0]
for i in range(1, len(dp)):
    best = max(best, sum(dp[i]))
    print(best)

Submission status: Runtime Error

Solution code:
#include<iostream>
#include<vector>
#include<math.h>
#include<iomanip>
#include<algorithm>
#include<set>
#include<map>
#include<cmath>
#include<string>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
typedef long long int llint;
typedef pair<ll, ll> pa;
#define MM 1000000000
#define MOD MM+7
#define MAX 101000
#define MAP 110
#define initial_value -1
#define MAX_T 1001
#define Pair pair<int,int>
#define chmax(a,b) (a<b ? a=b:0)
#define chmin(a,b) (a>b ? a=b:0)
#define INF (1 << 29) //536870912
const long double PI = acos(-1);
const ll DEP = 1e18;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};
ll N;
ll a[200002];
vector<ll> sum(0);
int main(){
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> a[i];
        sum.push_back(a[i] - i - 1);
    }
    ll ans = 0;
    ll tmp = 0;
    sort(sum.begin(),sum.end());
    ll bi = sum[N/2 - 1];
    for(int i = 0; i < N; i++){
        ans += abs(sum[i] - bi);
    }
    ll bz = sum[N/2];
    for(int i = 0; i < N; i++){
        tmp += abs(sum[i] - bz);
    }
    cout << min(tmp,ans) << endl;
}

Submission status: Runtime Error

Solution code:
#include<iostream>
#include<vector>
#include<math.h>
#include<iomanip>
#include<algorithm>
#include<set>
#include<map>
#include<cmath>
#include<string>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
typedef long long int llint;
typedef pair<ll, ll> pa;
#define MM 1000000000
#define MOD MM+7
#define MAX 101000
#define MAP 110
#define initial_value -1
#define MAX_T 1001
#define Pair pair<int,int>
#define chmax(a,b) (a<b ? a=b:0)
#define chmin(a,b) (a>b ? a=b:0)
#define INF (1 << 29) //536870912
const long double PI = acos(-1);
const ll DEP = 1e18;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};
ll N;
ll a[200002];
vector<ll> sum(0);
int main(){
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> a[i];
        sum.push_back(a[i] - i - 1);
    }
    ll ans = 0;
    sort(sum.begin(),sum.end());
    if(N % 2 == 1){
        ll mid = a[N/2];
        for(int i = 0; i < N; i++){
            ans += sum[i] - mid;
        }
        cout << ans << endl;
        return 0;
    } else {
        ll mid = (a[N/2] + a[N/2-1])/2;
        for(int i = 0; i < N; i++){
            ans += sum[i] - mid;
        }
        cout << ans << endl;
        return 0;
    }
}

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n=int(input())
a=[int(input()) + i for i in range(n)]
a.sort()
b=a[n//2]
ans=0
for i in range(n):
  ans+=abs(a[i]-b)
print(ans)

Submission status: Runtime Error

Solution code:
""" AtCoder """

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

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

A.sort()

b = A[N//2]
bb = A[N//2 + 1]

ans = 0
ansans = 0

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

print(min(ans, ansans))

Submission status: Runtime Error

Solution code:
import sys

N = int(input())
A = list(map(int, input().split()))
A = sorted([A[k]-(k+1) for k in range(N)])

for k in range((N-2)//2 + 1, N-1):
  if A[k] < A[k+1]:
    b = k
    break
  if k == N-2:
    print(0)
    sys.exit()
print(sum([abs(A[k]-A[b]) for k in range(N)]))

Submission status: Runtime Error

Solution code:
import math
n=int(input())
a=list(map(int,input().split()))
for i in range(n):
    a[i]=a[i]-i-1
a.sort()
if n%2==1:
    p=a[n//2]
    print(abs(sum(a[:n//2])-p*(n//2))+sum(a[n//2+1:])-p*(n//2))
else:
    l=a[n//2-1]+a[n//2]
    s=math.fllor(l/2)
    t=math.ceil(l/2)
    print(min(abs(sum(a[:n//2]))-s*n//2+sum(a[n//2:])-s*(n//2),abs(sum(a[:n//2]))-t*n//2+sum(a[n//2:])-t*(n//2)))

Submission status: Runtime Error

Solution code:
N = int(input())
A = input().split(' ')
A.sort()

B = [A[i]-i+1 for i in range(N)]
median = B[int(N/2)-1]

print(sum(B)-N*median)

Submission status: Runtime Error

Solution code:
N, As = int(input()), list(map(int, input().split()))
As = [As[i] - i - 1 for i in range(N)]
ans = sys.maxsize
for b in range(min(As), max(As) + 1):
    ans = min(ans, sum(map(lambda A: abs(A - b), As)))
print(ans)

Submission status: Runtime Error

Solution code:
N=int(input())
A=[int(i) for i in input().split(' ')]
for i in range(len(A)):
  a[i]-=i+1
if len(A)%2==1:
  b=(len(A)-1)//2
else:
  b=(len(A))//2-1
s=0
for i in range(len(A)):
  s+=abs(A[i]-(b+i))
print(s)

Submission status: Runtime Error

Solution code:
def func(A,b):
  s=0
  for i in range(len(A)):
    s+=abs(A[i]-(b+i))
  return s

N=int(input())
A=[int(i) for i in input().split(' ')]
min=None
for b in range(A[0],A[-1]-len(A)+1):
  if min=None:
    min=func(A,b)
  elif min>func(A,b):
    min=func(A,b)
print(min)

Submission status: Runtime Error

Solution code:
import sys
import math

N = int(input())
A = [int(x) for x in input().split()]

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

B = sorted(A2)

i1 = math.floor(N / 2)
i2 = math.ceil(N / 2)


b1 = B[i1]
b2 = B[i2]


def calcSad(A2, b):
    sum = 0
    for i in A2:
        sum += abs(i - b)
    return sum


sum = 99999999999999999999999
for b in range(b1, b2+1):
    s = calcSad(B, b)
    sum = min(sum, s)

print(sum)


sys.exit(0)

Submission status: Runtime Error

Solution code:
import math
n = int(input())
lis = list(map(int,input().split()))
for i in range(n):lis[-(i+1)] += i
lis.sort()
cou = 0
co = 0
num = lis[math.ceil(n/2)]
nu = lis[math.floor(n/2)]
for i in range(n):
  cou += abs(lis[i]-num)
  co += abs(lis[i]-nu)
print(min(cou,co))

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>

#define st first
#define nd second
#define all(x) (x).begin(), (x).end()

using namespace std;
using namespace placeholders;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template <class T> void mini(T &l, T r){l = min(l, r);}
template <class T> void maxi(T &l, T r){l = max(l, r);}

template <class TH> void _dbg(const char *sdbg, TH h){cerr << sdbg << "=" << h << "\n";}
template <class TH, class ...TA> void _dbg(const char *sdbg, TH h, TA... a){
	while (*sdbg != ','){cerr << *sdbg++;}cerr << "=" << h << ","; _dbg(sdbg + 1, a...);
}
template <class T> ostream &operator <<(ostream &os, vector<T> V){
	os << "["; for (auto vv: V) os << vv << ","; return os << "]";
}
template <class L, class R> ostream &operator <<(ostream &os, pair<L, R> P){
	return os << "(" << P.st << "," << P.nd << ")";
}

#ifdef SFIC
	#define eput(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
	#define eput(...) 218
#endif

const int N = 2E5 + 10;

int a[N];

int main(){
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; ++i){
		scanf("%d", a + i);
		a[i] -= i;
	}
	nth_element(a, a + n / 2, a + n);
	ll ans = 0;
	for (int i = 0; i < n; ++i)
		ans += abs(a[i] - a[n / 2]);
	printf("%lld\n", ans);
	return 0;
}

Submission status: Runtime Error

Solution code:
from statistics import mode

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

aa = list(map(lambda e: e[1] - (e[0] + 1), enumerate(a)))
minb = mode(aa)
ans = sum(map(lambda ea: abs(ea - minb), aa))

print(ans)

Submission status: Runtime Error

Solution code:
import math
import numpy as np

c = []
N = input()
for i in range(int(N)):
    c.append(int(input())-i-1)

c = np.asarray(c)
ave = np.mean(c)

a1 = np.sum(np.abs(c-math.floor(ave)))
a2 = np.sum(np.abs(c-math.ceil(ave)))

print(min(a1,a2))

Submission status: Runtime Error

Solution code:
import math
import numpy as np

c = []
N = input()
for i in range(N):
    c.append(input()-i-1)
    c = np.asarray(c)

ave = np.mean(c)

a1 = np.sum(np.abs(c-math.floor(ave)))
a2 = np.sum(np.abs(c-math.ceil(ave)))

print(math.min(a1,a2))

Submission status: Runtime Error

Solution code:
import random
from itertools import accumulate
N = int(input())
As = [int(i) for i in input().split(' ')]

#N = pow(10, 4)
#As = [random.randint(0,1000) for r in range(N)] 
As = list(accumulate(As))


def bsearch(l, ls, rs):
    n = int(len(l)/2)
    if n == 0:
        return [max(l[0]-ls , rs-l[0]), min(l[0]-ls , rs-l[0])]
    lsum = l[n] - ls
    rsum = rs - l[n]
    ll = l[:n]
    rl = l[n:]
    if lsum > rsum:
        return bsearch(ll, ls, rs)
    else:
        return bsearch(rl, ls, rs)

for i in range(N-3):
    cs = bsearch(As[:i+2], 0, As[i+1]) + bsearch(As[i+2:], As[i+1], As[-1])
    if i == 0:
        result = max(cs) - min(cs)
    else:
        if max(cs) - min(cs) < result:
            result = max(cs) - min(cs)
print(result)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)
using namespace std;
typedef long long ll;

const int MAX_N=2e5;	
const ll INF=1e12;
int N;
ll A[MAX_N];

int main(){
	cin>>N;
	REP(i,N){
		cin>>A[i];
	}
	ll lb=-INF,ub=INF;
	while(ub-lb>1){
		ll mid=(lb+ub)/2;
		int c1,c2;
		c1=c2=0;
		REP(i,N){
			if (A[i]>mid+i+1){
				c1++;
			}else{
				c2++;
			}
		}
		if (c1<=c2){
			ub=mid;
		}else{
			lb=mid;
		}
	}
	ll ans=0;
	REP(i,N){
		ans+=llabs(A[i]-(ub+i+1));
	}
	cout<<ans<<endl;
	return 0;
}

Submission status: Runtime Error

Solution code:
import sys
import collections


l1 = sys.stdin.readline()
l2 = sys.stdin.readline().split()
N = int(l1.strip())
l2 = [int(l2[i].strip()) - (i+1) for i in range(0,len(l2))]


A = sorted(l2)
minA = A[0]
maxA = A[N-1]

def culc(x):
	return sum([abs(y - x) for y in A])

res = culc(A[0])
resMin = res

C = collections.Counter(A)
# 辞書をソートしなくてもいいや。indexのlistつくる。
#C = sorted(C.items(), key=lambda x: x[0])

Ind = sorted(list(set(A)))

#print(A)
#print(C)
#print(Ind)

i = 0
k = Ind[i+1]

lowsum = C[k]

for x in range(minA+1, maxA+1):
	#print(res)
	# x <= A[j]
	#print("{}, {}".format(x, lowsum))
	res += lowsum #xが増えた分、x以下の分が増える
	res -= (N-lowsum) #xが増えた分、x以上の分が減る
	#print("i{}, Ind{}, x{}".format(i, k, x))

	# x-1<A[j], x=A[j]の場合
	if x >= k:
		i += 1
		k = Ind[i]
		lowsum += C[k]
	
	resMin = min(res, resMin)


print(resMin)

Submission status: Runtime Error

Solution code:
import statistics
N=int(input())
a=input()
S=a.split(" ")
for i in range(N):
    S[i]=abs(int(S[i])-(i+1))
b=statistics.mode(S)
for j in range(N):
    S[j]=abs(int(S[j])-b)
print(sum(S))

Submission status: Runtime Error

Solution code:
N=int(input())
a=input()
b=int(input())
S=a.split(" ")
for i in range(N):
    S[i]=abs(int(S[i])-(i+1+b))
print(sum(S))

Submission status: Runtime Error

Solution code:
# -*- coding:utf-8 -*-
n = int(input())
a = [int(i) for i in input().split()]
dp = [[x, 0] for x in range(0, len(a))]
 
 
def ins(x, i):
    if x in dp[i]:
        return
    if dp[i][0] != x and a[dp[i][0]] < a[x]:
        dp[i][1] = dp[i][0]
        dp[i][0] = x
    elif dp[i][1] != x and a[dp[i][1]] < a[x]:
        dp[i][1] = x
 
 
def mix(i, j):
    ins(dp[i][0], j)
    ins(dp[i][1], j)
 
 
for i in range(0, len(a)):
    for j in range(0, n):
        if i & (1 << j) == 0:
            mix(i, i | (1 << j))
 
 
ans = 0
for i in range(1, len(a)):
    u = a[dp[i][0]]+a[dp[i][1]]
    ans = max(ans, u)
    print(ans)

Submission status: Runtime Error

Solution code:
n=input()
numbers=list(map(int,input().split()))
num=(sum(numbers)+0.5)//n
print(sum([abs(i-num) for i in numbers]))

Submission status: Runtime Error

Solution code:
N= input()
A=input().split()
B=[A[i]-i for i in range(N)]
B.sort()
if N%2==0:
    print((B[N/2]+B[N/2-1])/2)
else:
    print(B[(N+1)/2])

Submission status: Runtime Error

Solution code:
# -*- coding:utf-8 -*-
n = int(input())
a = [int(i) for i in input().split()]
dp = [[x, 0] for x in range(0, len(a))]


def ins(x, i):
    if dp[i][0] != x and a[dp[i][0]] < a[x]:
        dp[i][1] = dp[i][0]
        dp[i][0] = x
    elif dp[i][1] != x and a[dp[i][1]] < a[x]:
        dp[i][1] = x


def mix(i, j):
    ins(dp[i][0], j)
    ins(dp[i][1], j)


for i in range(0, len(a)):
    for j in range(0, n):
        if i & (1 << j) == 0:
            mix(i, i | (1 << j))

ans = 0
for i in range(1, len(a)):
    u = a[dp[i][0]]+a[dp[i][1]]
    ans = max(ans, u)
    print(ans)

Submission status: Runtime Error

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

from itertools import accumulate


ans = float("inf")
if N == 4:
    ans = min(ans, (max(A) - min(A)))
else:
    cs = accumulate(A)
    for i in range(2, N - 2):
        left_cs = cs[:i]
        right_cs = cs[i:]
        for l, v in enumerate(left_cs):
            if v + left_cs[l + 1] >= left_cs[-1]:
                P = left_cs[l]
                Q = left_cs[-1] - P
                break
        for r, v in enumerate(right_cs):
            if v + right_cs[r + 1] >= right_cs[-1]:
                R = right_cs[r]
                S = right_cs[-1] - R
                break
        ans = min(ans, (max(P, Q, R, S) - min(P, Q, R, S)))

print(ans)

Submission status: Runtime Error

Solution code:
	//Clear mp
				for(Integer t:mp.keySet()){
					if(!load.contains(t)){
						System.out.println("Clears:"+t);
						mp.put(t,null);	
					}
				}

Submission status: Runtime Error

Solution code:
practice

Submission status: Runtime Error

Solution code:
i=int
k=input
N = i(k())
l = list(map(i,k().split()))
for j in range(n):
 lis[j] -= (j+1)
l.sort()
print(sum(list(map(lambda x: abs(x - l[N//2]),l))))

Submission status: Runtime Error

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))
arr.sort()
mean = float(arr[n//2]+arr[n//2+1])/2
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: Runtime Error

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))
arr.sort()
mean = float(arr[n//2]+arr[n//2+1])/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: Runtime Error

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))
arr.sort()
median = float(arr[n//2]+arr[n//2+1])/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: Runtime Error

Solution code:
n = int(input())
d,x = map(int, input().split())
times = [int(input()) for i in range(n)]

count = 0
for k in range(n):
    count += int(d/times[k]) + 1

print(count + x)