المپدیا

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

ابزار کاربر

ابزار سایت


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

پیزا سازی

کمیته‌ی دانشجویی تصمیم گرفته بزنه تو خط کار ساختمونی و از این حرفا! یه شرکت هم تاسیس کرده به اسم شرکت پیمانکاری $INOISC$ با مسئولیت محدود. هيئت مدیره‌ی این شرکت هم بالطبع اعضای کمیته هستند! شرکت به عنوان اولین کار می‌خواد توی مناقصه‌ي پیمانکاری ساختن تعدادی برج، شبیه برج پیزا شرکت کنه. کمیته از شما خواسته یه برنامه بنویسید که با کمک اون شرکت بتونه این مناقصه رو ببره.

$n$ تا نقطه روی محور داریم. مختصات این نقاط را با $a_i$ ها نشان می‌دهیم ($a_i$ ها همگی متفاوت هستند). روی نقطه $i$ ام می‌توانیم برجی به طول $b_i$ بسازیم. برج‌ها باید با زاویه‌ی ۶۰ درجه نسبت به افق (به طرف چپ یا راست) ساخته شوند. سمت چپ‌ترین و سمت راست‌ترین برج حتما باید ساخته شوند. در ضمن سمت چپ‌ترین برج باید به سمت راست و سمت راست‌ترین برج باید به سمت چپ ساخته شود. می‌خواهیم بیش‌ترین تعداد برج را بسازیم به طوری که برج‌ها با هم برخورد نکنند! (اشتراک در یک نقطه هم برخورد محسوب می‌شود) فرض کنید سمت راست‌ترین و سمت چپ‌ترین برج با هم برخورد نمی‌کنند.

ورودی

در فایل ورودی اول $n$ (تعداد نقاط) و بعد در یک خط $a_i$‌ ها و در خط بعد $b_i$ ها آمده است. ($n\leq 500$ و $|a_i|\leq 5 \times 10^8$)

خروجی

در فایل خروجی در یک سطر در مکان $i$ ام و ضعیت برج $i$ ام را بنویسید. $R$‌ به نشانه‌ی راست، $L$‌ به نشانه‌ي چپ و $S$ به نشانه‌ی عدم ساخت برج است.

محدودیت‌ها

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

ابزار صفحه