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

printЗадачи

1297. Ханойская башня

Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Головоломку "Ханойская башня" придумал французский математик Эдуард Люка. Игрушка, продававшаяся в 1883 году, состояла из 8 колец. Задача состоит в том, чтобы перенести за наименьшее число ходов пирамиду из колец разного диаметра с одного колышка на другой, используя третий колышек как вспомогательный. За один раз разрешается переносить только одно кольцо, причем нельзя класть кольцо большего диаметра на кольцо меньшего диаметра. В описании к игре рассказывалось о мифической "Пирамиде браминов", состоявшей из 64 золотых колец, в храме индийского города Бенареса. Каждый ход жрецы сопровождают молитвами, помогающими им действовать в правильном направлении. По преданию, как только жрецы храма сделают последний ход, грянет гром, храм рассыплется в пыль, погаснут звезды и наступит конец света. Так как для завершения работы жрецам потребуется `10^14` лет, то можно считать это предсказание верным: не только храм за такое время превратится в пыль, но и по расчетам физиков все звезды превратятся в холодные тела или черные дыры.
Решается головоломка достаточно просто. Например, чтобы переместить пирамиду из 8 дисков с колышка #1 на #2, используя #3, нужно
  • переместить семь верхних дисков с колышка #1 на #3, используя #2;
  • переместить восьмой диск с колышка #1 на #2;
  • переместить семь дисков с колышка #3 на #2, используя #1.
Наименьшее количество ходов для решения головоломки из `N` дисков равно `2^N-1`.
Напишите программу, которая по количеству дисков и числу сделанных ходов в минимальной последовательности ходов, требующихся для решения головоломки, определяет размещение дисков по колышкам после указанного хода. Диски пронумерованы от 1 (самый маленький) до `N` (самый большой). Требуется перенести диски с колышка #1 на колышек #2.
Во входном файле содержится две строки. В первой строке содержится целое число `N` – число дисков (`1\ ≤\ N\ ≤\ 100`). Во второй строке содержится целое число `K` – число выполненных ходов (`0\ ≤\ K\ ≤\ 2^N-1`).
В выходной файл вывести три строки – в `j`-й строке содержится количество и номера дисков, начиная с меньшего диска, на `j`-ом колышке, разделенные пробелом.

Пример ввода

8
19

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

3 6 7 8
2 3 4
3 1 2 5
loading