فهرست مندرجات
board
هپید به تازگی طراحی مدارهای الکتریکی را یاد گرفته و دیروز یک مدار جدید طراحی کرده که شامل $n$ چیپ است. او پس از اینکه چیپ‌ها را روی بُرد قرار داد، تازه یادش افتاد که هر چیپ باید به منبع تغذیه نیز متصل باشد. هر چیپ به شکل مستطیل است و دقیقاً دو ضلع فعّال دارد. هپید باید دقیقاً یکی از اضلاع فعّال چیپ را انتخاب کند و آن را با کابلی (هم‌عرض با اندازه‌ی ضلع انتخاب‌شده) به بیرون برد وصل کند.
با توجه به اینکه کابل‌ها تک‌رشته‌ای و شکننده هستند، او حقّ خم کردن آن‌ها را ندارد. ضمناً، کمترین تماسی میان دو عنصر متفاوت باعث ایجاد نویز و خرابی کلّ مدار می‌شود. (در واقع، هیچ کابلی نباید با هیچ چیپ یا کابل دیگری کوچکترین تماسی داشته باشد)
به هپید کمک کنید تا کابل‌کشی‌های لازم را انجام دهد.
ورودی
- در سطر اول ورودی $n$، تعداد چیپ‌های روی برد آمده است.
- در $n$ سطر بعد در هر خط مختصات نقطه‌ی گوشه‌ی پایین چپ و گوشه‌ی بالا راست چیپ آمده و در ادامه آن دو حرف لاتین آمده که نشان‌دهنده اضلاع فعال آن چیپ است. U به معنای ضلع بالا، D به معنای ضلع پایین، L به معنای ضلع چپ و R به معنای ضلع راست.
- مساحت گیت‌ها ناصفر است، و گیت‌ها با هم کوچکترین تماسی ندارند.
- تمام اعداد ورودی صحیح و کوچکتر از $10^9$ هستند.
- در ۳۰٪ تست‌ها مساحت تمام گیت‌ها دقیقاً برابر یک است.
- در تمام تست‌ها $n \leq 10^4$.
خروجی
- در صورت وجود سیم کشی معتبر عبارت Yes را چاپ کنید و در ادامه، $n$ خط چاپ کنید که هر خط شامل یکی از حروف L ، U، R و D است. حرف موجود در خط $i$ام نشانه‌ی جهتی است که برای $i$امین چیپ استفاده کردید.
- در صورتی که این کار امکان پذیر نبود، در تنها خط خروجی عبارت No Solution را چاپ کنید.
محدودیت‌ها
- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
ورودی و خروجی نمونه
| ورودی نمونه | خروجی نمونه |
|---|---|
| 3 1 1 4 5 D R 5 3 8 7 R L 2 8 9 10 U D | Yes D R U |
| 4 1 1 4 5 D R 5 3 8 7 R L 2 8 9 10 U D 5 1 6 2 L U | No Solution |
توضیحات
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
