Розбір

Можливо довести, що нам $\text{завжди}$ вигідно рухатись вперед, коли ми це можемо зробити.

Припустимо, що це не так, тоді Сакурако не буде рухатись вперед і світлофор стане червоним, через що їй доведеться чекати ще одну хвилину. Коли ж світлофор знову стане зеленим, то ми повернемось в стан перед тим, як Сакурако вирішила не переходити на зелений колір.

*під словом "стан" мається на увазі кольори всіх світлофорів та позиція Сакурако.

Якщо ця умова правдива, то оптимальний час, за який Сакурако пройде всі пішохідні переходи, не буде більшим за $2n$.

Через це обмеження на максимальну кількість ходів ми можемо просимулювати рух Сакурако:

• якщо наступний світлофор червоний в момент часу, коли ми до нього підійшли, то ми очікуємо 1 хвилину і потім пересуваємось вперед, витрачаючи ще одну хвилину.

• якщо зелений, то пересуваємось вперед, витрачаючи на це одну хвилину

Для визначення, чи світлофор червоний, чи зелений в момент часу $x$, ми можемо скористатись тим, що кожен світлофор буде незалежно циклічно змінювати свій колір.

Сумарний час роботи рішення $O(n)$.