Неправильные монахи
В одном из буддийских монастырей монахи уже тысячу лет занимаются перекладыванием дисков. Они располагают тремя стержнями, на которых надеты диски разных размеров. В начальном состоянии какое-то количество дисков было надето на первый стержень и упорядочены по размеру - от меньших к большим сверху вниз. Монахи должны переложить все диски с первого стержня на третий, выполняя единственное условие – любой диск нельзя положить на диск меньшего размера. При перекладывании можно использовать все три стержня. Монахи перекладывают один диск за одну секунду. Как только они закончат свою работу, наступит конец света.
Ну разве это по-монашески, приближать конец света? Неправильные какие-то монахи... :)
Поэтому нас не будет интересовать ответ на вопрос, каким-то образом связанный с апокалипсисом, а будет интересовать ответ на более привычный в обыденной нашей жизни вопрос: А за какое наименьшее количество перекладываний монахи смогут завершить свою работу, при условии, что перекладывают они диски оптимальным образом?
Входные данные
Количество дисков n (0 ≤ n ≤ 64), имеющихся в распоряжении монахов. По странному стечению обстоятельств число дисков в этой задаче не превышает количества клеток на обычной шахматной доске.
Выходные данные
Выведите наименьшее количество перекладываний, за которое монахи смогут завершить свою работу.