0221. Пизанская башня

Имя входного файла:	pisa.in
Имя выходного файла:	pisa.out
Ограничение по времени:	2 s
Ограничение по памяти:	256 megabytes

Многим из вас, наверное, известна легенда про Ханойскую башню. Легенда гласит, что в одном далеком монастыре находится бронзовый диск, на котором закреплены три алмазных стержня. Давным-давно, в самом начале времен, монахи этого монастыря провинились перед богами. Разгневанные боги положили n дисков на один из стержней, все диски имели разные радиусы и были расположены по убыванию радиуса – самый большой диск лежал снизу, на нем диск поменьше, …, самый маленький диск располагался сверху. Монахи должны перекладывать диски между стержнями, причем каждый раз должны класть диск либо на пустой стержень, либо поверх большего диска. Как только все n дисков будут переложены со стержня, на который боги сложили их, на другой стержень, башня вместе с храмом обратятся в пыль и под громовые раскаты погибнет мир.

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

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

Петю заинтересовало, за какое минимальное число действий можно перенести все диски с первого стержня Пизанской головоломки на третий. Помогите ему выяснить это.

Формат входного файла

Во входном файле задано единственное натуральное число n (1 ≤ n ≤ 40) – количество дисков.

Формат выходного файла

Выведите единственное число – минимальное число перекладываний, необходимое для того, чтобы все диски оказались на третьем стержне.

Пример:

В примере можно действовать следующим образом: переложить маленький диск с первого стержня на третий, затем средний диск с первого на второй, затем маленький с третьего на второй (поверх среднего), затем большой диск с первого на третий, и, наконец, последним действием пару дисков со второго стержня на третий. Всего необходимо пять действий.

pisa.in	pisa.out
3	5

Источник: Командное школьное первенство Республики Карелия по программированию, 30 октября 2011.

Обсудить       Отправить решение