воскресенье, 16 марта 2014 г.

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


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

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