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:
while 1:
    try:
        n=int(input())
        a=list(map(int,input().split()))
    except: break

    res=float('inf')
    for p in range(min(a),max(a)+1):
        res=min(res,sum((x-p)**2 for x in a))
    print(res)

Submission status: Accepted

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

Submission status: Accepted

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

m = sum(a)//N

ans1 = 0
ans2 = 0
ans3 = 0
for k in range(N):
    ans1 += (a[k]-m)**2
    ans2 += (a[k]-m-1)**2
    ans3 += (a[k]-m+1)**2

print(min(ans1,ans2,ans3))

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
Y=sum(A) // N
Sol=10**9
for y in range(Y-2,Y+2):
    Sol=min(Sol,sum(((a-y)**2 for a in A)))
print(Sol)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys

def s():
    return raw_input().strip()
def n():
    return int(raw_input())
def d():
    return float(raw_input())

def ls():
    return raw_input().strip().split()
def ln():
    return map(int, raw_input().strip().split())
def ld():
    return map(float, raw_input().strip().split())

def fs():
    return [raw_input().strip() for i in xrange(input())]
def fn():
    return [int(raw_input().strip()) for i in xrange(input())]
def fd():
    return [float(raw_input().strip()) for i in xrange(input())]

N = n()
A = ln()

min = 10e8
for i in xrange(-100, 101):
    s = 0
    for a in A:
        s += (a - i) ** 2
    if s < min:
        min = s
print min

Submission status: Accepted

Solution code:
N = int(raw_input())
a = map(int,raw_input().split())
ans =  10**9+7
for i in xrange(-100,101):
	cost = sum((i-a[j])**2 for j in xrange(N))
	if cost < ans:
		ans = cost
print ans

Submission status: Accepted

Solution code:


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

res = 1<<30
cand = -100
while cand <= 100:
    tmp = 0
    for a in A:
        dif = cand - a
        tmp += dif*dif
    res = min(res, tmp)


    cand += 1

print(res)

Submission status: Accepted

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

Submission status: Runtime Error

Solution code:
n = int(input())
x = sorted(list(map(int, input().split())), reverse = True)
x_2 = list(map(lambda x:x ** 2, x))
ichi = sum(x)
jijou = sum(x_2)
re = 10 ** 100


#def ji(p, x):
#    ans = p * (p - 2 * x)
#    return ans

for p in range(x[n], x[0] + 1):
    second = n * (p ** 2)
    third = -2 * p * ichi
    summ = jijou + second + third

    if re > summ:
        re = summ

print(re)

#for i in range(x[i]):

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
Sum =0
for i in range(len(A)):
  Sum += (A[0]-A[i])**2
Answer = Sum
for j in range(len(A)):
  Sum =0
  for k in range(-100,101):
    Sum+= (A[k]-j)**2
  Answer =min(Answer, Sum)
print(Answer)

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
Sum =0
for i in range(len(A)):
  Sum += (A[0]-A[i])**2
Answer = Sum
for j in range(-100,101):
  Sum =0
  for k in range(len(A)):
    Sum+= (A[k]-A[j])**2
  Answer =min(Answer, Sum)
print(Answer)

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,inout().split()))
Sum =0
for i in range(len(N)):
  Sum += (A[0]-A[i])**2
Answer = Sum
for j in range(len(N)):
  Sum =0
  for k in range(len(N)):
    Sum+= (A[k]-A[j])**2
  Answer =min(Answer, Sum)
print(Answer)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=sorted(a)
x=a[0]
y=a[n-1]
if x==y:
  print(0)
else:
  d=[]
  for i in range(x,y+1):
    c=0
    for v in range(n):
      c+=(i-a[v])**2
    d.append(c)
    continue
  d=sorted(d)
  print(d[0])

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=sorted(a)
x=a[0]
y=a[n-1]
if x==y:
  print(0)
else:
  d=[]
  for i in range(x,y):
    c=0
    for v in range(n):
      c+=(i-a[v])**2
    d.append(c)
    continue
  d=sorted(d)
  print(d[0])

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=sorted(a)
x=a[0]
y=a[n-1]
d=[]
for i in range(x,y):
  c=0
  for v in range(n):
    c+=(i-a[v])**2
  d.append(c)
  continue
d=sorted(d)
print(d[0])

Submission status: Runtime Error

Solution code:
def main():
    input = stdin.buffer.readline
    n = int(input())
    a = list(map(int, input().split()))
    x1 = sum(a) // n
    x2 = x1 + 1
    ans1 = 0
    ans2 = 0
    for ai in a:
        ans1 += (ai - x1) ** 2
        ans2 += (ai - x2) ** 2

    print(min(ans1, ans2))


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Runtime Error

Solution code:
from math import factorial,sqrt,ceil,gcd
import numpy as np

N = int(input())
lisA = list(map(int,input().split()))
arrA = np.array(lisA)

mean = np.mean(arrA)

targetnum = round(mean)

arrans = (arrA - targetnum)**2
ans = sum(arrans)

print(ans)

Submission status: Runtime Error

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

ave = round(sum(a)/n)
ans = 0

for _a in a:
    ans += (_a - ave)**2

print(ans1)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

print(min(b))

Submission status: Runtime Error

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

print(min(b))

Submission status: Runtime Error

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

print(min(b))

Submission status: Runtime Error

Solution code:
import math
N, *a = map(int, open(0).read().split())
ave = math.round(sum(a) / N)
ans = 0
for x in a:
  ans += (x - ave) * (x - ave)
print(ans)

Submission status: Runtime Error

Solution code:
# coding: utf-8
from math import ceil
from statistics import median, mean
N = int(input())
A = list(map(int, input().split()))
A.sort()
if N % 2 == 0:
    m = ceil((A[N//2] + A[N//2+1]) / 2)
else:
    m = A[N//2]
ans = 0
for i in range(N):
    ans += (A[i] - m)**2
print(ans)

Submission status: Runtime Error

Solution code:
def main(n, a):
    base = (max(a) + min(a)) / 2
    ans = 0

    for n in a:
        ans += (n - base)**2

    print(round(ans))


if __name__ == '__main__':
    n = int(input())
    a = map(int, input().split())

    main(n, a)

Submission status: Runtime Error

Solution code:
from statistics import mean
n = int(input())
a = list(map(int, input().split()))
t = round(mean(a))

sum = 0
for t in a:
    sum += (i - t)**2

print(sum)

Submission status: Runtime Error

Solution code:
n = int(input())
s = len(input())
mod = 10**9+7
dp = [[0]*(n+1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(1,n+1):
  dp[i][0] = (dp[i-1][0] + dp[i-1][1])%mod
  for j in range(1,min(n,i+1)):
    dp[i][j] = (dp[i-1][j-1]*2 + dp[i-1][j+1])%mod
  dp[i][n] = dp[i-1][n-1]*2%mod
s2 = pow(2,s,mod)
rev = pow(s2,mod-2,mod)
print(dp[n][s]*rev%mod)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N = int(input())
NUM = list(map(int,input().split()))
MAX = max(NUM)
MIN = min(NUM)
COSTLIST = []
for i in range (MIN,MAX):
    COST = 0
    for j in NUM:
        COST += (j-i)**2
    COSTLIST.append(COST)
MINIMUM = min(COSTLIST)

print(MINIMUM)

Submission status: Runtime Error

Solution code:
n=int(input())
l=[int(input()) for i in range(n)]
s=sum(l)/n
if s-int(s)<int(s)+1-s:
  s=int(s)
else:
  s=int(s)+1
ans=0
for i in l:
  ans+=(s-i)**2
print(ans)

Submission status: Runtime Error

Solution code:
#include <iostream>
using namespace std;

int N;
int x[210];
bool t = true;
int s = 0;
int main(){
    int ms = 10000000000;
    int t = 1;
    cin >> N;
    for (int i = 0; i < N; ++i)cin >> x[i];
        for (int j = -100; j <= x[N-1]; ++j){
        s = 0;
             for (int i = 0; i < N; ++i){
            int p = x[i] - j;
            //cout << p << endl;
            s += p * p;
        }
        //cout << s << endl;
        if (s < ms){
            ms = s;
            t = j;
        }
    }
    cout << ms << endl;
}

Submission status: Runtime Error

Solution code:

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

a=np.array(a)
min_s = 10**29
for i in range(201):
    s=np.sum((a-np.ones(N)*(i-100))**2)
    min_s = min(int(s),min_s)
print(min_s)

Submission status: Runtime Error

Solution code:
MOD = (10 ** 9) + 7

N = int(input())
s = list(input())

dp = [[0 for i in range(N + 1)] for j in range(N + 1)]


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

for n in range(1, N + 1):
	dp[n][0] = (dp[n - 1][0] + 2 * dp[n - 1][1]) % MOD
	for l in range(1, n):
		dp[n][l] = (dp[n - 1][l - 1] + 2 * dp[n - 1][l + 1]) % MOD

print(dp[N - 1][len(s)])

Submission status: Runtime Error

Solution code:
MOD = (10 ** 9) + 7

N = int(input())
s = list(input())

dp = [[0 for i in range(N + 1)] for j in range(N + 1)]


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

for n in range(1, N + 1):
	dp[n][0] = (dp[n - 1][0] + 2 * dp[n - 1][1]) % MOD
	for l in range(1, n):
		dp[n][l] = (dp[n - 1][l - 1] + 2 * dp[n - 1][l + 1]) % MOD

print(dp[N - 1][len(s)])

Submission status: Runtime Error

Solution code:
import math

N = int(input())
a = list(map(int, input().split()))
cost = math.inf
for i in range(-100, 101):
    temp = 0
    for a_i in a:
        temp += (a_i-i)**2
    cost = min(cost, temp)
print(cost)

Submission status: Runtime Error

Solution code:

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


total_cost = float('inf')
for n in range(-100, 101):
    cost = 0
    for i in range(N):
        cost += (a[i] - n) ** 2
    total_cost = min(total_cost, cost)
print(total_cost)

Submission status: Runtime Error

Solution code:
s=raw_input()
n=len(s)
cnt=[[0]*26 for _ in xrange(n+1)]
for i in xrange(n):
    for j in xrange(26):
        cnt[i+1][j]=cnt[i][j]
    cnt[i+1][ord(s[i])-ord("a")]+=1
if n==2:
    if s[0]==s[1]:
        print 1,2
        quit()
    else:
        print -1,-1
        quit()
for i in xrange(n):
    for j in xrange(i+3,n+1):
        max_cnt=0
        for k in xrange(26):
            max_cnt=max(max_cnt,cnt[j][k]-cnt[i][k])
        if (j-i)/2<max_cnt:
            print i+1,j
            quit()
print -1,-1

Submission status: Runtime Error

Solution code:
def cost(n, a, m):

  hihumi = 0  #hihumi => 滝本ひふみ

  for i in range(n):
    hihumi += (a[i] - m) ** 2

  return hihumi

N = int(raw_input())
a = map(int, raw_input().split())

ans = 100

for i in range(min(a), max(a) + 1):
  if (ans > cost(N, a, i)):
    ans = const(N, a, i)

print ans