Дивний сон#156

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

Спершу опишемо траєкторію точно. Степан дивиться вздовж і після кожного відрізка повертає праворуч, тому напрямки циклічно чергуються:

+X,\ -Y,\ -X,\ +Y,\ +X,\ \ldots

а довжини відрізків ідуть парами: 1, 1, 2, 2, 3, 3, 4, 4, \ldots

Простежимо, як далеко спіраль відходить від старту. Після першої четвірки відрізків вона сягає відстані у кожному з чотирьох напрямків, після другої — відстані , після -ї — відстані . Тобто «радіус» спіралі зростає рівно на одиницю за кожні чотири відрізки, причому напрямки вичерпуються в сталому порядку: спочатку правий, потім нижній, лівий і насамкінець верхній.

Звідси головне спостереження: рух припиняється на першому напрямку, у якому не вистачило місця, а все, що відбувалося до того, повністю визначається чотирма відстанями до стін:

R = N - x, \qquad L = x - 1, \qquad D = y - 1, \qquad U = M - y.

Оскільки в межах однієї четвірки верхній напрямок обробляється останнім, а правий — першим, то ці напрямки «переживають» різну кількість кроків. Через це зручно працювати з трохи зсунутими величинами

u = U + 1, \qquad r = R, \qquad d = D, \qquad l = L,

і саме серед них шукати мінімум \mu = \min(u, r, d, l) — він і показує, на якому витку спіраль упреться в стіну.

Далі значення вирівнюються за тим, який напрямок виявився обмежувальним: напрямки, які в цьому витку встигли пройти повністю, отримують \mu + 1, а ті, до яких черга вже не дійшла, — . Конкретно:

  • якщо мінімум досягається на , то r = d = l = \mu;

  • якщо на , то u = \mu + 1, а d = l = \mu;

  • якщо на , то u = r = \mu + 1, а l = \mu;

  • якщо на , то u = r = d = \mu + 1.

Тепер лишається просумувати довжини всіх пройдених відрізків. Кожен напрямок дає арифметичну прогресію, і суми згортаються у квадрати та трикутні числа, даючи остаточну формулу:

u^2 + r^2 + d(d+1) + l(l+1).

Розв'язок працює за , що принципово: моделювати спіраль по клітинках при N, M \le 10^9 неможливо. Усі величини сягають 10^{18}, тому рахуйте у 64-бітному типі.