Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
Platforms

Задача Platforms
 В старих іграх можна зустрітись з такою ситуацією. Герой стрибає по платформах, що висять у повітрі. Він повинен перебратися від одного краю екрана до іншого. В одній з версій даної гри, при стрибку з платформи на сусідню, у героя витрачається |y2y1| енергії, де y1 і y2 — висоти, на яких розміщено ці платформи. Крім того, є суперприйом, що дозволяє перескочити через платформу, але на це витрачається 3×|y3y1| енергії. Інша версія відрізняється лише тим, що в функціях витрат енергії модулі замінено на квадрати, тобто. (y2y1)2 при стрибку на сусідню та 3×(y3y1)2 при стрибку через одну. Відомі висоти платформ у порядку від лівого краю до правого. Знайдіть (для кожної з версій гри) мінімальну кількість енергії, достатню, щоб дістатись з 1-ї платформи до n-ї (останньої). 
Технічні умови: Програма повинна прочитати з клавіатури спочатку кількість платформ N (2≤N≤50000), потім N чисел в діапазоні від –2000 до +2000 кожне — висоти цих платформ. Програма повинна вивести на екран у єдиному рядку два розділені пропуском цілі числа — мінімальні необхідні затрати енергії для першої версії гри та для другої версії гри. 
Приклад:
Введення:               3 0 20 11
Виведення:            29 363
 

Для першої версії вигідніше стрибати по всім підряд платформам 0→ 20→11, сумарні витрати 20+9=29. Для другої — перестрибнути одразу 0→11 вигідніше (3*112=363), ніж стрибати по всім платформам підряд (202+92=481).

© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"