- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
مرحله انتخابی پردیس کد به رومینا و علی سپرده شده است. آنها قرار است یک مسابقه طناب کشی برگزار کنند و هر کدام از بین شرکتکنندگان یک تیم انتخاب کنند. تمام اعضای تیم برنده به مرحله نهایی راه پیدا میکنند.
تیمکشی به این صورت است: ابتدا رومینا از بین شرکتکنندگان یک نفر را انتخاب میکند. سپس علی دو نفر از افراد باقیمانده را برمیگزیند. از این مرحله به بعد، نوبت انتخابها بهصورت یکی در میان (شروع از رومینا) ادامه مییابد و هر بار هر نفر دو شرکتکننده را انتخاب میکند تا زمانی که دیگر فردی برای انتخاب باقی نماند. (در صورتی که در پایان، تعداد شرکتکنندگانِ باقیمانده کمتر از تعداد لازم برای انتخاب باشد، رومینا یا علی در نوبت آخر خود تنها یک نفر را انتخاب میکنند.)
هدف رومینا و علی این است که قویترین تیم ممکن را تشکیل دهند؛ بنابراین هر دو با بهینهترین و هوشمندانهترین روش ممکن انتخابهای خود را انجام میدهند.
بعد از تیمکشی. رومینا تصمیم میگیرد که به تعدادی از اعضای تیم مقابل رشوه دهد که به نفع او کنار بکشند و در طنابکشی منفعل باشند. کمترین تعداد اعضایی که رومینا باید به آنها رشوه بدهد تا مجموع وزن تیم او بیشتر از تیم علی شود، چند نفر است؟ و اگر برعکس، علی بخواهد این کار را انجام دهد، پاسخ چگونه خواهد بود؟ روش رشوه دهی برای پیروزی رومینا یا علی را اعلام کنید.
وزن تمام شرکتکنندهها با یکدیگر متفاوت است
ورودی
در خط اول عدد طبیعی \(n\) داده میشود که نشاندهندهی تعداد شرکتکنندگان است.
در خط دوم، \(n\) عدد طبیعی داده میشود که وزن شرکتکنندگان را نشان میدهد.
در خط سوم، یکی از رشتههای "romina" یا "ali" آمده است که مشخص میکند در این تضمین داده میشود وزن هیچ دو فردی یکسان نیست.
\[2 \leq n , a_i \leq 10^5\]
خروجی
در خط اول، کمینهی تعداد افرادی را که فرد مورد نظر باید به آنها رشوه دهد چاپ کنید. در خط دوم، وزن این افراد را به ترتیب از سنگین به سبک بنویسید.
مثالها
ورودی نمونه ۱
5
1 4 6 9 2
romina
خروجی نمونه ۱
0
ورودی نمونه ۲
4
1 4 6 9
romina
خروجی نمونه ۲
1
6
ورودی نمونه ۳
4
5 7 3 1
ali
خروجی نمونه ۳
1
1