Xanoy minorasi

Qiyin 1000 ms 64 MB 55%

Mavzular: Rekursiya

Uchta qoziq bor. Birinchi qoziqda n ta disk turibdi: eng kattasi pastda, yuqoriga qarab kichrayib boradi. Barcha disklarni uchinchi qoziqqa eng kam sonli yurishda o'tkazish kerak.

Qoidalar: bir yurishda faqat bitta, eng yuqoridagi diskni olish mumkin; katta diskni kichik disk ustiga qo'yib bo'lmaydi.

Eng kam yurishlar ketma-ketligi yagona va 2ⁿ − 1 ta yurishdan iborat. Shu ketma-ketlikdagi k-yurishni toping: u qaysi qoziqdan qaysi qoziqqa qilinadi?

Kiruvchi ma'lumotlar

Bitta qatorda ikkita butun son: n va k.

Chiquvchi ma'lumotlar

Ikkita son: k-yurishda disk olinadigan va qo'yiladigan qoziqlar raqami (1, 2 yoki 3).

Izoh

1 ≤ n ≤ 60
1 ≤ k ≤ 2ⁿ − 1

Masalan, n = 2 da yurishlar: 1→2, 1→3, 2→3.

Misollar

Kirish #1

2 1

Chiqish #1

1 2

Kirish #2

2 3

Chiqish #2

2 3