Тема 27. Программирование – оптимизация по времени и по памяти
27.07 Прочие прототипы
Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела программирование – оптимизация по времени и по памяти
Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#54787

Андрей едет из пункта 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

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное обучение
в Школково

Для детей ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Брянской областей, а также школьникам, находящимся в пунктах временного размещения Крыма обучение на платформе бесплатное.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ или олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!