Обозначим стартовый вагон буковкой A, выключим в нем свет и пойдем по ходу поезда, идем пока свет в вагонах горит, дошли до вагона с выключенным светом, обозначим его буковкой B, включаем в нем свет и идем обратно в A, если в A горит свет, значит мы обошли все вагоны, если свет в A выключен, то включаем его и возвращаемся в вагон B, выключаем в вагоне B свет, назначаем вагон B вагоном A и далее повторяем описанную процедуру, до тех пор пока не обнаружим в A свет.

У меня получается по три пробежки между точками A->B->A->B, далее точка B превращается в A и все повторяется, плюс одна финальная пробежка, когда во всех вагонах будет одинаковое состояние, по моей стратегии получается максимум 4*N проходов, вроде как удовлетворяет O(N).

Да, оба выражения отражают одно и то же.


Ничего метить нельзя, можно только ходить из вагона в вагон по ходу или против хода поезда и включать
или выключать свет в вагоне, кроме того можно считать вагоны. Буквами я их называю чтобы проще было
понять алгоритм. Например вагон с которого начали пусть будет 0-й, следующий вагон принятый новой точкой
отсчета например будет 5-й по счету от нулевого, следующий будет например 7-й по счету от 0-го и 2-й по
счету от 5-го, т.е. никаких букв мы в вагонах не рисуем.


Да, посчитал последнюю пробежку по всему кругу только туда, обратно упустил, получается 5N в худшем случае, в лучшем 2N.

Dima T,

Нет, каждый вагон посещается не более пяти раз, в самом плохом случае получаем 5*N.