Круговая трасса

Есть круговая трасса, на которой в некоторых местах стоят бензоколонки.
Расстояния между ними и количество бензина на каждой бензоколонке известны.
Имеется также машина с постоянным и известным расходом топлива.
Предложите алгоритм, работающий за $O(n)$ по времени, который позволяет найти ту, бензоколонку,
начиная с которой можно проехать всю трассу, или сказать, что такой нет.

Это задача №5, ШАД-2013, Новосибирск.

Решение.

Пусть $V_i$ и $l_i$ --- количество бензина i-й  бензоколонке и расстояние от i-й до i+1-й бензоколонки, $\alpha$ --- рассход на ед. длины.
Можно считать, что машина двигается против часовой стрелки.

Алгоритм.\\
1) Вычислим  $\delta_i = V_i - \alpha l_i$ --- остаток бензина в баке машины после проезда от i-й до i+1-й бензоколонки.
Если все $\delta_i<0 ---="" br="">2) Выбираем такой номер i, что$\delta_i\geqslant$. Начинаем суммировать$$S_k = \delta_i + \delta_{i+1} + \cdots + \delta_{i+k}$$пока$S_k\geqslant0$. Если дошли$k=n-1$, то i --- искомая бензоколонка.\\ 3) Если$S_{k^*}\geqslant0$, а$S_{k^*+1}<0 br="" i-1="" nbsp=""> $$S_{k+1} = \delta_{i-1} + \delta_i + \delta_{i+1} + \cdots + \delta_{i+k^*}.$$
Таким образом за n шагов (или меньше) мы либо получим номер $i^*$, либо перебрём все
бензоколонки и прийдём к выводу, что искомой бензоколонки нет.

Данный алгоритм совершает не более $2\cdot(2n+1+2n)$ шагов (учитывая арифметические операции и сравнения).