المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۱۸:سوال ۸

Folding

در یک صفحه‌ی طلقی شفاف به‌طول افقی ‎$m$‎ و ارتفاع عمودی ‎$n$‎، ‎$p$‎ نقطه‌ی سیاه رسم شده است. در هر حرکت می‌توانیم صفحه را از وسط به‌صورت افقی یا عمودی تا کنیم. پس از هر تاکردن مساحت صفحه نصف می‌شود و ممکن است برخی از نقاط روی هم قرار گیرند، به‌طوری که وقتی به صفحه شفاف می‌نگریم به صورت یک نقطه دیده شوند. می‌خواهیم با انجام دقیقاً ‎$k$‎ عمل تاکردن، کاری کنیم که کم‌ترین تعداد نقطه در صفحه‌ی تا خورده دیده شود. دقت کنید که پس از هر تا طول و عرض طلق باید اعداد طبیعی باقی بمانند.

ورودی

  • در سطر اول، به‌ترتیب ‎$m$‎، ‎$n$‎، ‎$p$‎ و ‎$k$‎ داده می‌شوند.
  • سپس در هر یک از ‎$p$‎ سطر بعد، مختصه یک نقطه به‌صورت طول و ارتفاع آن (نسبت به گوشه‌ی پایین و سمت چپ صفحه) آمده است.
  • ‎$1 \leq k \leq 100$‎
  • ‎$1 \leq p \leq 50000$‎
  • ‎$m \times n$‎ مضربی از ‎$2^k$‎ می باشد.
  • همه اعداد ورودی صحیح، نامنفی و کوچکتر از ‎$2^{64}$‎ هستند.

خروجی

  • در سطر اول خروجی کم‌ترین تعداد نقاط قابل رویت پس از ‎$k$‎ حرکت را بنویسید.
  • در سطر بعد رشته‌ای به طول ‎$k$‎ نویسه بنویسد که نوع هر یک از ‎$k$‎ عمل تا کردن نشان دهد.
    • حرف ‎$i$،‎ام این رشته نوع تا کردن ‎$i$‎ ام است. در یک تای افقی اگر نیمه‌ی پایین صفحه روی نیمه‌ی بالای صفحه قرار بگیرد حرف B‎ و اگر نیمه‌ی بالای صفحه روی نیمه‌ی پایین قرار بگیرد حرف ‎T‎ را درج می‌کنیم. به‌همین صورت، اگر پس از یک تای عمودی نیمه سمت چپ صفحه روی نیمه‌ی سمت راست قرار بگیرد حرف L‎ و در حالت برعکس حرف ‎R‎ را در خروجی درج می‌کنیم.
  • اگر مساله چند جواب بهینه داشته باشد، رشته‌ی جوابی را چاپ کنید که به لحاظ ترتیب الفبایی ‎(Lexicographical Order)‎ نخستین باشد.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
16 4 6 2‎
1 1‎
2 2‎
1 3‎
15 1‎
14 2‎
15 3
2‎
BL

ابزار صفحه