Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1340. Башня
Стеки, очередиОлимпиадные задачи на русском языке
| 11/04/1999 | Региональная олимпиада Информатика-1999 (5) |
Ограничения: время – 200ms/500ms, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение 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 (ноль), в противном случае.
Пример ввода
6 2 3 4 5 6 1
Пример вывода
10
