~/algor $ cat masalalar/xanoy-minorasi
Xanoy minorasi
Muallif:
Iqbolshoh Ilhomjonov
Uchta qoziq bor, ular $1$, $2$ va $3$ deb raqamlangan. $1$-qoziqda $n$ ta disk turibdi: eng kattasi pastda, yuqoriga qarab kichrayib boradi. Barcha disklarni $3$-qoziqqa eng kam sonli yurishda o'tkazish kerak. Bir yurishda faqat bitta, eng yuqoridagi disk olinadi; katta disk kichik disk ustiga qo'yilmaydi.
Eng kam yurishlar ketma-ketligi yagona va $2^{n} - 1$ ta yurishdan iborat. Shu ketma-ketlikning $k$-yurishi qaysi qoziqdan qaysi qoziqqa qilinishini toping. Masalan, $n = 2$ da yurishlar: $1 \to 2$, $1 \to 3$, $2 \to 3$.
Kiruvchi ma'lumotlar
Bitta qatorda ikkita natural son: $n$ va $k$.
Chiquvchi ma'lumotlar
Bitta qatorda ikkita natural son: $k$-yurishda disk olinadigan va qo'yiladigan qoziqlar raqami ($1$, $2$ yoki $3$).
Izoh
$1 \le n \le 60$
$1 \le k \le 2^{n} - 1 \lt 2^{60}$
Misollar
2 1
1 2
2 3
2 3