- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
میدانیم شرکتهای هرمی جایگاه ویژهای در میان اهالی برره دارند.
جان نثار برره شرکت هرمی نثارکوداتبیآر (NesarCo.Br) را به منظور کلاهبرداری و پولشویی تأسیس کرده است. شرکت نثارکو ساختار خاصی دارد. به این شکل که در شرکت \(H\) رده وجود دارد که در ردههای \(1\) تا \(H-1\) هر فرد ۲ زیردست دارد (یک زیردست چپ و یک زیردست راست). شمارهگذاری افراد به این ترتیب انجام میشود که ابتدا عدد \(x\) را برابر تعداد اعضای شرکت در نظر گرفته و سپس از ردهی صفر (بالاترین رده) شروع میکنیم و از چپ به راست افراد آن را به این شکل شماره گذاری میکنیم: عدد \(x\) را به فرد فعلی نسبت میدهیم و سپس از \(x\) یکی میکاهیم و هنگامی که ردهی فعلی شرکت کامل عددگذاری شد سراغ ردهی بعدی میرویم و... تا کل افراد شمارهگذاری شوند.
برای مثال شمارهگذاری افراد در نثارکو به ازای \(H = 3\) به شکل زیر است:
همچنین هر فرد به جز جان نثار (که رئیس کل است) در نثارکو با یک رشته از L و R هم شناخته میشود. رشتهی هر فرد به این صورت است که از جاننثار شروع میکنیم و به سمت فرد مورد نظر در ساختار شرکت حرکت میکنیم. در هر مرحله اگر به سمت چپ رفتیم L و در غیر این صورت R را یادداشت میکنیم.
چندی پیش شیرفرهاد گیر یکی از اعضای نثارکو افتاد و چند میلیون از پولش بالا کشیده شد. اما شیرفرهاد رشتهی کلاهبردار را دارد! شمارهی فرد کلاهبردار را پیدا کنید تا شیرفرهاد سراغ کلاهبردار برود و نفلهاش کند.
ورودی
در خط اول \(H\) و رشتهی کلاهبردار آمده است. تضمین میشود طول رشتهی کلاهبردار ناتهی و حداکثر \(H\) است.
\[1 \le H \le 30\]
خروجی
در تنها خط خروجی شمارهی فردی که از شیرفرهاد کلاهبرداری کرده است را چاپ کنید.
مثال
ورودی نمونه ۱
3 LR
خروجی نمونه ۱
11
مسیر گفته شده در شکل بالا مشخص شده است.
ورودی نمونه ۲
3 RRL
خروجی نمونه ۲
2
مسیر گفته شده در شکل بالا مشخص شده است.
ورودی نمونه ۳
2 L
خروجی نمونه ۳
6