Робот Гильберта
(Время: 1 сек. Память: 16 Мб Сложность: 54%)
Кривая Гильберта порядка N – самоподобная непрерывная ломаная, заполняющая квадрат 2N x 2N и проходящая через все клетки данного квадрата. Каждая кривая N-го порядка строится рекурсивно: квадрат делится на 4 части и в каждой из частей рисуется кривая (N-1)-го порядка. При этом верхние части остаются без изменений, а нижние поворачиваются на 90 градусов в разные стороны. Далее, все части соединяются тремя отрезками, образуя непрерывную ломаную.
На следующем рисунке показаны первые три кривые:
Робот начал свое движение по кривой Гильберта из клетки с координатами (1,1) и в некоторый момент остановился в клетке с координатами (X,Y). Ваша задача – определить количество шагов, которые он сделал, чтобы попасть в данную клетку. За шаг следует считать перемещение в соседнюю клетку.
Входные данные
Входной файл INPUT.TXT содержит натуральные числа N, X и Y (N ≤ 30, X,Y ≤ 2N). Здесь N – порядок кривой Гильберта, (X,Y) – координата робота.
Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на задачу.
Примеры
№ | INPUT.TXT | OUTPUT.TXT |
1 | 1 1 1 | 0 |
2 | 2 3 4 | 9 |
3 | 3 6 5 | 33 |
Система оценки
Решения, работающие только для N ≤ 3, будут оцениваться в 20 баллов.
Решения, работающие только для N ≤ 10, будут оцениваться в 70 баллов.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|