Задача к ЕГЭ по информатике на тему «Программирование – оптимизация по времени и по памяти» №2

Андрей едет из пункта $A$ в пункт $B$ на автомобиле. Расстояние между этими пунктами равно $N$ километров. Известно, что с полным баком автомобиль способен проехать $k$ километров. Дана карта, на которой отмечены координаты бензоколонок, относительно пункта $A$ . Определите минимальное число заправок, которые придется сделать Андрею чтобы успешно достичь пункта $B$ . Известно, что при выезде из пункта $A$ бак был полон.

Входные данные

В первой строке вводятся числа $N$ и $k$ (натуральные, не превосходят $1000$ ). В следующей строке вводится количество бензоколонок $S$ , потом следует $S$ натуральных чисел, не превосходящих $N$ — расстояния от пункта $A$ до каждой заправки. Заправки упорядочены по удаленности от пункта $A$ .

Выходные данные

Если при данных условиях пункта $B$ достичь невозможно, то вывести число $− 1$ . Если решение существует, то вывести минимальное количество остановок на дозаправку, которое нужно, чтобы достичь пункта $B$ .

f = open("input.txt")

n, k = [int(i) for i in f.readline().split()]
s = int(f.readline())

# список координат каждой заправки
d = [int(i) for i in f.readlines()]

# добавляем в список координат координату точки B
# это нужно для того, чтобы мы могли проверить,
# можно ли доехать с последней заправки до точки B без дозаправки или нет
d.append(n)

current_fuel = k  # текущая наполненность бака
current_dist = 0  # пройденное расстояние
ans = 0  # ответ
possible = True  # флаг, указывающий то, смогли ли мы доехать до пункта B
coords = []
for i in range(s+1):
    # проверка того, что мы не сможем проехать до следующей
    # заправки и нам нужно заправиться
    if d[i] - current_dist > current_fuel:
        # проверка того, что мы можем заправиться (в пункте A заправок нет)
        # и проверка того, что мы после заправки сможем доехать до следующей заправки
        if current_dist != 0 and k >= d[i] - current_dist:
            current_fuel = k - (d[i] - current_dist)
            ans += 1
            coords.append(current_dist)
        else:
            possible = False
            break
    # если мы смогли доехать до следующей заправки без дозаправки,
    # то необходимо уменьшить кол-во топлива в баке
    else:
        current_fuel -= (d[i] - current_dist)
    current_dist = d[i]

if possible:
    print(ans)












































































































































































































else:
    print(-1)

Ответ: 31