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()))
b = 0
for i in range(N):
    b += a[i]
r = round(b/N)
ans = 0
for i in range(N):
    ans += (a[i]-r)**2
print(ans)

Submission status: Accepted

Solution code:
def cost(x):
    cost = (x - ave)**2
    return cost


n = input()
a = list(map(int, input().split()))
ave = round(sum(a)/int(n))
print(sum(list(map(cost, a))))

Submission status: Accepted

Solution code:
n = input()
a = list(map(int, input().split()))
ans = list()
for i in range(min(a), max(a)+1):
    cost = 0
    for num in a:
        cost += (num - i)**2
    ans.append(cost)
print(min(ans))

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
ans=float('inf')
for v in range(min(l),max(l)+1):
    c=sum([(a-v)**2 for a in l])
    ans=min(ans,c)
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=[int(x) for x in input().split()]
maxA=max(A)
minA=min(A)
ans=10**9
for i in range(minA,maxA+1):
    kouho=0
    for j in range(N):
        kouho+=(i-A[j])**2
    ans=min(ans,kouho)
print(ans)

Submission status: Accepted

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

a_u = round(sum(a)/n)
a_d = int(sum(a)/n)
ans_u = 0
ans_d = 0
for i in range(n):
    ans_u += (a[i]-a_u)**2
    ans_d += (a[i]-a_d)**2
print(min(ans_u,ans_d))
#print(round(-2.5),int(-2.5))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
int_list = [int(x) for x in input().split()]

# int_listの各整数をyに書き換えるときのコストの総和を計算
def calc_cost(int_list, y):
    cost = 0
    for x in int_list:
        cost += (x - y)**2
    return cost

cost_list = [calc_cost(int_list, y) for y in range(min(int_list), max(int_list)+1)]
print(min(cost_list))

Submission status: Accepted

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

min_cost = 10 ** 9 + 7
for i in range(-100, 101):
    cost = 0
    for j in range(N):
        cost += (A[j] - i) ** 2
    min_cost = min(cost, min_cost)

print(min_cost)

Submission status: Accepted

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

def cost(x,y):
    return (x-y)**2

avg = round(sum(nums)/len(nums))

res = 0
for n in nums:
    res += cost(n, avg)
print(res)

Submission status: Accepted

Solution code:

n = int(raw_input())
ais = map(int, raw_input().split())
ais.sort()
vv= sum(ais)/len(ais)
def g(ais,m):
	s= 0
	for ai in ais: s+=abs(ai - m) **2
	return s
print min([g(ais,m) for m in [vv+dela for dela in [-1,0,+1]]])

Submission status: Accepted

Solution code:

n = int(raw_input())
ais = map(int, raw_input().split())
ais.sort()

def f(ais):
	return [sum(ais)/len(ais),sum(ais)/len(ais)+1,sum(ais)/len(ais)-1]
	if len(ais) % 2:
		return [ais[len(ais)/2]]
	
	v = ais[len(ais)/2 -1] + ais[len(ais)/2]
	return [v/2,v/2-1,v/2+1]
def g(ais,m):
	s= 0
	for ai in ais: s+=abs(ai - m) **2
	return s
print min([g(ais,m) for m in f(ais)])

Submission status: Accepted

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

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

ans = 1000100
ch = 0 
for ch in range(min(a), max(a)+1):
    tmp = 0 
    for i in range(n):
        tmp += (a[i]-ch)**2
    if tmp <= ans:
        ans = tmp 
print(ans)

Submission status: Accepted

Solution code:
inf = float('inf')
n = int(input())
arr = list(map(int, input().split()))

min_cost = inf
for i in range(-100, 101):
    cost = 0
    for j in arr:
        cost += (j - i)**2
    min_cost = min(min_cost, cost)
print(min_cost)

Submission status: Accepted

Solution code:
num = int(input())
str_line = input().split(" ")
num_line = [int(n) for n in str_line]

ave = 0
for i in range(num):
    ave += num_line[i]

if ave%num == 0:
    ave //= num

else:
    if ave%num <= num/2:
        ave //= num
    else:
        ave = -(-ave//num)

wa = 0
for i in range(num):
    temp = num_line[i] - ave
    wa += temp*temp
    
print(wa)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    inlis = list(map(int, input().split()))

    ans = 10 ** 10

    for kouho1 in range(-100,101):
        tmp1 = 0
        for i in range(n):
            tmp1 += (inlis[i]- kouho1) ** 2
        if tmp1 < ans:
            ans = tmp1
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
lst = list(map(int, input().split()))
avg = round(sum(lst) / N)

result = 0
for i in lst:
    result += (i - avg)**2

print(result)

Submission status: Accepted

Solution code:
import sys
import math

def main():

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

    y = round(sum(a)/len(a))

    ans = 0
    for i in a:
        ans += pow((i - y), 2)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
maxa=(10)**11
N=int(input())
L=list(map(int,input().split()))
for i in range(-100,101):
  R=[(i-y)**2 for y in L]
  a=sum(R)
  maxa=min(maxa,a)
print(maxa)

Submission status: Accepted

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

res = float('inf')
for i in range(-100, 101):
    s = 0
    for v in a:
        s += (v - i) ** 2
    res = min(res, s)

print(res)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(T) for T in input().split()]
Min = 10**9
for TN in range(min(A),max(A)+1):
    Min = min(Min,sum((TN-TA)**2 for TA in A))
print(Min)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
m=int(round(sum(a)/n,0))
ans=0
for i in a:
  ans+=(i-m)**2
print(ans)

Submission status: Accepted

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

inf=float('inf')

ans=inf

for b in range(-100,101):
  ch=0
  for i in range(n):
    ch+=(b-a[i])**2
    
  ans=min(ans,ch)
  
print(ans)

Submission status: Accepted

Solution code:
def keisan(N,A):
     
     KAI = 0
     A.sort
 
     min = -100
     max = 101
     
     i = min
     
     while i <= max:
         kari = 0
         j = 0
         while j < N:
             kari += (A[j]-i)**2
             j += 1
        
         
         if kari <= KAI or i == min:
             KAI = kari
         i += 1
 
     
     return KAI
 
 
N = int(input())
 
A = input().split()
int_list = list(map(int,A))
 
print(keisan(N,int_list))

Submission status: Accepted

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
a.sort()
ans = []
for i in range(a[0], a[-1]+1):
    cnt = 0
    for j in range(n):
        cnt += (a[j] - i)**2
    ans.append(cnt)

print(min(ans))

Submission status: Accepted

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

a.sort()

def cost(a, y):
    ans = 0
    for i in a:
        ans += (i - y) * (i - y)
    return ans

# binary search

left = a[0]
right = a[n-1]

while left < right:
    center = (left + right) // 2
    if cost(a, center) < cost(a, center+1):
        right = center
    else:
        left = center + 1

print(cost(a, left))

Submission status: Accepted

Solution code:
import math
 
N = int(input())
A = [int(a) for a in input().split(" ")]
ave = sum(A) / N
can1 = math.floor(ave)
can2 = math.ceil(ave)
 
cost1 = sum([(a - can1) ** 2 for a in A])
cost2 = sum([(a - can2) ** 2 for a in A])
print(min([cost1, cost2]))

Submission status: Accepted

Solution code:
from math import *
n=int(input())
l=list(map(int,input().split()))
s=ceil(sum(l)/n)
ss=s-1
c=0
x=0
for i in range(n):
    c+=(s-l[i])**2
for i in range(n):
    x+=(ss-l[i])**2
print(min(c,x))

Submission status: Accepted

Solution code:
n=int(input())
a=[int(i)for i in input().split()]
cost=[]
for i in range(-100,101):
    tmp=0
    for j in a:
        tmp+=(j-i)**2
    cost.append(tmp)
print(min(cost))

Submission status: Accepted

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

l=a[0]
r=a[-1]

ans=float('inf')
for pin in range(l,r+1):
  cnt=0
  for i in range(n):
    cnt+=(a[i]-pin)**2
    
  ans=min(ans,cnt)
  
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

input()
a = np.array(sorted(map(int, input().split())))
print(min(sum((a - i) ** 2) for i in range(min(a), max(a) + 1)))

Submission status: Accepted

Solution code:
# @oj: atcoder
# @id: hitwanyang
# @email: 296866643@qq.com
# @date: 2020-08-14 10:16
# @url:https://atcoder.jp/contests/abc043/tasks/arc059_a
import sys,os
from io import BytesIO, IOBase
import collections,itertools,bisect,heapq,math,string
from decimal import *
# region fastio

BUFSIZE = 8192

BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
# ------------------------------
def main():
    n=int(input())
    a=list(map(int,input().split()))
    mn,mx=min(a),max(a)
    ans=10**9
    for i in range(mn,mx+1):
        temp=0
        for j in a:
            temp+=(j-i)*(j-i)
        ans=min(ans,temp)
    print (ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

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

a_sum = sum(a_list)
f = a_sum // n
c = (a_sum + n - 1) // n
b = f if abs(a_sum - f * n) < abs(a_sum - c * n) else c

ans = 0
for a in a_list:
    ans += (a - b) ** 2
print(ans)

Submission status: Accepted

Solution code:
# C - いっしょ
def main():
    import math
    _ = int(input())
    a = list(map(int, input().split()))
    t = float('inf')

    for i in range(min(a), max(a)+1):
        cnt = 0
        for j in a:
            cnt += (j-i)**2
        else:
            if cnt < t:
                t = cnt
    else:
        print(t)

    
if __name__ ==  "__main__":
    main()

Submission status: Accepted

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

def calc_cost(x,avg):
  return (x-avg)**2

avg = sum(a)//N

delta = [-2,-1,0,1,2]

ans=10**20
for i in range(len(delta)):
  val = sum(map(lambda x:calc_cost(x,avg+delta[i]),a))
  ans = min(ans,val)
  
print(ans)

Submission status: Accepted

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

t = 10**9
for i in range(min(a),max(a)+1):
    num = 0
    for h in a:
        num += (h-i)**2
    if num <= t:
        t = num
print(t)

Submission status: Accepted

Solution code:
import math
import statistics
N = int(input())
A = [int(x) for x in input().split()]
avg = math.floor(statistics.mean(A))
a = 0
b = 0
for i in range(len(A)):
    a += (A[i] - avg)**2
    b += (A[i] - avg - 1)**2
print(min(a,b))

Submission status: Accepted

Solution code:
n = int(input())
a_list = list(map(int,input().split()))
mid = round(sum(a_list)/n)
ans = 0
for a in a_list:
    ans += (a-mid) ** 2
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
# n=2
# a=[4,8]
minimum=10000000
for i in range(-100,101):
    cost=0
    for j in range(n):
        cost+=(i-(a[j]))**2
        if j==n-1:
            if cost<minimum:
                minimum=cost

print(minimum)

Submission status: Accepted

Solution code:
N = input()
list1 = list(map(int,input().split()))
list2 = []
for i in range(min(list1),max(list1)+1):
    a = 0
    for j in range(len(list1)):
        a += (list1[j] - i)**2
    list2.append(a)
print(min(list2))

Submission status: Accepted

Solution code:
N=int(input())
s=list(map(int,input().split()))
s_max=max(s)
s_min=min(s)
A=[]
for i in range(s_min,s_max+1):
  b=0
  for j in s:
    b+=(j-i)**2
  A.append(b)
print(min(A))

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int, input().split()))
b = []
for i in range(-100, 101):
	t = 0
	for j in a:
		t += (j - i) ** 2
	b.append(t)
print(min(b))

Submission status: Accepted

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

avg = round(sum(a) / n)

cost = 0

for e in a:
    cost += (e-avg)**2

print(cost)

Submission status: Accepted

Solution code:
N,*a = open(0).read().split()

N=int(N)

list1=list(map(int,a))

#print(N)

#print(list1)

a=[]

for i in range(-100,101):
    int1=0
    for n in range(N):
        x = (list1[n]-i)
        y = x**2
        int1+=y
        if n==N-1:
            a.append(int1)
    
#print(a)

#print(max(a))

print(min(a))

Submission status: Accepted

Solution code:
import statistics
import math
n = int(input())
a = list(map(int,input().split()))
ans1,ans2 = 0,0
a_avr1 = math.ceil((statistics.mean(a)))
a_avr2 = math.floor((statistics.mean(a)))
for i in range(n):
  ans1 += (a[i] - a_avr1)**2
  ans2 += (a[i] - a_avr2)**2
print(min(ans1,ans2))

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int, input().split()))
avg = round(sum(a)/N)
sums = []
for i in range(min(a), avg+1):
    s = 0
    for j in range(N):
        s += (i-a[j])**2
    sums.append(s)
print(min(sums))

Submission status: Accepted

Solution code:

N = int(input())
list = [int(a) for a in input().split()]

A = sum(list)//N
ans = 0

for k in range(N):
    ans = ans + (list[k] - A) ** 2

for i in range(-100,100):
    sum_new = 0
    for j in range(N):
        sum_new = sum_new + (list[j] - i) ** 2
    if(ans > sum_new):
        ans = sum_new

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
l = list(map(int,input().split()))
l_ans = [[] for _ in range(201)]

for i in range(-100,101):
    sum = 0

    for j in range(N):
        sum = sum + (i-l[j])**2

    l_ans[i+100] = sum

print(min(l_ans))

Submission status: Accepted

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

start = round(sum(L) / N)
f = lambda x: (x - start)**2

print(sum(list(map(f, L))))

Submission status: Accepted

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

m = sum(a)//n
ans = float("inf")
for i in range(m, m+2):
  t = 0
  for j in a:
    t += abs(j-i)**2
  ans = min(t,ans)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from sys  import stdin,stdout

import bisect

import math

def st():
    return list(stdin.readline().strip())

def inp():
    return int(stdin.readline())

def li():
    return list(map(int,stdin.readline().split()))

def mp():
    return map(int,stdin.readline().split())

def pr(n):
    stdout.write(str(n)+"\n")

def soe(limit):
    l=[1]*(limit+1)
    prime=[]
    for i in range(2,limit+1):
        if l[i]:
            for j in range(i*i,limit+1,i):
                l[j]=0

    for i in range(2,limit+1):
        if l[i]:
            prime.append(i)
    return prime

def segsoe(low,high):
    limit=int(high**0.5)+1
    prime=soe(limit)
    n=high-low+1
    l=[0]*(n+1)
    for i in range(len(prime)):
        lowlimit=(low//prime[i])*prime[i]
        if lowlimit<low:
            lowlimit+=prime[i]
        if lowlimit==prime[i]:
            lowlimit+=prime[i]
        for j in range(lowlimit,high+1,prime[i]):
            l[j-low]=1
    for i in range(low,high+1):
        if not l[i-low]:
            if i!=1:
                print(i)
                
def gcd(a,b):
    while b:
        a=a%b
        b,a=a,b
    return a

def power(a,n):
    r=1
    while n:
        if n&1:
            r=(r*a)
        a*=a
        n=n>>1
    return r

def check(n,l):
    s=0
    for i in range(len(l)):
        s+=(l[i]-n)*(l[i]-n)
    return s

def solve():
    n=inp()
    x=[]
    l=li()
    for i in range(min(l),max(l)+1):
        x.append(check(i,l))
    pr(min(x))
        

for _ in range(1):
    solve()

Submission status: Accepted

Solution code:
import math
import collections
import fractions
import itertools
import functools
import operator

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    cost = []
    for i in range(-100, 101):
        ramen = 0
        for j in range(n):
            ramen += abs(a[j]-i)**2
        cost.append(ramen)
    print(min(cost))
    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
n=int(input())
X=list(map(int, input().split()))
y=round(sum(X)/n)
cost=0
for x in X:
    cost+=(x-y)**2

print(cost)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int,input().split()))
    listcost = []
  
    for i in range(min(a),max(a)+1):
        cost = 0
        for j in a:
            if i != j:
                cost += (i - j) ** 2
        listcost.append(cost)
    print(min(listcost))
  
  
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
import numpy as np
import math

N = int(input())

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

avr = np.average(a)

av1 = math.floor(avr)
av2 = math.ceil(avr)

res1 = 0
res2 = 0

for num in a:
    res1 += (num - av1) ** 2
    res2 += (num - av2) ** 2

print(min(res1, res2))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

def main():

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

    cost = 0
    listCost = []

    for i in range(min(a), max(a)+1):
        for j in a:
            if i != j:
                cost += (i - j) ** 2

        listCost.append(cost)
        cost = 0

    ans = min(listCost)

    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))

N = I()
a = LI()

x = sum(a)//N
y = x + 1

print(min(sum((i-x)**2 for i in a),sum((i-y)**2 for i in a)))