Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


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

Folding

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

ورودی

  • در سطر اول، به‌ترتیب ‎m‎، ‎n‎، ‎p‎ و ‎k‎ داده می‌شوند.
  • سپس در هر یک از ‎p‎ سطر بعد، مختصه یک نقطه به‌صورت طول و ارتفاع آن (نسبت به گوشه‌ی پایین و سمت چپ صفحه) آمده است.
  • 1k100
  • 1p50000
  • m×n‎ مضربی از ‎2k‎ می باشد.
  • همه اعداد ورودی صحیح، نامنفی و کوچکتر از ‎264‎ هستند.

خروجی

  • در سطر اول خروجی کم‌ترین تعداد نقاط قابل رویت پس از ‎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

ابزار صفحه