Masala #0160

Xotira 16 MB Vaqt 500 ms
14

Hanoy minorasi 2

Hanoy minorasi o’yini judayam mashhur o’yin, unda 3 ta ustun va bir nechta har xil diametrli disklar bo’lari. O’yin boshida disklar qaysidir bir ustunda yuqoridan pastga disklar diametri o’sish tartibida saralangan holda joylashgan bo’ladi va biz shu disklarni boshqa bir ustunga quyidagi shartlarni buzmasdan yig’ishimiz kerak:

  • Bir marotada faqatgina bitta diskni boshqa ustunga ko’chirish mumkin.
  • Har bir ko’chirishda qaysidir ustunning eng yuqoridagi diskini olib boshqa bir ustunning eng yuqori qismiga qo’yiladi.
  • Hech bir disk o’zidan kichik diskning ustiga qo’yilmaydi.

Adiz 3 ustunli Hanoy minorasidan zerikdi va o’zi uchun 4 ustunli Hanoy minorasi o’yinini yaratdi, uning o’yini ham yuqoridagi barcha shartlarga bo’ysunadi.

Adizning Hanoy minorasida dastlab N ta disk minoralarning 1-ustunida joylashgan. Adiz o’yinni allaqachon boshlab yuborgan, sizga disklarning Hanoy minorasida joylashganligi tartibi beriladi, siz Adiz eng kamida nechta yurish amalga oshirganligini aniqlang.


Kiruvchi ma'lumotlar:

INPUT.TXT kirish faylining dastlabki satrida bitta butun son, N(1 ≤ N ≤ 10) – disklar soni kiritiladi. Keyingi qatorda N ta butun son, 1 dan N gacha diametrli disklarning mos ravishda har biri hozirgi holatda o’yinning qaysi ustunida ekanligi beriladi.


Chiquvchi ma'lumotlar:

OUTPUT.TXT chiqish faylida yagona son, Adiz o’yinni boshlaganidan buyon eng kamida nechta yurish amalga oshirganligini chop eting.


Misollar
# input.txt output.txt
1
3
1 4 1
3
Izoh:

1-testda

Dastlabki holat

1-yurishda

2-yurishda

3-yurishda(ya'ni joriy o'yindagi joriy holat)

 

1

 

 

 

2

 

 

 

3

 

 

 

 

 

 

 

 

 

2

 

 

 

3

1

 

 

 

 

 

 

 

 

 

 

 

 

3

1

 

2

 

 

 

 

 

 

1

 

 

 

3

 

 

2