المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:متفرقه:سوال های تمرینی دوره ی تابستان:سوال ۱۵

Magic

پس از موفقیت مکعب جادویی، آقای روبیک نمونه‌ی مسطح آن را با نام مربع‌های جادویی ابداع کرد که از ۸ مربع یکسان تشکیل شده است:

در این مسئله، ما حالتی را بررسی می‌کنیم که رنگ همه‌ی خانه‌ها متفاوت باشد. رنگ‌ها را با اعداد ۱ تا ۸ نمایش می‌دهیم. وضعیت مربع‌های جادویی را این‌گونه نشان می‌دهیم که رنگ خانه‌ها از خانه‌ی چپ و بالا می‌نویسیم و درجهت عقربه‌های ساعت حرکت می‌کنیم. به‌عنوان مثال، نمایش شکل ۱ با رشته‌ی $(1,2,3,4,5,6,7,8)$ مشخص می‌شود. این همیشه وضعیت آغازین است.

سه عمل ساده برای تغییر مربع‌های جادویی داریم. این اعمال را با حروف A و B و C نشان می‌دهیم.

  • A: تعویض سطرهای بالا و پایین
  • B: یک واحد شیفت دادن مربع‌ها به سمت راست به‌صورت دوری
  • C: یک واحد دوران چهار خانه‌ی میانی درجهت عقربه‌های ساعت

در این‌جا می‌توانید حاصل انجام دادن هریک از این اعمال را بر روی وضعیت آغازین ببینید.

ورودی

یک سطر شامل ۸ عدد صحیح (جایگشتی از اعداد ۱…۸) که نشان‌دهنده‌ی حالت نهایی است.

خروجی

  • در سطر اول خروجی طول کوتاه‌ترین دنباله‌ی مطلوب را بنویسید.
  • در سطر دوم دنباله‌ای با طول کمینه برای انجام تبدیل خواسته‌شده بتویسید. در صورت وجود چندین دنباله، آر را که از لحاظ الفبایی کمینه است بنویسید.

محدودیت‌ها

  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
2 6 8 4 5 7 3 1 7
BCABCCB

پاسخ

منتظر پر کردن این قسمت توسط علاقمندان هستیم.


ابزار صفحه