15/05/2024 09:54:32

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

1340. Башня

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

На доске имеется три колышка A, B и C. На колышек A нанизаны `N` одинаковых дисков, пронумерованных сверху вниз от 1 до `N`. Колышки B и C пустые. Необходимо перенести все диски на колышек B, используя в качестве вспомогательного колышек C и соблюдая следующие правила:

нельзя возвращать диски на колышек A;
нельзя снимать диски с колышка B;
можно перемещать только по одному диску за ход.

начальное положение

конечное положение

Определить, возможно ли получить заданный конечный порядок размещения дисков на колышке B и минимальное количество ходов для этого.

Во входном файле в первой строке содержится количество дисков `N` (`1\ ≤\ N\ ≤\ 1000`) на колышке A. Следующие `N` строк файла содержат перестановку чисел от 1 до `N` (по одному числу в строке) – требуемое расположение дисков на колышке B в порядке сверху вниз.

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

Пример ввода

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