مسِئله ی K : برج هانوی

مساله «برج هانوی» از سه میله با نام های A و B و C تشکیل می شود که n دیسک با قطر های مختلف ( و ارتفاع های یکسان ) در میله ها قرار دارند. در ابتدای کار تمام دیسک ها به صورت مرتب شده بر اساس قطرشان ( طوری که کم قطرترین دیسک بالاترین و بزرگ ترین دیسک پایین ترین باشد ) روی میله A قرار دارند.

یک حرکت «مجاز» در این مساله برداشتن بالاترین دیسک از یک میله( میله مبدا )و قرار دادن آن در میله ای دیگر( میله مقصد ) است بطوری که هیچ گاه یک دیسک روی دیسکی با قطر کوچکتر قرار نگیرد. با این وصف ، یک حرکت را می توان با دو حرف بزرگ انگلیسی نمایش داد که حرف اول میله مبدا و حرف دوم میله مقصد است. برای مثال حرکت AB یعنی برداشتن بالاترین دیسک میله A و قرار دادن آن روی تمام دیسک های میله B ( در صورت وجود ). دقت کنید که حرکت AB تنها زمانی مجاز است که میله A حداقل یک دیسک داشته باشد و بعلاوه یا میله B خالی باشد یا قطر بالاترین دیسک میله A ( که جابجا می شود ) از قطر بالاترین دیسک میله B کمتر باشد.

با شروع از حالتی که تمام دیسک ها بصورت مرتب در میله ی A قرار دارند ( نظیر شکل بالا )، بازی هنگامی تمام می شود که تمام دیسک ها به همین ترتیب در میله B قرار بگیرند ( و میله های A و C خالی باشند ) یا تمام دیسک ها به همین ترتیب در میله ی C قرار بگیرند ( و میله های A و B خالی باشند ).

هوشنگ برای حل کردن این معما ، الگوریتم زیر را در پیش می گیرد. او ابتدا یک جایگشت از تمام 6 حرکت موجود در نظر می گیرد ( مثلا جایگشت CB ، AC ، BA ، BC ، AB ، CA از چپ به راست ) ، سپس در هر مرحله سمت چپ ترین حرکت مجاز از حرکات این جایگشت را انجام می دهد. علاوه بر این ، او هبچ وقت دوست ندارد یک دیسک را در دو حرکت متوالی جابجا کند و از این رو اگر یک حرکت ( بعد از حرکت اول ) از مقصد حرکت قبلی آغاز شود ، او این حرکت را غیر مجاز تلقی می کند. برای مثال اگر جایگشت نمونه ی گفته شده را روی میله های شکل در نظر بگیریم ، اولین حرکت هوشنگ AB خواهد بود   ( چرا که CA بدلیل خالی بودن میله C غیر مجاز است ) و حرکت دوم او AC خواهد بود: CA غیر مجاز است چون C هنوز خالی است؛ AB غیر مجاز است چون دیسک با قطر 2 را نمی توان روی دیسک با قطر 1 ( که در حرکت اول به B منتقل شده ) قرار داد؛ BC نیز غیر مجاز است چرا که دیسک رویی B در حرکت قبلی تکان خورده و هوشنگ دوست ندارد یک دیسک را در 2 حرکت متوالی جابجا کند و از این رو سمت چپ ترین حرکت مجاز ، AC است!

می توان اثبات کرد که الگوریتم هوشنگ همیشه پایان می یابد! آنچه از شما خواسته می شود این است که با دانستن تعداد دیسک ها و استراتژی هوشنگ( جایگشتی از 6 حرکت ممکن )، مشخص کنید که هوشنگ چند جابجایی انجام می دهد تا بازی تمام شود.

ورودی

در سطر اول ورودی ، تعداد تست داده می شود. سپس هر تست در 2 خط داده می ش.د که خط اول تنها یک عدد n را داشته و در خط دوم یک جایگشت از حرکات ممکن بصورت 6 رشته 2 حرفی ( معتبر و دو به دو متمایز) داده می شود.

خروجی

به ازای هر تست ورودی ، در یک سطر تعداد حرکاتی که هوشنگ می کند را بنویسید.

محدودیت ها

می دانیم که N<=۱ و N<=۳۰  و جواب خروجی هیچ تستی از 10 به توان 18 بیشتر نبست.

دانلود برنامه سوال

دانلود فایل PDF مساله