Тренажёр

Нашли ошибку?

Минимум заправок

ЛёгкаяНайти ошибку2 ошибкиГлава 8

РешеноНашли ошибку?

#жадные алгоритмы#граничные случаиid: ga-refuel-stops

Трасса длиной distance км, на ней заправки в точках stations (км от старта, по возрастанию). Полного бака хватает на tank км, стартуем с полным баком. Жадная стратегия: ехать, пока хватает топлива, и заправляться на самой дальней достижимой заправке. Функция refuel_stops(stations, distance, tank) возвращает минимальное число заправок или -1, если не доехать. В ней две ошибки — найдите и исправьте их.

Пример

refuel_stops([100, 200, 350, 450], 600, 250)   # 2: заправки на 200 и 450
refuel_stops([100, 200], 300, 300)             # 0: бака хватает ровно до финиша
refuel_stops([100, 400], 600, 250)             # -1

Решение

def refuel_stops(stations: list[int], distance: int, tank: int) -> int:
    """Минимальное число заправок до финиша или -1."""
    reach = tank  # докуда можно доехать без новой заправки
    stops = 0
    i = 0
    while reach <= distance:
        farthest = None
        while i < len(stations) and stations[i] < reach:
            farthest = stations[i]
            i += 1
        if farthest is None:
            return -1  # ни одной новой заправки в пределах досягаемости
        stops += 1
        reach = farthest + tank
    return stops

Вывод

tests.py — только для чтения
def test_example():
    """Пример: 2 заправки"""
    got = refuel_stops([100, 200, 350, 450], 600, 250)
    assert got == 2, f"ожидалось 2, получено {got!r}"


def test_tank_exactly_enough():
    """Бака хватает ровно до финиша → 0"""
    got = refuel_stops([100, 200], 300, 300)
    assert got == 0, f"ожидалось 0, получено {got!r}"


def test_impossible():
    """Разрыв между заправками больше бака → -1"""
    got = refuel_stops([100, 400], 600, 250)
    assert got == -1, f"ожидалось -1, получено {got!r}"


def test_station_at_reach_edge():
    """Заправка ровно на пределе запаса хода — до неё можно доехать"""
    got = refuel_stops([250], 500, 250)
    assert got == 1, f"ожидалось 1, получено {got!r}"


def test_no_stations():
    """Заправок нет"""
    assert refuel_stops([], 100, 150) == 0, "бака хватает — 0"
    assert refuel_stops([], 200, 150) == -1, "бака не хватает — -1"


def test_greedy_farthest():
    """Выбирается самая дальняя из достижимых заправок"""
    got = refuel_stops([10, 20, 30, 40, 50, 60, 70, 80, 90], 100, 50)
    assert got == 1, f"ожидалось 1 (заправка на 50), получено {got!r}"


def test_many_stops():
    """Заправки каждые 10 км, бак на 10 км"""
    got = refuel_stops(list(range(10, 100, 10)), 100, 10)
    assert got == 9, f"ожидалось 9, получено {got!r}"

Можно решать и в своём редакторе: «Скопировать с тестами» и запустите python3 refuel_stops.py — тесты те же, результат покажет ✓ / ✗ и итог.

Подсказка 1
Обе ошибки — на границах. Проверьте случай, когда запаса хода хватает ровно до финиша.
Подсказка 2
Можно ли заправиться на заправке, до которой запаса хода хватает ровно впритык?

solution.py

def refuel_stops(stations: list[int], distance: int, tank: int) -> int:
    """Минимальное число заправок до финиша или -1."""
    reach = tank  # докуда можно доехать без новой заправки
    stops = 0
    i = 0
    while reach < distance:
        farthest = None
        while i < len(stations) and stations[i] <= reach:
            farthest = stations[i]
            i += 1
        if farthest is None:
            return -1  # ни одной новой заправки в пределах досягаемости
        stops += 1
        reach = farthest + tank
    return stops