Ловушка поезда

Автор задачи и разработчик: Павел Скобелин

Для начала научимся проверять, правда ли, что $$$n \leqslant x$$$ для произвольного $$$x$$$. Для этого отметим состояние в текущем вагоне, сделаем $$$x$$$ шагов вперед, и после каждого шага будем менять состояние на противоположное тому, которое мы оставили в первом вагоне. Затем сделаем $$$x$$$ шагов назад — если состояние в первом вагоне поменялось, то $$$x \geqslant n$$$. Аналогичным образом можно проверять, что $$$n$$$ лежит от $$$x$$$ до $$$2x$$$: просто в первой половине вагонов сделаем состояние равным первому, а во второй половине — противоположным.

Теперь воспользуемся классической идеей подъема по степеням двойки. Рассмотрим по очереди $$$x \in [1, 2, 4, 8, 16, \ldots]$$$. Как только найдем $$$2x \geqslant n$$$, будем понимать, что $$$n \in (x, 2x]$$$.

Теперь, зная максимальную границу ответа (причем $$$x < n \leqslant 2n$$$), пройдем вперед $$$2x$$$ шагов и выключим все обогреватели. Так как вагонов в поезде не более $$$2x$$$, значит, теперь все обогреватели выключены. После этого включим обогреватель в текущем вагоне, пройдем $$$x$$$ шагов вперед (все еще не вернувшись в исходный, так как $$$x < n$$$), и будем делать по одному шагу, каждый раз проверяя состояние обогревателя в текущем вагоне. Как только мы встретим первый включенный — значит, мы прошли по циклу.

При аккуратной реализации такой алгоритм займет не более $$$15 \cdot n - 10 < 16 \cdot n$$$ действий.