printНеклассифицированные

printСетки

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Сетки нашли широкое применение в решении большого количества научных задач, так как они представляют наиболее простой и естественный способ разбиения пространства на области, которые можно различать. При этом часто эти сетки являются регулярными, т.е. в таких сетках все ячейки имеют одинаковую форму и расположены периодически.
Для того чтобы отличать одну ячейку сетки от другой, ячейки сетки нумеруют тем или иным способом.
Предлагаем следующий способ нумерации потенциально бесконечной прямоугольной сетки:
  • произвольная ячейка сетки нумеруется 1;
  • далее нумеруются последовательно все ранее не пронумерованные ячейки, смежные с группой уже пронумерованных ячеек (ячейка считается смежной с группой ячеек, если она имеет хотя бы одну общую сторону с некоторой ячейкой группы), по часовой стрелке, начиная с самой нижней ячейки (ближайшей к группе уже пронумерованных ячеек);
  • шаг 2 повторяется для новой группы пронумерованных ячеек (при первом выполнении шага 2 группа пронумерованных ячеек состоит из одной ячейки с номером 1, при втором – из ячеек 1, 2, 3, 4, 5, и т.д.).
Ниже приведён центральный фрагмент прямоугольной сетки, пронумерованной по такому принципу.
3219102136
18941122
831512
16721324
281562540
Перед вами стоит задача: по заданным номерам `a`, `b` двух ячеек прямоугольной сетки определить минимальное число шагов, которые необходимо сделать, чтобы попасть из ячейки с номером `a` в ячейку с номером `b`. Двигаться по сетке можно только через смежные стороны ячеек.
Входные данные
В первой строке два целых числа `a` и `b` (`1\ ≤\ a,\ b\ ≤\ 10^17`) – номера ячеек прямоугольной сетки.
Выходные данные
В первой строке целое число – минимальное число шагов.

Пример ввода

21 14

Пример вывода

6
Источник: NEERC, Западно-Сибирский четвертьфинал, 2007
loading