Sakurako is Late#348

Sakurako is Late (Editorial)

Автори:

Тимкович Олександр, Фейса Богдан

Підготував:

Фейса Богдан

Розбір:

Фейса Богдан

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

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

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

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

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

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

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

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

Сумарний час роботи рішення .