И снова об экзамене ШАДа
Индийские математики любили делать хитрые доказательства теорем: например, равносоставленный квадрат и подпись: «Теорема Пифагора, смотрите!» Вот и я нашёл одно такое доказательство. Задача знакомая.
На круговой дороге стоят канистры с бензином. Есть машина с известным расходом и пустым баком неограниченной ёмкости. За O(n) выяснить, можно ли, подзаправляясь из канистр, проехать всю дорогу. Если можно, указать какую-нибудь канистру, с которой можно начать.
Поставим машину у первой канистры, зальём M литров (с избытком) начнём вояж по трассе. Как только круг замкнётся, проверим уровень. Если меньше M, значит, явно невозможно: содержимого канистр не хватает, чтобы проехать весь круг. Если, например, M+p: восстанавливаем канистры, проезжаем ещё круг, глушим мотор и начинаем думать.
Если бензин ни разу не опускался ниже M, значит, мы угадали и можно начать с самой первой канистры. Рассмотрим второй вариант: меньше всего топлива (а именно M−q) в было перед i-й канистрой. Очевидно, это «меньше всего» было на первом круге: второй - точная копия первого, но топлива на p литров больше. Слив из бака M−q топлива и ограничившись маршрутом от i-й канистры на первом круге до неё же на втором, получаем нужный нам маршрут.
Получаем такой алгоритм. Вычисляем частичные суммы: сколько топлива машина приобретёт или потеряет, чтобы проехать от 1-й канистры до 2-й, 3-й, 4-й и т.д. Последняя сумма - сколько топлива машина приобретёт, проехав целый круг. Если эта сумма отрицательна, проехать нельзя. Если все суммы положительны, начинать от первой канистры. Иначе - начать от той, где замечено наименьшее отрицательне число.
Последние два условия можно объединить в одно, добавив фиктивную нулевую сумму «от первой канистры до первой».