Высокие горы

Автор задачи: Рогачева Е.В.

Снарядил старший сын обоз с подарками богатыми, и отправился за высокие горы за своей невестой. А ехать нелегко - то в гору подниматься, то с горы спускаться. Надо остановки делать, чтобы отдохнуть. Но и добраться поскорее хочется.

Обозначим через E «запас сил» обоза. При подъеме в гору на единичную высоту обоз теряет 2*M «сил», а при спуске с такой же высоты - M «сил». Отдыхать обоз может только в «точках перевала» - либо после спуска перед подъемом, либо после подъема перед спуском. Обоз не может двигаться дальше, если до следующего перевала он должен потратить сил больше, чем имеется у него в запасе. За единицу времени он может восстановить V сил. Однако обоз не может набрать сил больше, чем Emax, сколько бы он ни отдыхал.

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

Формат входного файла input.txt.

Первая строка - целые числа N, E0, Emax, M, V через пробел.

N - количество точек «перевала» при движении обоза, 2 <= N <= 100. E0 - начальный запас сил обоза (0 <= E0 <= Emax), Emax - максимально возможный «запас сил» обоза (1 <= Emax <= 1000) M - количество сил, которое теряется при спуске с единичной высоты (0 <= M <= 1000), V - количество сил, которое восстанавливается за единицу времени при отдыхе (0 <= V <= 1000).

Вторая строка - целые числа h1, h2, …, hN через пробел - высоты, на которых расположены точки перевала (-1000 <= h1, h2, …, hN <= 1000).

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

Формат выходного файла output.txt.

Первая строка - целое число T - минимальное время отдыха, которое потребуется обозу в пути или слово NO, если обоз не может проехать до места назначения с указанными ограничениями.

Пример входного файла Пример выходного файла

3 13 15 3 2 1

Решение. Только 6 участников городского тура олимпиады 2006 Самары прошли все тесты и получили максимальное число баллов. Многие из тех, кто решил другие даже более сложные задачи, не сумел пройти все тесты для этой задачи.

Анализ показал, что в большинстве решений не учтено одно из условий задачи, а именно - V - количество сил, которое восстанавливается за единицу времени при отдыхе, может быть равно нулю(0 <= V <= 1000). Это означает, что если энергии для движения недостаточно, то при V=0 отдыхать бесполезно и нужно выдать в выходной файл 'NO'.

Второй особенностью является условие ограничение на Emax, даже при V>0 накопить энергию большую Emax нельзя. Учтите и это в своем решении. На сайте есть разбор задач и авторские решения. Но вы, зная особенности тестов, должны теперь самостоятельно решить и сдать решение.