Problem:


Score : 200 points

Problem Statement

Evi has N integers a_1,a_2,..,a_N. His objective is to have N equal integers by transforming some of them.

He may transform each integer at most once. Transforming an integer x into another integer y costs him (x-y)^2 dollars. Even if a_i=a_j (i≠j), he has to pay the cost separately for transforming each of them (See Sample 2).

Find the minimum total cost to achieve his objective.

Constraints

1≦N≦100

-100≦a_i≦100

Input

The input is given from Standard Input in the following format:

N
a_1 a_2 ... a_N

Output

Print the minimum total cost to achieve Evi's objective.

Sample Input 1

2
4 8

Sample Output 1

8

Transforming the both into 6s will cost (4-6)^2+(8-6)^2=8 dollars, which is the minimum.

Sample Input 2

3
1 1 3

Sample Output 2

3

Transforming the all into 2s will cost (1-2)^2+(1-2)^2+(3-2)^2=3 dollars. Note that Evi has to pay (1-2)^2 dollar separately for transforming each of the two 1s.

Sample Input 3

3
4 2 5

Sample Output 3

5

Leaving the 4 as it is and transforming the 2 and the 5 into 4s will achieve the total cost of (2-4)^2+(5-4)^2=5 dollars, which is the minimum.

Sample Input 4

4
-100 -100 -100 -100

Sample Output 4

0

Without transforming anything, Evi's objective is already achieved. Thus, the necessary cost is 0.



Sample input:
2
4 8


Sample output:
8

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
ans = int(1e18)
for i in range(101):
    cnt = 0
    for j in range(n):
        cnt += (a[j]-i)**2
    ans = min(ans,cnt)
    cnt = 0
    for j in range(n):
        cnt += (a[j]+i) **2
    ans = min(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    a=list(map(int,input().split()))
    ans=INF
    for i in range(-100,101):
        tmp=0
        for x in a:
            tmp+=(x-i)**2
        ans=min(ans,tmp)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
a = list(map(int,input().split()))
res = 10**18
for val in range(-100,101):
    tmp = sum([(val-val2)**2 for val2 in a])
    res = min(res,tmp)
print(res)

Submission status: Accepted

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

max_A = max(A)
min_A = min(A)

ans = 10**9
for y in range(min_A, max_A+1):
    tmp = 0
    for a in A:
        xsuby = a - y
        tmp += xsuby ** 2
    ans = min(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
N=int(input());a=[int(i) for i in input().split()]
print(min([sum([(n-i)**2 for n in a])for i in range(-100,101)]))

Submission status: Accepted

Solution code:
N = int(input())
a = [int(i) for i in input().split()]
ans = float("inf")
for i in range(-100, 101):
    ans = min(sum([(n - i)** 2 for n in a]), ans)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
asum = sum(a)
a2sum = 0
for m in a:
  a2sum += m**2
x1 = asum//n
x2 = x1+1
z1 = n*x1**2-2*asum*x1+a2sum
z2 = n*x2**2-2*asum*x2+a2sum
print(min(z1,z2))

Submission status: Accepted

Solution code:
ans=0
n=int(input())
res=0
a=list(map(int,input().split()))
b=sum(a)//n
c=b+1
for i in a:
    ans+=abs(i-b)**2
    res+=abs(i-c)**2
print(min(ans,res))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
ans = float('inf')
for i in range(-100, 101):
    dummy = 0
    for a_i in a:
        dummy += pow((a_i-i), 2)
    ans = min(ans, dummy)
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import re
import math
from collections import defaultdict
from collections import deque
from fractions import Fraction
import itertools
from copy import deepcopy
import random
import time
import os
import queue
import sys
import datetime
from functools import lru_cache
#@lru_cache(maxsize=None)
readline=sys.stdin.readline
sys.setrecursionlimit(2000000)
#import numpy as np
alphabet="abcdefghijklmnopqrstuvwxyz"
mod=int(10**9+7)
inf=int(10**20)
def yn(b):
    if b:
        print("yes")
    else:
        print("no")
def Yn(b):
    if b:
        print("Yes")
    else:
        print("No")
def YN(b):
    if b:
        print("YES")
    else:
        print("NO")
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def is_pow(a,b):#aはbの累乗数か
    now=b
    while now<a:
        now*=b
    if now==a:return True
    else:return False
def getbin(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def get_facs(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod_>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:return num
def get_primes(n,type="int"):
    if n==0:
        if type=="int":return []
        else:return [False]
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def is_prime(num):
    if(num<=1):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def ifelse(a,b,c):
    if a:return b
    else:return  c
def join(A,c=""):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s
def factorize(n,type_="dict"):
    b = 2
    list_ = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            list_.append(b)
        b+=1
    if n > 1:list_.append(n)
    if type_=="dict":
        dic={}
        for a in list_:
            if a in dic:
                dic[a]+=1
            else:
                dic[a]=1
        return dic
    elif type_=="list":
        return list_
    else:
        return None
def pm(x):
    return x//abs(x)
def inputintlist():
    return list(map(int,input().split()))
######################################################################################################
def main():
    n=int(input())
    A=inputintlist()
    ans=0
    a=round(sum(A)/len(A))
    for b in A:
        ans+=(a-b)**2
    print(ans)
main()

Submission status: Accepted

Solution code:
# coding: utf-8
import re
import math
from collections import defaultdict
from collections import deque
from fractions import Fraction
import itertools
from copy import deepcopy
import random
import time
import os
import queue
import sys
import datetime
from functools import lru_cache
#@lru_cache(maxsize=None)
readline=sys.stdin.readline
sys.setrecursionlimit(2000000)
#import numpy as np
alphabet="abcdefghijklmnopqrstuvwxyz"
mod=int(10**9+7)
inf=int(10**20)
def yn(b):
    if b:
        print("yes")
    else:
        print("no")
def Yn(b):
    if b:
        print("Yes")
    else:
        print("No")
def YN(b):
    if b:
        print("YES")
    else:
        print("NO")
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def is_pow(a,b):#aはbの累乗数か
    now=b
    while now<a:
        now*=b
    if now==a:return True
    else:return False
def getbin(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def get_facs(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod_>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:return num
def get_primes(n,type="int"):
    if n==0:
        if type=="int":return []
        else:return [False]
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def is_prime(num):
    if(num<=1):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def ifelse(a,b,c):
    if a:return b
    else:return  c
def join(A,c=""):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s
def factorize(n,type_="dict"):
    b = 2
    list_ = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            list_.append(b)
        b+=1
    if n > 1:list_.append(n)
    if type_=="dict":
        dic={}
        for a in list_:
            if a in dic:
                dic[a]+=1
            else:
                dic[a]=1
        return dic
    elif type_=="list":
        return list_
    else:
        return None
def pm(x):
    return x//abs(x)
def inputintlist():
    return list(map(int,input().split()))
######################################################################################################
def main():
    n=int(input())
    A=inputintlist()
    ans=inf
    for i in range(0,2):
        a=sum(A)//len(A)+i
        x=0
        for b in A:
            x+=(a-b)**2
        ans=min(ans,x)
    print(ans)
main()

Submission status: Accepted

Solution code:
# coding: utf-8
import re
import math
from collections import defaultdict
from collections import deque
from fractions import Fraction
import itertools
from copy import deepcopy
import random
import time
import os
import queue
import sys
import datetime
from functools import lru_cache
#@lru_cache(maxsize=None)
readline=sys.stdin.readline
sys.setrecursionlimit(2000000)
#import numpy as np
alphabet="abcdefghijklmnopqrstuvwxyz"
mod=int(10**9+7)
inf=int(10**20)
def yn(b):
    if b:
        print("yes")
    else:
        print("no")
def Yn(b):
    if b:
        print("Yes")
    else:
        print("No")
def YN(b):
    if b:
        print("YES")
    else:
        print("NO")
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def is_pow(a,b):#aはbの累乗数か
    now=b
    while now<a:
        now*=b
    if now==a:return True
    else:return False
def getbin(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def get_facs(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod_>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:return num
def get_primes(n,type="int"):
    if n==0:
        if type=="int":return []
        else:return [False]
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def is_prime(num):
    if(num<=1):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def ifelse(a,b,c):
    if a:return b
    else:return  c
def join(A,c=""):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s
def factorize(n,type_="dict"):
    b = 2
    list_ = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            list_.append(b)
        b+=1
    if n > 1:list_.append(n)
    if type_=="dict":
        dic={}
        for a in list_:
            if a in dic:
                dic[a]+=1
            else:
                dic[a]=1
        return dic
    elif type_=="list":
        return list_
    else:
        return None
def pm(x):
    return x//abs(x)
def inputintlist():
    return list(map(int,input().split()))
######################################################################################################
def main():
    n=int(input())
    A=inputintlist()
    ans=inf
    for a in range(-100,101):
        x=0
        for b in A:
            x+=(a-b)**2
        ans=min(ans,x)
    print(ans)
main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
cost = float("inf")
for i in range(-100, 101):
    tmp_cost = 0
    for a in A:
        tmp_cost += (a - i) ** 2
    cost = min(tmp_cost, cost)
print(cost)

Submission status: Accepted

Solution code:
N = int(input())
an = list(map(int,input().split()))
ave  = round((sum(an)/N),0)
ans = 0

for i in an:
    ans += (i-ave)**2

print(int(ans))

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int,input().split()))
b = sum(a)
b =  int((b+0.5*N) // N)
ans = 0
for i in range(N):
    ans += (a[i]-b)**2
print(ans)

Submission status: Accepted

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

import sys
import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n = ii()
    L = lmi()
    avg = sum(L) / n
    avg = math.ceil(avg) if math.ceil(avg) - avg <= avg - math.floor(avg) else math.floor(avg)
    print(sum([(elm - avg) ** 2 for elm in L]))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

ans = 10000000
for i in range(-100, 101):
  sm = 0
  for x in a:
    sm += (x-i) ** 2
  ans = min(ans, sm)
  
print(ans)

Submission status: Accepted

Solution code:
def main():
  n=int(input())
  num = list(map(int,input().split()))
  ave=round(sum(num)/len(num))
  ans=0
  for i in range(0,len(num)):
    ans+=(ave-num[i])*(ave-num[i])
  print(ans)

main()

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int,input().split()))
m = round(sum(l)/len(l))
ans = 0
for i in range(len(l)):
  ans += (m - l[i])**2

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin

def S(): return stdin.readline().rstrip()
def I(): return int(stdin.readline().rstrip())
def LS(): return list(stdin.readline().rstrip().split())
def LI(): return list(map(int,stdin.readline().rstrip().split()))

def cost(x,y):
    return pow(x-y,2)
n = I()
a = LI()

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

ave = round(sum/n)
if ave+0.5 <= sum/n:
    ave += 1

ans = 0
for i in range(n):
    ans += cost(a[i],ave)

print(ans)

Submission status: Accepted

Solution code:
def main():
    from collections import Counter
    n, *a = map(int, open(0).read().split())
    c = Counter(a)
    d = list(c.keys())
    x, y = min(d), max(d)
    ans = float("Inf")
    for i in range(x, y + 1):
        tmp = 0
        for k, v in c.items():
            tmp += (k - i) ** 2 * v
        ans = min(ans, tmp)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
num = int(sum(a) / len(a))
check = [num -3, num - 2, num -1, num, num + 1, num + 2, num +3]
ans = float('inf')
for i in check:
    cnt = 0
    for j in a:
        cnt += (i - j) ** 2

    ans = min(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
b = []
for i in range(a[0], a[n-1]+1) :
	ans = 0
	for j in range(len(a)) :
		ans = ans + (a[j]-i)**2
	b.append(ans)
print(min(b))

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
xs = [int(x) for x in input().split()]
a = int(np.average(xs))
b = a + 1
print(min(sum([(x - a) ** 2 for x in xs]), sum([(x - b) ** 2 for x in xs])))

Submission status: Accepted

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

def cino(test=False):
    if not test:
        return int(input())
    else:
        return input()
def cina():
  return list(map(int,input().split()))

a = cino()
l = cina()
ans = 10**18
for i in range(-100,101):
    cost = 0
    for j in range(len(l)):
        cost += (i-l[j])**2
    ans = min(ans,cost)
print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
MOD = 10**9+7
MAX = 10**18
n = int(input())
a = list(map(int,input().split()))
ans = MAX
for i in range(-100,101):
    cost = 0
    for j in range(n):
        cost += (i-a[j])**2
    ans = min(ans,cost)
print(ans)

Submission status: Accepted

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

ave = round(sum(a) / n)
ans = sum(map(lambda x: (ave - x) ** 2, a))
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
total=0
ans1=0
ans2=0
for i in a:
    total+=i
tmp1=total//n
tmp2=-(-total//n)
for i in a:
    ans1+=(i-tmp1)**2
for i in a:
    ans2+=(i-tmp2)**2
print(min(ans1,ans2))

Submission status: Accepted

Solution code:
n = int(input())
# n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
# abc = [int(input()) for i in range(5)]
if min(a) == max(a):
    print(0)
    exit()

ans = (max(a)*max(a))*n
for i in range(min(a), max(a)+1):
    total = 0
    for j in range(n):
        total += (a[j]-i)*(a[j]-i)
    if total < ans:
        ans = total


print(ans)

Submission status: Accepted

Solution code:
import numpy as np
input()
A = np.array(input().split(), dtype=np.int32)
print(min((A - i).dot(A - i) for i in range(-100, 101)))

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int,(input().split())))
nim = float("inf")
for i in range(-100,101):
    s = 0
    for j in a:
        s += (i-j)**2
    nim = min(nim,s)
print(nim)

Submission status: Accepted

Solution code:
N=int(input())
a=list(map(int,input().split()))
def change(a,x):
    sum=0
    for i in a:
        sum+=(x-i)**2
    return sum

def binarysearch(left,right,a):
    if right-left<=1:
        return min(change(a,left),change(a,right))
    else:
        center=left+(right-left)//2
        if change(a,center)<=change(a,center+1):
            return binarysearch(left,center,a)
        else:
            return binarysearch(center,right,a)

if change(a,100)<=change(a,99):
    print(change(a,100))
elif change(a,-100)<=change(a,-99):
    print(change(a,-100))
else:
    print(binarysearch(-100,100,a))

Submission status: Accepted

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

avg1 = sum(a) // n
avg2 = (sum(a) // n) + 1
ans1 = 0
ans2 = 0
for i in range(n):
    ans1 += abs(a[i] - avg1) ** 2
    ans2 += abs(a[i] - avg2) ** 2

print(min(ans1,ans2))

Submission status: Accepted

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

total = 0
for i in range(n):
    total += As[i]

# detect optimal number
ave = total / n

if ave != int(ave):
    if ave >= int(ave)+0.5:
        ave = int(ave)+1
    else:
        ave = int(ave)

ans = 0
for i in range(n):
    ans += (ave-As[i])**2

print(int(ans))

Submission status: Accepted

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

i = 0
m = 100
M = -100

s = 0
while i < n:
    s += a[i]
    i+=1

s1 = s//n
s2 = s1 + 1

i = 0
x1 = 0
x2 = 0
while i < n:
    x1 += (s1-a[i])**2
    x2 += (s2-a[i])**2
    i+=1

if x1<x2:
    ans = x1
else:
    ans = x2
print(ans)

Submission status: Accepted

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

    cost = 10**10

    for a in range(-200, 201):
        c = 0
        for i in range(N):
            c += (a - A[i])**2
        if c < cost:
            cost = c
    print(cost)
if __name__ == "__main__":
    main()

Submission status: Accepted

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

avg = 0
if (max(a)+min(a))%2 == 0:
    avg = (max(a)+min(a))/2
else:
    avg = (max(a)+min(a))/2+1

for i in range(-100,101,1):
    sum = 0
    for j in a:
        sum += (j-i)**2
    ans.append(sum)
    
print(min(ans))

Submission status: Accepted

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

x = int(sum(li)/len(li))
y = sum(li)/len(li)
if y-x > 0.5:
    x += 1

ans = 0

for i in li:
    ans += (i-x)**2

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
number = list(map(int, input().split()))
total_a = 0
total_b = 0
average = sum(number)//len(number)

for i in number:
    total_a += (average-i)**2
    total_b += (average+1-i)**2

print(min(total_a, total_b))

Submission status: Accepted

Solution code:
from math import ceil, floor

n = int(input())
ls = list(map(int, input().split()))
sqsm = 0
for i in range(n):
    sqsm += ls[i] * ls[i]
sm = sum(ls)
x1 = floor(sm / n)
x2 = ceil(sm / n)
print(min(sqsm + n * x1 * x1 - 2 * sm * x1, sqsm + n * x2 * x2 - 2 * sm * x2))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
max = max(a)
min = min(a)
cost_min = n * (max - min)**2
for m in range(min, max+1):
    cost = 0
    for x in a:
        cost += (x - m)**2
    if cost < cost_min:
        cost_min = cost
print(cost_min)

Submission status: Accepted

Solution code:
import statistics as st
import math
int(input())
s = list(map(int, input().split()))
md = math.floor(st.mean(s))
mu = md + 1
sd = 0
su = 0
for i in range(0, len(s)):
    sd = sd + (s[i] - md) ** 2
    su = su + (s[i] - mu) ** 2
print(min(sd, su))

Submission status: Accepted

Solution code:
def c_be_together():
    N = int(input())
    A = [int(i) for i in input().split()]
    a_ave = sum(A) // N
    return min(sum([(a - option)**2 for a in A]) for option in (a_ave, a_ave + 1))

print(c_be_together())

Submission status: Accepted

Solution code:
n = int(input())
x = list(map(int,input().split()))
ave = sum(x)//n
sum1=0
sum2=0
for i in range(n):
    sum1+=(x[i]-ave)*(x[i]-ave)
    sum2+=(x[i]-ave-1)*(x[i]-ave-1)
print(min(sum1,sum2))

Submission status: Accepted

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

ans = 10**9
for num in range(-100, 101):
    temp = 0
    for i in range(n):
        temp += (num - a[i])**2
    ans = min(ans, temp)

print(ans)

Submission status: Accepted

Solution code:
def resolve():
    N = int(input())
    A = sorted(list(map(int, input().split())))
    start, end = min(A), max(A)
    mincost = float("inf")
    for i in range(start, end+1):
        _cost = 0
        for a in A:
            _cost += abs(a-i)**2
        mincost = min(mincost, _cost)
    print(mincost)


if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:
import numpy as np

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

a_min=np.min(a)
a_max=np.max(a)

cost_list=[]
for i in range(a_min, a_max+1):
  
  cost=0
  for val in a:
    cost+=(val-i)**2
    
  cost_list.append(cost)
  
min_cost=np.min(cost_list)

print(min_cost)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
mins=100**2*n
for i in range(min(a),max(a)+1):
  sum=0
  for j in range(n):
    sum+=abs(a[j]-i)**2
  if sum<mins:
    mins=sum
print(mins)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
mean = sum(a)//n
ansl = 0
anss = 0
for i in range(n):
    ansl += (a[i]-mean)**2
    anss += (a[i]-mean-1)**2

print(min(ansl,anss))

Submission status: Accepted

Solution code:
#! python3
import math

def main():
    N = int(input())
    alist = [int(num) for num in input().split()]
    ans1 = 0
    ans2 = 0
    m = sum(alist) / N

    if sum(alist) % N == 0:
        ans = 0
        for i in range(N):
            ans += (alist[i] - m)**2
    else:
        mu = math.floor(m)
        mo = math.ceil(m)
        for i in range(N):
            ans1 += (alist[i] - mu)**2
            ans2 += (alist[i] - mo)**2

        if ans1 <= ans2:
            ans = ans1
        else:
            ans = ans2

    print(int(ans))


main()

Submission status: Accepted

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

x = sum(a)
if x > 0:
  x = int(x/N+0.5)
else:
  x = int(x/N-0.5)

total = 0
if a[0] == x and a[-1] == x:
  print(0)
else:  
  for i in range(N):
    total += (x-a[i])**2
  print(int(total))

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    n = int(input())
    lst = list(map(int, input().split()))

    ans = (50*100)*(50*100)
    for i in range(-100,101):
        mn = 0
        for c in lst:
            mn += (i-c)*(i-c)
        ans = min(ans,mn)

    print(ans)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    n = int(input())
    lst = list(map(int, input().split()))

    ans = (50*101)*(50*101)
    for i in range(-100,101):
        mn = 0
        for c in lst:
            mn += (i-c)*(i-c)
        ans = min(ans,mn)

    print(ans)

Submission status: Accepted

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

M = max(lst)
m = min(lst)
ans = float("INF")

for i in range(m,M+1):
    num = 0
    for j in lst:
        num += (i-j)**2
    ans = min(ans, num)

print(ans)

Submission status: Accepted

Solution code:
n= int(input())
a= list(map(int,input().split()))
maxa,mina=max(a),min(a)
if maxa==mina:print(0)
else:
    gmin=9999999
    for c in range(mina,maxa+1):gmin=min(gmin,sum([(c-b)*(c-b) for b in a]))
    print(gmin)

Submission status: Accepted

Solution code:
# N  =int(input())
# a = list(map(int,input().split()))
# ans = (10**9)
# for av in range(min(a),max(a)+1):
#     Sum = 0
#     for i in range(N):
#         Sum += (a[i]-av)**2
#     if Sum < ans:
#         ans = Sum
# print(ans)

N  =int(input())
a = list(map(int,input().split()))
b = list(set(a))
ans = (10**9)
for av in range(min(a),max(a)+1):
    Sum = 0
    for i in range(N):
        Sum += a[i]**2-2*a[i]*av+av**2
    if Sum < ans:
        ans = Sum
print(ans)

Submission status: Accepted

Solution code:
N  =int(input())
a = list(map(int,input().split()))
ans = (10**9)
for av in range(min(a),max(a)+1):
    Sum = 0
    for i in range(N):
        Sum += (a[i]-av)**2
    if Sum < ans:
        ans = Sum
print(ans)

Submission status: Accepted

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

ans =10**8
for i in range(-100,101):
    cost = 0
    for k in a:
        cost += (k-i)**2
    ans = min(cost,ans)

print(ans)

Submission status: Accepted

Solution code:
q = int(input())

l = [int(x) for x in input().split(' ')]

avarage = round(sum(l)/q)

cost = 0
for i in range(q):
    cost += (l[i]-avarage)**2

print(cost)