프로그램 명: usa_skidesign
제한시간: 1 초

[요약] N개의 언덕이 있고, 각 고지가 주어질 때, 각 고지를 깎거나, 쌓아올릴 수 있다(단, 깎거나 쌓아올릴때 비용은 [깎거나 쌓아올린 높이]^2이다. ) 최소고도의 고지와 최대고도의 고지의 차이가 17이 넘지 않게 만들때, 최소 비용을 구하는것이 문제이다.

Farmer John has N hills on his farm (1 <= N <= 1,000), each with an integer elevation in the range 0 .. 100. In the winter, since there is abundant snow on these hills, FJ routinely operates a ski training camp.

Unfortunately, FJ has just found out about a new tax that will be assessed next year on farms used as ski training camps. Upon careful reading of the law, however, he discovers that the official definition of a ski camp requires the difference between the highest and lowest hill on his property to be strictly larger than 17. Therefore, if he shortens his tallest hills and adds mass to increase the height of his shorter hills, FJ can avoid paying the tax as long as the new difference between the highest and lowest hill is at most 17.

If it costs x^2 units of money to change the height of a hill by x units, what is the minimum amount of money FJ will need to pay? FJ is only willing to change the height of each hill by an integer amount.

입력

출력

* Line 1: The minimum amount FJ needs to pay to modify the elevations of his hills so the difference between largest and smallest is at most 17 units.

입출력 예

입력

5
20
4
1
24
21

출력

18

INPUT DETAILS:

FJ's farm has 5 hills, with elevations 1, 4, 20, 21, and 24.

OUTPUT DETAILS:

FJ keeps the hills of heights 4, 20, and 21 as they are.  He adds mass to the
hill of height 1, bringing it to height 4 (cost = 3^2 = 9).  He shortens
the hill of height 24 to height 21, also at a cost of 3^2 = 9.

출처:2014/jan/bronze
[질/답] [제출 현황] [푼 후(16)]
[ 채 점 ] [홈으로]  [뒤 로]