Заправки на трассе


Отправить решение Решать в редакторе

Сложность: 40%
Очки: 100 (частичный балл)
Ограничение по времени: 1.0s
Ограничение по памяти: 256M

Автор:
Тип задачи
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Автомобиль едет по трассе от начала (0) до города на отметке L. Бак вмещает топлива на C километров, в начале он полон. На трассе есть n заправок, на каждой можно заправиться до полного бака. Какое наименьшее число заправок нужно посетить, чтобы доехать? Если доехать нельзя, выведите -1.

Формат ввода

В первой строке даны n, L и C. Во второй — отметки заправок по возрастанию (если n = 0, вторая строка пустая).

Формат вывода

Выведите минимальное число остановок или -1.

Ограничения

0 ≤ n ≤ 10⁵, 1 ≤ C, L ≤ 10⁹+5, отметки различны и лежат строго между 0 и L.

Примеры

Пример 1

Ввод:

3 10 4
3 6 8

Вывод:

2
Пример 2

Ввод:

1 10 4
7

Вывод:

-1

Комментарии

Еще нет ни одного комментария.