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| единиц энергии. Конечно же, энергию следует расходовать максимально экономно.

Известны высоты платформ в порядке от левого края до правого. Найдите минимальное количество энергии, достаточное, чтобы добраться с 1-й платформы до n-й (последней) и список (последовательность) платформ, по которым нужно пройти.

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
4
1 2 3 4

Qeyd

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

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