Спершу опишемо траєкторію точно. Степан дивиться вздовж і після кожного відрізка повертає праворуч, тому напрямки циклічно чергуються:
а довжини відрізків ідуть парами: 1, 1, 2, 2, 3, 3, 4, 4, \ldots
Простежимо, як далеко спіраль відходить від старту. Після першої четвірки відрізків вона сягає відстані у кожному з чотирьох напрямків, після другої — відстані , після -ї — відстані . Тобто «радіус» спіралі зростає рівно на одиницю за кожні чотири відрізки, причому напрямки вичерпуються в сталому порядку: спочатку правий, потім нижній, лівий і насамкінець верхній.
Звідси головне спостереження: рух припиняється на першому напрямку, у якому не вистачило місця, а все, що відбувалося до того, повністю визначається чотирма відстанями до стін:
Оскільки в межах однієї четвірки верхній напрямок обробляється останнім, а правий — першим, то ці напрямки «переживають» різну кількість кроків. Через це зручно працювати з трохи зсунутими величинами
і саме серед них шукати мінімум \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.
Тепер лишається просумувати довжини всіх пройдених відрізків. Кожен напрямок дає арифметичну прогресію, і суми згортаються у квадрати та трикутні числа, даючи остаточну формулу:
Розв'язок працює за , що принципово: моделювати спіраль по клітинках при N, M \le 10^9 неможливо. Усі величини сягають 10^{18}, тому рахуйте у 64-бітному типі.