You are not allowed to perform this action
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 |
| ▸ سوال قبل | سوال بعد ◂ |