Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 






Высокие горы

Задачу добавил: alef

Успешно сдано решений: 60

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

Обозначим через 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

0 2 1

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

1

Сдать задачу

Задать вопрос жюри по этой задаче