e-olymp
Задачи

Ханойские башни - перезагрузка

Ханойские башни - перезагрузка

prb6156

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

Да, пока вы не успели поверить в то, что монахи индуистского монастыря действительно занимаются решением этой головоломки, спешу сообщить, что это всего лишь легенда. Причем вовсе не древняя, как большинство известных легенд. Придумал ее в конце XIX века французский математик Эдуард Люка. Красивая история оказалась очень удачным рекламным трюком для "раскрутки" (как сказали бы современные PR-менеджеры) придуманной Люка изящной головоломки, выполненной из дерева и состоящей из восьми дисков. Начиная с 1883 года она продавалась под разными названиями — "Башни Брахмы", "Головоломка о конце света", "Пагода-головоломка", да и место действия легенды неоднократно переносилось то в Китай, то в Тибет, но в итоге "прижилось" во Вьетнаме — вместе с названием "Ханойские башни".

Когда же завершится жизнь очередного нового Брахмы, с учётом того, что он обязательно учтёт опыт своего предшественника и дисков у монахов однозначно будет больше?

Входные данные

Единственное число - количество дисков n (64n10000), выданное монахам очередным Брахмой.

Выходные данные

Единственное число - минимальное количество перекладываний, необходимое монахам для переноса башни с 1-го стрежня на 3-й в оптимальном режиме.

Лимит времени 1 секунда
Лимит использования памяти 32 MiB
Входные данные #1
64
Выходные данные #1
18446744073709551615
Автор Анатолий Присяжнюк