07/04/2025 04:53:36

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

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

Задачи

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

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

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

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

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

Задачи

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 (ноль), в противном случае.

Пример ввода

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