eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Шестиугольные пути

Шестиугольные пути

Лимит времени 2 секунды
Лимит использования памяти 64 MiB

Поиск кратчайшего маршрута является типичной задачей для водителя грузовика. Если грузовик движется по кратчайшему пути, это экономит деньги. Кроме того, важно знать альтернативные маршруты той же длины, в случае если основной маршрут недоступен, например, из-за некоторых дорожных работ.

Для описания области необходимо промоделировать ее карту. В ACM недавно обнаружили, что треугольные и прямоугольные модели областей являются недостаточными, поэтому решили использовать шестиугольники для описания карт. Клетки правильной шестиугольной сетки (например, сот) можно нумеровать, начиная с 1 (в любой клетке) и двигаться по спирали к другим клеткам. Таким образом, каждая ячейка однозначно идентифицируется своим номером. И наоборот, каждое положительное целое число определяет одну ячейку.

Две клетки называются соседними, если они имеют одну общую сторону. В бесконечной структуре каждая ячейка имеет ровно шесть соседей. Например, ячейка номер 2 соседствует с 1, 3, 7, 8, 9 и 10. Шестиугольный путь - это непустая последовательность ячеек, в которой каждая из них (кроме последней) является соседней с последующей. Шестиугольный путь между двумя ячейками X и Y - это путь, в котором X - первая ячейка последовательности, а Y - последняя. Длиной пути называется количество ячеек в нем минус один. Длина пути представляет собой количество шагов, необходимых для прохождения всего маршрута.

Вам следует найти длину кратчайшего маршрута между двумя клетками, а также общее количество взаимно различных маршрутов такой же длины. Различные маршруты должны различаться по крайней мере в одном члене последовательности, т.е. они не должны формировать полностью непересекающихся последовательности.

Входные данные

Входные данные состоят из нескольких тестов, каждый из которых расположен на отдельной строке. Строка содержит два целых числа X и Y (1X, Y1000000, XY), разделенных пробелом. Числа задают две различные ячейки. За последним тестом следует строка из двух нулей, которая обозначает конец входных данных.

Выходные данные

Для каждого теста вывести предложение "There are N routes of the shortest length L.". Замените L наименьшей длиной пути между ячейками X и Y. Замените N количеством различных путей той же самой длины. Если существует только один путь, то используйте слова "is" и "route" вместо "are" и "routes".

Пример

Входные данные #1
1 2
0 0
Выходные данные #1
There is 1 route of the shortest length 1.
Источник Czech Technical University Open 2003