Олимпиадный тренинг

Задача . Ski Course Design


Задача

Темы: Жадный алгоритм

У Фермера Джона на ферме N склонов (1 <= N <= 1,000), каждый с целое высотой в диапазоне от 0 до 100. Зимой, когда выпадает снег, ФД организует на них лыжный тренировочный лагерь.
Однако сейчас ФД вычитал, что по новому закону придётся платить налог, если разница между его самым высоким и самым низким склоном строго больше чем 17. Поэтому если он срежет самый высокий склон или увеличит высоту самого низкого склона, так чтобы соответствовать закону (разница не больше 17), он избежит оплаты соответствующего налога за нарушение закона.
Если x^2 – стоимость изменения высоты склона на x единиц, какое минимальное количество денег придётся заплатить ФД, Чтобы привести свои склоны в соответствие с новым законом. Высоты меняются только на целую величину x.
PROBLEM NAME: skidesign
Формат входных данных
* Строка 1: Целое число N.
* Строки 2..1+N: Каждая строка содержит высоту одного склона.
Формат выходных данных
* Строка 1: Минимальное количество денег, которое нужно заплатить, чтобы разница между самым высоким и самым низким склонами стала не более чем 17 единиц.
Примечание
ФД оставит высоты 4, 20, и 21 как они были. Он добавит высоту склону с высотой 1 до высоты 4 (цена = 3^2=9) Он уменьшит высоту 24 до высоты 21 (цена = 3^2=9)
Примеры
№Входные данныеВыходные данные
1 
5
1
4
20
21
24
 
18
Статистика успешных решений по компиляторам
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет