eolymp
bolt
Try our new interface for solving problems
Məsələlər

Платформы - дополнительный критерий оптимизации

Платформы - дополнительный критерий оптимизации

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Во многих старых играх с двумерной графикой можно столкнуться с подобной ситуацией. Какой нибуть герой прыгает по платформам (или островкам), которые висят в воздухе. Он должен перебраться с одного края экрана до другого. При этом, при прыжке с одной платформы на соседнюю, у героя уходит |y_2-y_1| энергии, где y_2 и y_1 - высоты, на которых расположены эти платформы. Кроме того у героя есть суперприём, который позволяет перескочить через платформу, но на это затрачивается 3*|y_2-y_1| единиц энергии. Конечно же, энергию следует расходовать максимально экономно.

Предположим, что вам известны координаты всех платформ в порядке от левого края до правого. Во первых, найдите минимальное количество энергии, которое потребуется герою, чтобы добраться с первой платформы до последней с одинаковыми минимальными затратами энергии, если таких существует несколько, то среди них выберите способ с минимальным количеством прыжков.

Giriş verilənləri

В первой строке записано количество платформ N (2N100000), вторая - N целых чисел, значения которых не превышают по модулю 4000 - высоты платформ.

Çıxış verilənləri

Выведите в одной строке два числа через пробел: сначала минимальное количество энергии, потом минимальное (среди тех, при которых возможно минимальное количество энергии) количество прыжков.

Nümunə

Giriş verilənləri #1
4
1 2 3 30
Çıxış verilənləri #1
29 3

Qeyd

Второй ответ первого примера всё-таки 3 (а не 2), т.к. просят искать не вообще минимальное количество прыжков, а минимальное среди тех способов, при которых достигается минимальное количество затраченной энергии. В данном конкретном случае минимальное количество затраченной энергии (29) достигается только одним способом, и в нём 3 прыжка.

Müəllif Илья Порублёв
Mənbə Летняя школа Севастополь 2013, Волна 1, День 2