/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 200 点
問題文
N 個の整数 a_1,a_2,..,a_N が与えられます。えび君はこれらを書き換えて全て同じ整数にしようとしています。各a_i (1≦i≦N)は高々一回しか書き換えられません(書き換えなくても良い)。整数xを整数yに書き換えるとき、コストが(x-y)^2かかります。仮にa_i=a_j (i≠j)だとしても、ひとつ分のコストで同時に書き換えることは出来ません(入出力例2 を参照)。えび君が目的を達成するのに必要なコストの総和の最小値を求めてください。
制約
- 1≦N≦100
- -100≦a_i≦100
入力
入力は以下の形式で標準入力から与えられる。
N a_1 a_2 ... a_N
出力
えび君が全てを同じ整数に書き換えるのに必要なコストの総和の最小値を出力せよ。
入力例 1
2 4 8
出力例 1
8
全てを6に書き換えると、コストの総和は(4-6)^2+(8-6)^2=8となり、これが最小です。
入力例 2
3 1 1 3
出力例 2
3
全てを2に書き換えると(1-2)^2+(1-2)^2+(3-2)^2=3となります。各a_iごとに書き換えるので、二つの1を一度にコスト(1-2)^2で書き換えられるわけではないことに注意してください。
入力例 3
3 4 2 5
出力例 3
5
4は書き換えずに、2と5を共に4に書き換えることで(2-4)^2+(5-4)^2=5が達成できて、これが最小です。
入力例 4
4 -100 -100 -100 -100
出力例 4
0
何も書き換えなくともえび君は目的を達成しています。よってこの場合コストは0です。
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.