Одне перекладування Ханойських веж
Тут ми рзглянемо класичну задачу про Ханойські вежі. У ній є три стержні та набір круглих дисків. Нехай кількість дисків дорівнює n. Диски мають різний розмір, ніякі два з яких не мають одинакового радіусу. Основне правило полягає у тому, що заборонено класти більший диск на менший. Пронумеруємо диски від 1 (найменший) до n (найбільший), стержні будемо називати A, B та C. Спочатку усі диски розміщено на стержні A. Мета задачі полягає у перенесенні їх на стержень C, послідовно перекладаючи їх один за одним, ніколи не кладучи більший диск на менший. Існує добре відомий розв'язок, який рекурсивно переміщує n–1 диск з A на B, потім переміщує один диск з A на C, після чого рекурсивно переміщує n – 1 диск з B на C.
Псевдокод рекурсивного розв'язання задачі про Ханойські вежі має вигляд:
move(num_disks, from_post, spare_post, to_post)
if (num_disks == 0)
return
move(num_disks – 1, from_post, to_post, spare_post)
print ("Move disk ", num_disks, " from ", from_post, " to ", to_post)
move(num_disks – 1, spare_post, from_post, to_post)
У цій задачі необхідно визначити k-те перекладування за заданими k та n.
Вхідні дані
Кожен рядок містить два цілих числа k та n. В кінці вхідних даних розміщено рядок з двух нулів. Вхідні значення коректні, k та n - додатні цілі числа, k менше 2^n, тому k-те перекладування існує, n не більше 60, тому відповідь поміщається у 64-бітовий цілочисельний тип.
Вихідні дані
Вивести шукане k-те перекладування, здійснене алгоритмом. Формат виведення повинен бути наступним: "Case", один пропуск, номер тесту, двокрапка, один пропуск, і відповідь для поточного тесту у форматі: номер диску, ім'я стержня from_post та ім'я стержня to_post, відокремлюючи їх одним пропуском. Пропуски у кінці рядка не виводити.