المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۳:عملی:سوال ۱

قفل جادویی

هری پاتر در راه رسیدن به سنگ جادو به قفلی برخورد کرده است که شامل $1 \leq n \leq1000$ کلید با شماره‌های ۱ تا $n$ می‌باشد. در حاشیه این قفل رشته‌ای از $L$ و $R$ به طول $n-1$ دیده می‌شود که طی تحقیقات هرمایونی به عنوان رشته‌ی راهنما شناسایی شد. این تحقیقات نشان می‌دهد که در صورتی قفل باز می‌شود که هری کلیدها را با یک ترتیب (جایگشت) مشخص فشار دهد. این جایگشت باید به صورتی باشد که اگر ما جاگشت مورد نظر را با $i=1…n: \pi_i$ نشان دهیم و اگر حرف $i$ ام رشته‌ی راهنما $L$ باشد یعنی که $\pi_{i+1}< \pi_i$ و اگر $R$ باشد، یعنی که $\pi_{i+1}> \pi_i$. شما باید برای عبور از این درب به وی کمک کنید و یک جایگشت از کلیدها بیابید که شرایط رشته‌ی راهنما را داشته باشد.

ورودی

در سطر اول فایل ورودی، عدد $n$ و در سطر بعد رشته‌ی راهنما آمده است.

خروجی

در صورتی که مسئله جواب داشت، جایگشت مورد نظر را در سطر اول بنویسید. در غیر این صورت در خروجی عبارت No Solution را بنویسید.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
5
LRLL
2 1 5 4 3

ابزار صفحه