المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی انتخاب تیم:دوره ی ۱۴:سوال ۲۳

بازی رایانه‌ای

یک بازی کامپیوتری روی یک جدول $6\times 6$ اجرا می‌شود: ابتدا در هر خانه‌ جدول یکی از اعداد ۱ تا ۳۶ نوشته شده است (هر عدد دقیقا یک بار در جدول آمده است). هدف ما آن است که اعداد را با انجام ۳۶ حرکت در خانه‌های جدول مرتب کنیم: اعداد ۱ تا ۶ در سطر اول از چپ به راست، اعداد ۷ تا ۱۲ در سطر دوم از چپ به راست و به همین ترتیب. این ۳۶ حرکت به این صورت انجام می‌شوند که ابتدا یک حرکت روی خانه‌ای که در انتهای بازی عدد ۱ در آن خواهد بود (خانه‌ی بالا سمت چپ) انجام می‌گیرد، سپس دومین حرکت روی خانه‌ای که در انتهای بازی حاوی عدد ۲ خواهد بود (خانه‌ی دوم از سطر اول) و … به همین ترتیب سی‌و‌ششمین حرکت روی خانه‌ای انجام می‌گیرد که در نهایت حاوی عدد ۳۶ خواهد بود (خانه‌ی پایین سمت راست). این ۳۶ حرکت دقیقا به همین ترتیب گفته شده انجام می‌گیرند و پس از حرکت سی‌وششم جدول باید مرتب شده باشد.

فرض کنید می‌خواهیم روی خانه سطر $i$ ام و ستون $j$ ام یک حرکت انجام دهیم. برای انجام این حرکت باید یکی از دو انتخاب زیر را انجام دهیم: یا آن‌که همه‌ی خانه‌های سطر $i$ ام را یک شیفت دایره‌ای به راست دهیم، یا آن‌که همه‌ی اعداد ستون $j$ ام را یک شیفت دایره‌ای به پایین دهیم. منظور از شیفت دایره‌ای اعداد یک سطر به سمت راست این است که عدد خانه‌ی اول آن سطر (خانه‌ی سمت چپ) به خانه‌ی دوم می‌رود، عدد خانه‌ی دوم به خانه‌ی سوم و … عدد خانه‌ی ششم به خانه‌ی اول منتقل می‌شود. همچنین منظور از شیفت دایره‌ای اعداد یک ستون به پایین آن است که عدد خانه اول آن ستون (خانه‌ی بالا) به خانه‌ی دوم، عدد خانه‌ی دوم به خانه‌ی سوم … و عدد خانه‌ی ششم به خانه‌ی اول آن ستون منتقل می‌گردد.

ورودی

در فایل ورودی وضعیت اولیه‌ی جدول در شش سطر آمده است.

خروجی

در فایل خروجی در ۶ سطر ۳۶ حرف بنویسید که حروف به ترتیب نوع انتخاب انجام شده برای حرکت‌ها را مشخص می‌کنند. یک حرف $R$ در سطر $i$ و ستون $j$ ام فایل خروجی نشان می‌دهد که حرکت انجام شده بر روی خانه‌ی $(i,j)$، شیفت دایره‌ای سطر $i$ به سمت راست بوده‌ است. همچنین حرف $D$ نشان‌دهنده‌ی شیفت دایره‌ای ستون $j$ به سمت پایین می‌باشد. بین هر دو حرف در هر سطر یک فاصله بگذارید.

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

ورودي نمونه خروجي نمونه
7 1 2 3 4 5
13 8 9 10 11 12
19 14 15 16 17 18
25 20 21 22 23 24
31 26 27 28 29 30
6 32 33 34 35 36
D R R R R R
R R R R R R
R R R R R R
R R R R R R
R R R R R R
R R R R R R

ابزار صفحه