Задача №113075. Путешествие
Андрей едет из пункта A в пункт B на автомобиле. Расстояние между этими пунктами равно \(N\) километров. Известно, что с полным баком автомобиль способен проехать k километров. Дана карта, на которой отмечены координаты бензоколонок, относительно пункта A. Определите минимальное число заправок, которые придется сделать Андрею чтобы успешно достичь пункта B. Известно, что при выезде из пункта A бак был полон.
В первой строке вводятся числа \(N\) и \(k\) (натуральные, не превосходят 1000). В следующей строке вводится количество бензоколонок \(S\), потом следует \(S\) натуральных чисел, не превосходящих \(N\) – расстояния от пункта A до каждой заправки. Заправки упорядочены по удаленности от пункта A.
Если при данных условиях пункта B достичь невозможно, то вывести число -1. Если решение существует, то вывести минимальное количество остановок на дозаправку, которое нужно чтобы достичь пункта B.
100 20 1 50
-1
100 50 1 50
1
100 100 3 10 20 80
0