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

می‌دانیم روز آزادی بیان جایگاه ویژه‌ای در میان اهالی برره دارد.

امروز روز آزادی بیان در برره است، به همین منظور اهالی پایین ببره و بالا ببره در میدان شهر جمع می‌شوند و به نوبت به یکدیگر ناسزا می‌گویند.

روش ناسزا گفتن در برره به این ترتیب است که:

• ابتدا یکی از اهالی بالا برره یک ناسزا به پایین برره‌ای‌ها می‌گوید.

• سپس برای این که خشم پایین برره‌ای ها فروکش کند دو نفر از پایین برره‌ای‌ها به بالا برره‌ای‌ها ناسزا می‌گویند.

• در مرحله بعد ۳ نفر از بالا برره‌ای‌ها به پایین برره‌ای‌ها ناسزا می‌گویند.

• و این جریان به همین ترتیب ادامه پیدا می‌کند تا هنگامی که یکی از دو طرف در یک مرحله $K$ ناسزا به طرف دیگر بگوید.

در این هنگام است که خشم بر طرف مقابل حاکم شده و درگیری بین دو طرف صورت می‌گیرد.

کَیانوش که از دور به این ماجرا نگاه می‌کند، آهی عمیق می‌کشد، نگاهی معنادار به دوربین می‌اندازد و طرفی که اول خشمگین می‌شود را به بینندگان نشان می‌دهد. حال شما با گرفتن $K$ در ورودی، بگویید که کَیانوش کدام طرف را نشان داده.

ورودی🔗

در خط اول $K$ داده شده است. $1 \le K \le 100$

خروجی🔗

در تنها خط خروجی در صورتی که ابتدا بالابرره‌ای‌ها خشمگین می‌شوند Bala Barare و در غیر این صورت Payin Barare را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

1

خروجی نمونه ۱🔗

Payin Barare

ورودی نمونه ۲🔗

74

خروجی نمونه ۲🔗

Bala Barare

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

می‌دانیم تیم ملی نخودخوری جایگاه ویژه‌ای در میان اهالی برره دارد.

شیرفرهاد، سحرناز و شادونه‌خانم به مربی‌گری سالارخان اعضای تیم ملی نخودخوری برره‌اند. مثل همه‌ی رشته‌ها نخودخوری هم به بازی‌های تدارکاتی نیاز دارد، از این رو امروز قرار است تیم ملی در مغازه‌ی کیوون بالابرره نخود بخورند تا برای مسابقات آماده شوند. کیوون بالابرره نخود را کیلویی نمی‌فروشد! بلکه به ازای هر دقیقه، اگر یک نفر در مغازه مشغول نخودخوردن باشد به ازای هر نفر $a$ ریال، اگر دو نفر مشغول نخودخوردن باشند به ازای هر نفر $b$ ریال و اگر سه نفر مشفول نخودخوردن باشند به ازای هر نفر $c$ ریال می‌گیرد. زمان ورود و خروج شیرفرهاد، سحرناز و شادونه‌خانم به ترتیب داده شده‌است، محاسبه کنید سالارخان چند ریال باید به کیوون بالابرره بدهد.

ورودی🔗

در خط اول $a$، $b$، $c$ به ترتیب داده شده‌اند. در سه خط بعدی به ترتیب دو عدد داده می‌شود که زمان ورود و خروج شیرفرهاد، سحرناز و شادونه‌خانم است. زمان‌ها به دقیقه‌اند و مبدا زمان موقع بازشدن مغازه‌ی کیوون بالابرره است. همه‌ی اعداد ورودی بین ۱ تا ۱۰۰ هستند. دقت کنید منظور از این که در دقیقه‌ی $t$ یک نفر وارد\خارج می‌شود شروع دقیقه‌ی $t$ است. مثلا در مثال اول شیر فرهاد در شروع دقیقه‌ی ۱ وارد و در شروع دقیقه‌ی ۶ خارج می‌شود (۵ دقیقه در فروش‌گاه است). دقت کنید یک فرد در تمام مدتی که در مغازه است نخود می‌خورد.

$a > b > c$ $a, b, c \in \mathbb{N}$

خروجی🔗

مقدار پولی که سالارخان باید به کیوون بالابرره بدهد.

مثال🔗

ورودی نمونه ۱🔗

5 3 1
1 6
3 5
2 8 

خروجی نمونه ۱🔗

33

در دقایق ۱ و ۶ و ۷ یک نفر درون مغازه است (۵×۱×۳). در دقایق ۲ و ۵ دو نفر درون مغازه اند (۳×۲×۲). در دقایق ۳ و ۴ سه نفر درون مغازه اند (۱×۳×۲). $3 \times 1 \times 5+2 \times 2 \times 3+2 \times 3 \times 1 = 33$

ورودی نمونه ۲🔗

10 8 6
15 30
25 50
70 80 

خروجی نمونه ۲🔗

480

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

می‌دانیم بازی منطقی جایگاه ویژه‌ای در میان اهالی برره دارد.

شادونه‌خانم و شاخ‌شمشاد که از خوب‌های منطق برره هستند بازی دوز برره‌ای را اختراع کرده‌اند. جدول این بازی به شکل زیر است:

در هر خانه از جدول یا یک نخود وجود دارد یا خالی‌ست. در یک حرکت، بازیکن می‌تواند یک نخود و یک جهت (بالا، پایین، چپ یا راست) انتخاب کند اگر در آن جهت نخود دیگری وجود داشته باشد که پشت آن خالی باشد می‌تواند نخود انتخاب شده را در جهت انتخاب شده از روی نخود کناری بپراند (مثال‌ها را ببینید). شادونه‌خانم باید بازی را شروع کند و از شما می‌خواهد تا تعداد حرکت‌های ممکن برای شروع را حساب کنید.

ورودی🔗

جدول بازی در ۷ سطر می‌آید که در هر سطر ۷ کاراکتر وجود دارد. تضمین می‌شود که دو کاراکتر اول و دو کاراکتر آخر از دو سطر اول و دو سطر آخر کاراکتر * (به معنای خانه‌ی تهی) خواهد بود. در بقیه‌ی خانه‌ها ‍o (حرف کوچک) نشان‌دهنده‌ی نخود و . نشان‌دهنده‌ی خانه‌ی خالی‌ست.

خروجی🔗

در خروجی تعداد حرکت‌های ممکن برای شروع را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

**ooo**
**ooo**
ooooooo
ooo.ooo
ooooooo
**ooo**
**ooo**

خروجی نمونه ۱🔗

4

ورودی نمونه ۲🔗

**ooo**
**ooo**
..ooo..
oo...oo
..ooo..
**ooo**
**ooo**

خروجی نمونه ۲🔗

12

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

می‌دانیم یه قل دو قل جایگاه ویژه‌ای در میان اهالی برره دارد.

این بازی در برره به شکل عجیبی انجام می‌شود. بر روی یک خط $n$ سنگ قرار می‌گیرد که روی سنگ $i$اُم عدد $a_i$ نوشته شده و در موقعیت $x_i$ قرار دارد.

به ازای هر بازه‌ای از خط(بازه‌ای از $x$ها)، تعداد اعداد متمایزی که روی سنگ‌های داخل این بازه نوشته شده‌است را درجه‌ی الدنگی آن بازه می‌نامیم. شما باید بین همه‌ی بازه‌هایی که درجه‌ی الدنگی آنها بیشینه است کوتاه‌ترین (یعنی بازه‌ای که انتها منهای ابتدایش کمینه است) آنها را پیدا کنید و طول آن را چاپ کنید.

ورودی🔗

در خط اول $n$، تعداد سنگ‌ها آمده است. در هر یک از $n$ خط بعد در خط $i$ به ترتیب $x_i$ و $a_i$ آمده است. همه‌ی $x_i$ها متمایز اند. $1 \le n \le 50\ 000$ $1 \le a_i, x_i \le 10^9$

خروجی🔗

طول کوتاه‌ترین بازه با درجه الدنگی بیشینه را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

6
25 7
26 1
15 1
22 3
20 1
30 1

خروجی نمونه ۱🔗

4

بازه‌ی ۲۲ تا ۲۶ (با طول ۴) جواب است. درجه‌ی الدنگی این بازه ۳ است و طول آن برابر ۴. درجه‌ی الدنگی آن بیشینه است و طول آن بین تمام بازه‌هایی که درجه‌ی الدنگی آنها بیشینه است کمینه است.

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

می‌دانیم ** سیکل گرفتن ** جایگاه ویژه‌ای در میان اهالی برره دارد.

نظام، شیرفرهاد و کیوون می‌خواهند مدرک سیکل خود را بگیرند در این راستا باید در امتحان تستی‌ای که کَیانوش برای آنها طراحی کرده شرکت کنند.

از آنجایی که این ۳ نفر خواندن و نوشتن بلد نیستند (!) تصمیم می‌گیرند که بدون خواندن سوالات با الگوی تکرار شونده‌ی خاصی تست‌ها‌ را جواب بدهند. امتحانی که کَیانوش طراحی کرده دارای $N$ سوال ۳ گزینه‌ای است، همچنین در جدول زیر الگویی که هر فرد طبق آن به سوالات پاسخ می‌دهد نشان داده شده است:

حال ما به شما تعداد و کلید سوالات را می‌دهیم و شما باید بیشترین نمره‌ای که یک فرد از بین این ۳ نفر در امتحان کسب کرده و اسم افرادی را که بیشترین نمره را کسب کرده‌اند به دست آورید.

ورودی🔗

در خط اول ورودی عدد $N$ آمده که تعداد سوالات را نشان ‌می‌دهد و در خط بعدی رشته‌ای متشکل از اعداد ۱ تا ۳، به طول $N$ می‌آید که کلید سوالات را مشخص می‌کند (عدد $i$ام رشته گزینه‌ی درست برای سوال $i$ام امتحان را مشخص می‌کند). $1 \le N \le 100$

خروجی🔗

در خط اول خروجی بالاترین نمره‌ای که در امتحان کسب شده را چاپ کنید.

در خطوط بعدی اسم افرادی را چاپ کنید که بالاترین نمره‌ی امتحان را کسب کرده اند (به ترتیب حروف الفبا).

مثال🔗

ورودی نمونه ۱🔗

15
111323311123111

خروجی نمونه ۱🔗

7
keyvoon
nezam
shir farhad

ورودی نمونه ۲🔗

10
1112321332

خروجی نمونه ۲🔗

3
keyvoon
nezam

توضیح نمونه ۲: در این مثال

کیوون به سوالات سوم، ششم و هشتم،

نظام به سوالات اول، هفتم و نهم،

و شیرفرهاد به سوالات دوم و هشتم پاسخ درست داده‌اند.

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

می‌دانیم شرکت پالایش و پخش نخود جایگاه ویژه‌ای در بین اهالی برره دارد.

در راستای این هدف، شرکت پالایش و پخش نخود سالار (با مسؤلیت محدود) در نظر دارد سال آینده نخود مورد نیاز اهالی برره را تأمین کند. در راستای این هدف کَیانوش لیستی از میزان نخود مورد نیاز هر خانوار برره را جمع‌آوری کرده است. طبق برآورد در برره $n$ خانواده زندگی می‌کنند که $i$اُمین آنها در سال آینده به $a_i$ کیلو نخود نیاز خواهد داشت.

شرکت سالار با مذاکرات انجام شده $m$ کیلو نخود به برره وارد کرده‌ است. می‌دانیم هر خانواری که کمتر از نیازش نخود دریافت کند به اندازه‌ی مجذور اختلاف میزان دریافتی با میزان درخواستی‌اش ناسزا نثار سالارخان می‌کند. در صورتی که سالارخان نخودها را به صورت بهینه بین خانوارها پخش کند کمترین تعداد ناسزایی که می‌شنود را به دست آورید (دقت کنید که سالارخان تنها می‌تواند مقادیر صحیح و نامنفی کیلو نخود به هرخانوار بدهد).

ورودی🔗

در خط اول $m$، مقدار نخودی که سالارخان دارد، و $n$، تعداد خانوارهای برره، آمده است. در خط بعدی به ترتیب مقدار نخود مصرفی هر خانوار آمده است. تضمین می‌شود مقدار نخود وارد شده توسط شرکت سالار همیشه کمتر از مجموع نخود مصرفی کل خانوار های برره است. $1 \le m, a_i \le 2 \times 10^9$ $1 \le n \le 100\ 000$

خروجی🔗

کمترین ناسزایی که در حالت بهینه نثار سالارخان می‌شود را چاپ کنید.

تضمین می شود که جواب مسئله هیچ‌گاه از $4 \times 10^{18}$ بیشتر نمی‌شود.

مثال🔗

ورودی نمونه ۱🔗

5 3
1 3 2

خروجی نمونه ۱🔗

1

توضیح نمونه اول:

سالارخان به خانوار اول ۱ کیلو نخود و به هر یک از خانوار دوم و سوم ۲ کیلو نخود می‌دهد، در نتیجه تنها یک ناسزا از خانوار دوم نثارش می‌شود.

ورودی نمونه ۲🔗

10 4
4 5 2 3

خروجی نمونه ۲🔗

4

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

می‌دانیم بازی‌های اصیل جایگاه ویژه‌ای در میان اهالی برره دارد.

امروز کَیانوش و شیرفرهاد به مزرعه رفته‌اند تا نخود بکارند، از آنجا که نخود کاشتن در برره به صورت زیر پوستی انجام می‌شود، شیرفرهاد و کَیانوش تصمیم می‌گیرند در حین کاشت نخود یکی از بازی‌های اصیل برره‌ را هم انجام‌دهند.

این بازی اینگونه انجام می‌شود که ابتدا شیرفرهاد عدد $a$ و کَیانوش عدد $b$ را به این صورت انتخاب می‌کنند که عددی که شیر فرهاد انتخاب کرده از عدد انتخابی کَیانوش بیشتر نباشد. حال شیرفرهاد می‌خواهد عدد خود را (عدد $a$) برابر با عدد کَیانوش کند (عدد $b$) به این منظور شیرفرهاد در هر مرحله می‌تواند یکی از مقسوم علیه‌های عدد فعلی خود را (به جز عدد ۱ و خود عدد) به آن اضافه کند.

شیرفرهاد که هیچ‌گونه استعدادی در این بازی ندارد از شما می‌خواهد که این کار را برایش با کمترین تعداد حرکت انجام دهید.

ورودی🔗

ورودی تنها شامل یک خط است که در آن دو عدد طبیعی $a$ و $b$ با فاصله از هم آمده است. $4 \le a \le b \le 100\ 000$

خروجی🔗

در تنها خط خروجی در صورتی که شیر فرهاد می‌توانست عدد $a$ را با عدد $b$ برابر کند، کمترین تعداد حرکت لازم برای انجام این کار را چاپ کنید و در صورتی که نمی‌توان عدد $a$ را برابر $b$ کرد ‍‍‍‍-1 را در خروجی چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

4 24

خروجی نمونه ۱🔗

5

توضیح نمونه ۱: کمترین تعداد حرکت لازم برای رسیدن از عدد ۴ به ۲۴ برابر ۵ است.

$4 \rightarrow 6 \rightarrow 8 \rightarrow 12 \rightarrow 18 \rightarrow 24$

ورودی نمونه ۲🔗

8748 83462

خروجی نمونه ۲🔗

10

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

می‌دانیم شرکت‌های هرمی جایگاه ویژه‌ای در میان اهالی برره دارند.

جان نثار برره شرکت هرمی نثارکودات‌بی‌آر (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

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

می‌دانیم عدالت قضایی جایگاه ویژه‌ای در میان اهالی برره دارد.

کَیانوش، نظام و کیوون به ترتیب به جرم اخلال در نظم عمومی، کشیدن گرد نخود و زورگیری در ژاندارمری برره دست‌گیر شده‌اند.

نقشه‌ی زندان به شما داده شده است. زندان به شکل یک جدول $n \times m$ است و از سه سلول تشکیل شده است. سلول مجموعه‌ای از بلوک‌های خالی از جدول است که دو به دو به هم مسیر دارند (یک مسیر دنباله‌ای از خانه‌هاست که هر دوتای پشت سر هم با هم مجاورند، منظور از مجاورت در این سوال مجاورت ضلعی‌ست). بقیه‌ی زندان با بلوک‌های گلی پر شده است. این سه زندانی می‌خواهند با تخریب بلوک‌های گلی مجاور سلول‌های خود، هر ۳ سلول را به یک دیگر متصل کنند و با هم برای فرار نقشه بریزند. بدیهی‌ست وقتی یک بلوک گلی خراب شود ممکن است بلوک‌های گلی دیگری در دسترس قرار گیرد. کمترین تعداد بلوک‌های گلی‌ای که باید خراب کنند را بیابید.

ورودی🔗

در خط اول $n$ و $m$ داده شده است که به ترتیب تعداد سطرها و ستون‌های زندان ژاندارمری برره را نشان می‌دهد. در هر یک از $n$ سطر بعدی $m$ کاراکتر آمده است که X نشان‌دهنده‌ی بخشی از یک سلول و . نشان‌دهنده‌ی یک دیوار است. $1 \le n, m \le 50$

خروجی🔗

کمترین تعداد دیواری که باید خراب کنند را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

6 16
................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
..XXX....XXX....

خروجی نمونه ۱🔗

4

##توضیح نمونه ۱:

مطابق شکل زیر اگر بلوک‌های گلی‌ای که با * مشخص شده اند را خراب کنند تمامی سلول‌ها به هم متصل می‌شوند.

................
..XXXX....XXX...
...XXXX*...XX...
.XXXX..**..XXX..
...*....XXXXX...
..XXX....XXX....

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

می‌دانیم بازه بازی جایگاه ویژه‌ای در میان اهالی برره دارد.

شیرفرهاد و کَیانوش به دل طبیعت رفته بودند که تصمیم گرفتند بازه بازی کنند! در این بازی $n$ بازه وجود دارد و برنده کسی‌ست که اندازه‌ی بزرگترین مجموعه‌ی برره‌پسند را بیابد. یک مجموعه از بازه‌ها برره‌پسند است اگر و فقط اگر تمامی اعضای آن متمایز باشند و به ازای هر دو بازه مثل $a$ و $b$، یا $a$ درون $b$ قرار گیرد یا بلعکس.

شما به عنوان طرفدار شیرفرهاد اندازه‌ی بزرگترین مجموعه‌ی برره‌پسند را بیابید تا او برنده شود. دقت کنید اندازه‌ی یک مجموعه برابر تعداد اعضای آن است.

ورودی🔗

در خط اول $n$ آمده است. در هر یک از $n$ خط بعدی $a_i$، شروع بازه‌ی $i$اُم و $b_i$ پایان بازه‌ی $i$اُم داده شده است. $1 \le n \le 100\ 000$ $1 \le a_i \le b_i \le 1\ 000\ 000$ $a_i, b_i \in \mathbb{N}$

خروجی🔗

در تنها خط خروجی اندازه بزرگترین مجموعه‌ی برره‌پسند را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

3
3 4
2 5
1 6 

خروجی نمونه ۱🔗

3

ورودی نمونه ۲🔗

5
10 30
20 40
30 50
10 60
30 40 

خروجی نمونه ۲🔗

3

توضیح نمونه ۲:🔗

در این نمونه اندازه بزرگترین مجموعه‌ی برره پسند برابر ۳ است و بازه‌های ۳و۴و۵ (به ترتیب ورودی) این مجموعه را می‌سازند.

ورودی نمونه ۳🔗

6
1 4
1 5
1 6
1 7
2 5
3 5 

خروجی نمونه ۳🔗

5

توضیح نمونه ۳:🔗

در این نمونه تنها کافیست که اولین بازه (به ترتیب ورودی) را از مجموعه حذف کنیم، در نتیجه ۵ بازه دیگر بزرگترین مجموعه برره پسند را تشکیل می‌دهند.