Роботи#197

Роботи (Розбір)

Моделювати секунд неможливо (t \le 10^{18}), тому треба зрозуміти, куди робот потрапляє «врешті-решт».

Ключове спостереження: напрямок визначає клітинка, а не робот. Тому робот на клітинці з R іде праворуч, доки не стане на клітинку з L; там він розвернеться і піде ліворуч — але клітинка ліворуч від першої L обов'язково має R, тож наступної секунди він повернеться назад. Отже, кожна пара сусідніх клітинок вигляду RL — це пастка, у якій робот вічно коливається з періодом .

Звідси розв'язок для робота, що стартує в клітинці .

Випадок s_i = \texttt{R}. Нехай — позиція найближчої L праворуч (включно з ; насправді p > i). Якщо такої немає, робот дійде до правого краю і зникне — перевіряємо, чи встигне він вийти за секунд. Інакше він рухається праворуч p - i секунд і опиняється в . Далі коливається між і p-1. Тому, позначивши \mathrm{rem} = t - (p - i):

  • якщо \mathrm{rem} < 0, робот ще в дорозі, у клітинці i + t;

  • інакше він у клітинці при парному і в клітинці p - 1 при непарному.

Випадок s_i = \texttt{L} симетричний: нехай — найближча R ліворуч. Робот іде ліворуч i - q секунд до клітинки , а потім коливається між і q+1: при парному залишку він у , при непарному — у q+1. Якщо R ліворуч немає, робот виходить за лівий край.

Масиви «найближча L праворуч» і «найближча R ліворуч» будуються двома простими проходами.

Складність — . Значення сягає 10^{18}, тому всі обчислення часу ведіть у 64-бітному типі; для відповіді достатньо перевіряти лише парність залишку.