Начало
ЗадачиПодразделы
Другие разделы
| STL |
| Антагонистические игры |
| Геометрия |
| Графы |
| Динамическое программирование |
| Дихотомия |
| Длинная арифметика |
| Комбинаторика |
| Основы |
| Перебор |
| Поиск в глубину |
| Поиск в ширину |
| Последовательности |
| Сортировка |
| Теория чисел |
Дата и время
17/11/2024 09:20:11
Неклассифицированные
A Foldy but a Goody Checker Give Me an E Target Practice Агентурная сеть Ленивый папа Последовательность Правописание Прибор Сетки Стрелок Строки Фибоначчи Шутка
Сетки
Вывод формулыБинарный поиск
Олимпиадные задачи на русском языке
| 17/11/2007 | Тренировка (задачи Западно-Сибирского четвертьфинала 2007) (D) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Сетки нашли широкое применение в решении большого количества научных задач, так как они представляют наиболее простой и естественный способ разбиения пространства на области, которые можно различать. При этом часто эти сетки являются регулярными, т.е. в таких сетках все ячейки имеют одинаковую форму и расположены периодически.
Для того чтобы отличать одну ячейку сетки от другой, ячейки сетки нумеруют тем или иным способом.
Предлагаем следующий способ нумерации потенциально бесконечной прямоугольной сетки:
- произвольная ячейка сетки нумеруется 1;
- далее нумеруются последовательно все ранее не пронумерованные ячейки, смежные с группой уже пронумерованных ячеек (ячейка считается смежной с группой ячеек, если она имеет хотя бы одну общую сторону с некоторой ячейкой группы), по часовой стрелке, начиная с самой нижней ячейки (ближайшей к группе уже пронумерованных ячеек);
- шаг 2 повторяется для новой группы пронумерованных ячеек (при первом выполнении шага 2 группа пронумерованных ячеек состоит из одной ячейки с номером 1, при втором – из ячеек 1, 2, 3, 4, 5, и т.д.).
Ниже приведён центральный фрагмент прямоугольной сетки, пронумерованной по такому принципу.
| 32 | 19 | 10 | 21 | 36 |
| 18 | 9 | 4 | 11 | 22 |
| 8 | 3 | 1 | 5 | 12 |
| 16 | 7 | 2 | 13 | 24 |
| 28 | 15 | 6 | 25 | 40 |
Перед вами стоит задача: по заданным номерам `a`, `b` двух ячеек прямоугольной сетки определить минимальное число шагов, которые необходимо сделать, чтобы попасть из ячейки с номером `a` в ячейку с номером `b`. Двигаться по сетке можно только через смежные стороны ячеек.
Входные данные
В первой строке два целых числа `a` и `b` (`1\ ≤\ a,\ b\ ≤\ 10^17`) – номера ячеек прямоугольной сетки.
Выходные данные
В первой строке целое число – минимальное число шагов.
Пример ввода
21 14
Пример вывода
6
