C - Be Together

Contest Duration: 2016-08-13(Sat) 12:00 - 2016-08-13(Sat) 13:40 (local time) (100 minutes) Back to Home

C - Be Together Editorial

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$

出力

えび君が全てを同じ整数に書き換えるのに必要なコストの総和の最小値を出力せよ。

入力例 1Copy

Copy

2
4 8

出力例 1Copy

Copy

全てを $6$ に書き換えると、コストの総和は $(4-6)^2+(8-6)^2=8$ となり、これが最小です。

入力例 2Copy

Copy

3
1 1 3

出力例 2Copy

Copy

全てを $2$ に書き換えると $(1-2)^2+(1-2)^2+(3-2)^2=3$ となります。各 $a_i$ ごとに書き換えるので、二つの $1$ を一度にコスト $(1-2)^2$ で書き換えられるわけではないことに注意してください。

入力例 3Copy

Copy

3
4 2 5

出力例 3Copy

Copy

$4$ は書き換えずに、 $2$ と $5$ を共に $4$ に書き換えることで $(2-4)^2+(5-4)^2=5$ が達成できて、これが最小です。

入力例 4Copy

Copy

4
-100 -100 -100 -100

出力例 4Copy

Copy

何も書き換えなくともえび君は目的を達成しています。よってこの場合コストは $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 1Copy

Copy

2
4 8

Sample Output 1Copy

Copy

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

Sample Input 2Copy

Copy

3
1 1 3

Sample Output 2Copy

Copy

Transforming the all into $2$ s 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 $1$ s.

Sample Input 3Copy

Copy

3
4 2 5

Sample Output 3Copy

Copy

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

Sample Input 4Copy

Copy

4
-100 -100 -100 -100

Sample Output 4Copy

Copy

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