Дивний сон#474

Дивний сон (Editorial)

Автор, розробник, автор розбору: Ілля Пермяков

Нехай поточна координата — , а поточний крок — . Позначимо = \lfloor \frac{p}{y_i} \rfloor. Тоді найближчі координати до на числовій прямій, кратні y_i — q \cdot y_i зліва, та (q + 1) \cdot y_i справа. Щоб зрозуміти, у яку з цих двох координат йти, достатньо подивитись на відстань від цих позицій до :

  • Козак Вус опиниться у координаті q \cdot y_i, якщо p - q \cdot y_i \leq p - (q + 1) \cdot y_i.

  • В іншому випадку, він опиниться у координаті (q + 1) \cdot y_i.

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