چهار عدد

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

احمد در درس ریاضی ضعیف است و از شما می‌خواهد که به او در حل سوال های مدرسه اش کمک کنید. او تا به حال ٢ سوال از ٣ سوال تمرین‌ها را حل کرده ولی نمی‌تواند سوال آخر را حل کند. سوال آخر به این شرح است: چند عدد از ١ تا $n$ وجود دارد که بر حداقل یکی از چهار عدد $a$ ، $b$ ، $c$ ، $d$ بخش‌پذیر باشد؟

ورودی🔗

در خط اول ورودی، ۵ عدد آمده که اولی $n$ است و چهار عدد $a$ ، $b$ ، $c$ ، $d$ بعد از آن آمده‌اند.

$1 \leq n, a, b, c, d \leq 100 \, 000$

خروجی🔗

در تنها خط خروجی، تعداد اعداد طبیعی کوچک تر یا مساوی $n$ را که بر حداقل یکی از ۴ عدد داده شده بخش‌پذیر است بنویسید.

مثال🔗

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

24 2 3 4 5

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

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- پسرخاله به تازگی مدیر شرکت شده است. او قصد دارد تا فرهنگ اختلاس نکردن را در شرکت نهادینه کند. برای این کار او لیستی از کارمندانی که اختلاس کرده‌اند تهیه کرده است و قصد دارد کارمندی که بیشتر از همه اختلاس کرده است را معرفی کند تا باقی افراد درس عبرت گرفته و بیش از این اختلاس نکنند. اما از آنجایی که مقدار اختلاس ها نجومی است، او نمی تواند تشخیص دهد که کدام کارمند بیش تر از همه اختلاس کرده است. او از شما می‌خواهد برنامه ای بنویسید تا نام فردی که بیشتر از همه اختلاس کرده است را چاپ کند. # ورودی در خط اول ورودی، عدد $n$ (تعداد کارمندان) آمده است. در $n$ خط بعدی در هر خط به ترتیب نام خانوادگی اختلاس کننده و میزان اختلاس او آمده است. $$1 \leq n \leq 10^4$$ + نام خانوادگی هر نفر شامل حروف کوچک و بزرگ انگلیسی و حداکثر به طول ۵٠ است. + نام خانوادگی هیچ دو نفری برابر نیست. + میزان اختلاس هر نفر عددی مثبت و کوچک تر مساوی $10^9$ است. + ضمانت می‌شود که فقط یک نفر بیشترین اختلاس را کرده است. # خروجی در تنها خط خروجی، نام خانوادگی فردی که بیشتترین اختلاس را کرده است، چاپ کنید. # مثال‌ها ## ورودی نمونه ۱ ``` 2 Zamani 100 Makani 200 ``` ## خروجی نمونه ۱ ``` Makani ``` ## ورودی نمونه ۲ ``` 4 jalali 12 jamili 14 jalili 12 jamali 13 ``` ## خروجی نمونه ۲ ``` jamili ```

اختلاس

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

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

ورودی🔗

در خط اول ورودی، عدد $n$ (تعداد کارمندان) آمده است. در $n$ خط بعدی در هر خط به ترتیب نام خانوادگی اختلاس کننده و میزان اختلاس او آمده است.

$1 \leq n \leq 10^4$

نام خانوادگی هر نفر شامل حروف کوچک و بزرگ انگلیسی و حداکثر به طول ۵٠ است.
نام خانوادگی هیچ دو نفری برابر نیست.
میزان اختلاس هر نفر عددی مثبت و کوچک تر مساوی $10^9$ است.
ضمانت می‌شود که فقط یک نفر بیشترین اختلاس را کرده است.

خروجی🔗

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

مثال‌ها🔗

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

2
Zamani 100
Makani 200

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

Makani

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

4
jalali 12
jamili 14
jalili 12
jamali 13

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

jamili

ساده‌سازی رشته

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

علی که از ساده کردن رشته ها خسته شده است از شما برای ساده سازی رشته ها کمک می‌خواهد. علی هر بار یک رشته به طول $n$ می‌گیرد و آن را به شکل زیر ساده می‌کند:

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

به عنوان مثال، برای رشته‌ی dacbbcac ابتدا bb از رشته حذف شده و رشته برابر daccac می‌شود. سپس cc حذف شده و رشته برابر daac می‌شود. نهایتاً aa حذف شده و مقدار نهایی رشته dc می‌شود.

ورودی🔗

در خط اول ورودی، عدد $n$ (طول رشته) آمده است و در خط دوم ورودی، یک رشته به طول $n$ آمده است.

$1 \leq n \leq 100$

خروجی🔗

در تنها خط خروجی، رشته نهایی ساده شده را چاپ کنید.

مثال🔗

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

8
dacbbcac

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

dc

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- فصل جدید لیگ محلات به تازگی پایان یافته است و نتایج تمام بازی‌های آن مشخص شده است. این لیگ $n$ تیم دارد که اسم تیم $i$ام یک رشته‌ی تک حرفی شامل حرف کوچک $i$ام الفبای انگلیسی است. تیم‌ها دو به دو به مصاف هم رفته‌اند. در هر بازی در صورت تساوی دو تیم ١ امتیاز می‌گیرند و در غیر این صورت، تیم برنده ٣ امتیاز می‌گیرد و تیم بازنده امتیازی نمی‌گیرد. رتبه بندی نهایی تیم‌ها به این صورت است که تیم با امتیاز بالاتر رتبه‌ی بهتری می‌گیرد و در صورت تساوی امتیازها تیم با تفاضل گل (تعداد گل‌های زده منهای تعداد گل‌های خورده) بیشتر رتبه‌ی بهتری می‌گیرد. اگر هم امتیاز و هم تفاضل گل دو تیم برابر بود، تیم با اسم کوچک‌تر از نظر الفبایی رتبه‌ی بهتری می‌گیرد. در این سوال باید با ورودی گرفتن نتایج بازی‌ها، رتبه بندی نهایی را چاپ کنید. # ورودی در خط اول ورودی، عدد $n$ آمده است که نشان دهنده‌ی تعداد تیم‌هاست. در $n$ سطر بعدی در هر سطر $n$ عدد تک رقمی (بین ۰ تا ۹) آمده است که عدد $j$ام در سطر $i$ ($i \neq j$) به معنای تعداد گل‌هایی است که تیم $i$ام در بازی با تیم $j$ام وارد دروازه‌ی حریف کرده است. تضمین می‌شود همواره عدد $i$ام سطر $i$ برابر با صفر است. $$2 \leq n \leq 26$$ # خروجی در تنها خط خروجی، یک رشته‌ی $n$ حرفی چاپ کنید که حرف $i$ام آن اسم تیمی باشد که در رتبه بندی رتبه‌ی $i$ام را به دست آورده است. # مثال‌ها ## ورودی نمونه ۱ ``` 3 0 1 2 0 0 1 3 1 0 ``` ### خروجی نمونه ۱ ``` cab ``` ## ورودی نمونه ۲ ``` 3 0 1 1 2 0 3 1 2 0 ``` ### خروجی نمونه ۲ ``` bac ```

لیگ محلات

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

فصل جدید لیگ محلات به تازگی پایان یافته است و نتایج تمام بازی‌های آن مشخص شده است. این لیگ $n$ تیم دارد که اسم تیم $i$ ام یک رشته‌ی تک حرفی شامل حرف کوچک $i$ ام الفبای انگلیسی است. تیم‌ها دو به دو به مصاف هم رفته‌اند. در هر بازی در صورت تساوی دو تیم ١ امتیاز می‌گیرند و در غیر این صورت، تیم برنده ٣ امتیاز می‌گیرد و تیم بازنده امتیازی نمی‌گیرد. رتبه بندی نهایی تیم‌ها به این صورت است که تیم با امتیاز بالاتر رتبه‌ی بهتری می‌گیرد و در صورت تساوی امتیازها تیم با تفاضل گل (تعداد گل‌های زده منهای تعداد گل‌های خورده) بیشتر رتبه‌ی بهتری می‌گیرد. اگر هم امتیاز و هم تفاضل گل دو تیم برابر بود، تیم با اسم کوچک‌تر از نظر الفبایی رتبه‌ی بهتری می‌گیرد. در این سوال باید با ورودی گرفتن نتایج بازی‌ها، رتبه بندی نهایی را چاپ کنید.

ورودی🔗

در خط اول ورودی، عدد $n$ آمده است که نشان دهنده‌ی تعداد تیم‌هاست. در $n$ سطر بعدی در هر سطر $n$ عدد تک رقمی (بین ۰ تا ۹) آمده است که عدد $j$ ام در سطر $i$ ( $i \neq j$ ) به معنای تعداد گل‌هایی است که تیم $i$ ام در بازی با تیم $j$ ام وارد دروازه‌ی حریف کرده است. تضمین می‌شود همواره عدد $i$ ام سطر $i$ برابر با صفر است.

$2 \leq n \leq 26$

خروجی🔗

در تنها خط خروجی، یک رشته‌ی $n$ حرفی چاپ کنید که حرف $i$ ام آن اسم تیمی باشد که در رتبه بندی رتبه‌ی $i$ ام را به دست آورده است.

مثال‌ها🔗

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

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

cab

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

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

bac

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- آدرینا یک آدم گریز است. امروز در مسیر حرکت خود از خانه به حلقه‌ی آدم گریزان، مجبور است از پارکی پر از آدم بگذرد. پارک به شکل یک مستطیل $m \times n$ است و تعدادی آدم در آن در حال قدم زدن هستند. او می‌خواهد از ضلع بالایی آن به ضلع پایینی پارک برسد و طبق تجربیات گذشته خود نیز می‌داند که اگر در یک مسیر مستقیم حرکت کند، امیدِ ریاضی تعداد آدم هایی که می‌بیند کم‌تر است! در لحظه‌ای که آدرینا به پارک می‌رسد تعداد $k$ نفر آن‌جا هستند که هرکدام به یکی از جهت‌های بالا (`U`)، پایین (`D`)، چپ (`L`) یا راست (`R`) هستند و هر ثانیه یک خانه در جهت خود حرکت می‌کنند. آدرینا نیز هر ثانیه یک خانه به سمت پایین حرکت می‌کند و **تنها در صورتی یک آدم را می‌بیند که در یک زمان با او در یک خانه قرار گیرد.** آدرینا می‌خواهد بداند به ازای گذر از هر مسیر موجود، چندتا آدم می‌بیند که در نهایت کم آدم ترین مسیر را انتخاب کند. دقت کنید آدم‌ها هر لحظه به مسیر خود ادامه می‌دهند و در انتهای مسیر از پارک خارج می‌شوند. تضمین می‌شود در لحظه شروع در هیچ خانه‌ای دو آدم قرار ندارد و هم چنین هیچ آدمی در ضلع بالایی (محل شروع حرکت آدرینا) نیست. # ورودی در خط اول ورودی سه عدد $n$ و $m$ و $k$ آمده‌اند که به ترتیب طول و عرض پارک و تعداد آدم‌ها در لحظه ورود به پارک را نشان می‌دهد. در $n$ خط بعدی هر خط یک رشته متشکل از $m$ حرف می‌آید که پارک را نشان می‌دهند. در هر خانه یا کسی نیست که با نقطه نشان شده است و یا یک نفر در آن خانه قرار دارد که با یکی. از حروف `R`، `L`، `D`، `U` جهت حرکت آن را مشخص کرده‌ایم. $$2 \leq n, m \leq 1000$$ $$0 \leq k \leq (n - 1) \times m$$ # خروجی در تنها خط خروجی $m$ عدد با فاصله از هم چاپ شود که $i$امین آن تعداد آدم‌هایی است که آدرینا با شروع حرکت از خانه $i$ام سطر اول آن‌ها را می‌بیند. # مثال‌ها ## ورودی نمونه ۱ ``` 3 3 4 ... R.L R.U ``` ## خروجی نمونه ۱ ``` 0 2 2 ``` ## ورودی نمونه ۲ ``` 2 2 2 .. RL ``` ## خروجی نمونه ۲ ``` 1 1 ``` ## ورودی نمونه ۳ ``` 2 2 2 .. LR ``` ## خروجی نمونه ۳ ``` 0 0 ```

دموفوب

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

آدرینا یک آدم گریز است. امروز در مسیر حرکت خود از خانه به حلقه‌ی آدم گریزان، مجبور است از پارکی پر از آدم بگذرد. پارک به شکل یک مستطیل $m \times n$ است و تعدادی آدم در آن در حال قدم زدن هستند. او می‌خواهد از ضلع بالایی آن به ضلع پایینی پارک برسد و طبق تجربیات گذشته خود نیز می‌داند که اگر در یک مسیر مستقیم حرکت کند، امیدِ ریاضی تعداد آدم هایی که می‌بیند کم‌تر است!

در لحظه‌ای که آدرینا به پارک می‌رسد تعداد $k$ نفر آن‌جا هستند که هرکدام به یکی از جهت‌های بالا (U)، پایین (D)، چپ (L) یا راست (R) هستند و هر ثانیه یک خانه در جهت خود حرکت می‌کنند. آدرینا نیز هر ثانیه یک خانه به سمت پایین حرکت می‌کند و تنها در صورتی یک آدم را می‌بیند که در یک زمان با او در یک خانه قرار گیرد.

آدرینا می‌خواهد بداند به ازای گذر از هر مسیر موجود، چندتا آدم می‌بیند که در نهایت کم آدم ترین مسیر را انتخاب کند. دقت کنید آدم‌ها هر لحظه به مسیر خود ادامه می‌دهند و در انتهای مسیر از پارک خارج می‌شوند.

تضمین می‌شود در لحظه شروع در هیچ خانه‌ای دو آدم قرار ندارد و هم چنین هیچ آدمی در ضلع بالایی (محل شروع حرکت آدرینا) نیست.

ورودی🔗

در خط اول ورودی سه عدد $n$ و $m$ و $k$ آمده‌اند که به ترتیب طول و عرض پارک و تعداد آدم‌ها در لحظه ورود به پارک را نشان می‌دهد. در $n$ خط بعدی هر خط یک رشته متشکل از $m$ حرف می‌آید که پارک را نشان می‌دهند. در هر خانه یا کسی نیست که با نقطه نشان شده است و یا یک نفر در آن خانه قرار دارد که با یکی. از حروف R، L، D، U جهت حرکت آن را مشخص کرده‌ایم.

$2 \leq n, m \leq 1000$ $0 \leq k \leq (n - 1) \times m$

خروجی🔗

در تنها خط خروجی $m$ عدد با فاصله از هم چاپ شود که $i$ امین آن تعداد آدم‌هایی است که آدرینا با شروع حرکت از خانه $i$ ام سطر اول آن‌ها را می‌بیند.

مثال‌ها🔗

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

3 3 4
...
R.L
R.U

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

0 2 2

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

2 2 2
..
RL

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

1 1

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

2 2 2
..
LR

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

0 0

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- یک روز گرم تابستانی بچه‌ها تو ساحل مشغول ساخت برج های شنی هستند. تا پایان روز آن‌ها موفق به ساخت $n$ برج شنی در یک ردیف می‌شوند. آن‌ها برج‌ها را از چپ به راست با شماره های ١ تا $n$ شماره گذاری می‌کنند. ارتفاع برج $i$ام برابر $h_i$ است. در هنگام رفتن از ساحل نابغه متوجه می‌شود که برج‌ها به ترتیب ارتفاع نیستند و ظاهری زشت دارند. آن ها تصمیم می‌گیرند که ترتیب برج‌ها را به صورتی دربیاورند که برای هر $i$ بین $1$ تا $n - 1$ داشته باشیم $h_i \leq h_{i+1}$. نابغه الگوریتم زیر را برای مرتب‌سازی پیشنهاد می‌کند: + برج‌ها به بلوک‌هایی افراز شوند که هر بلوک شامل تعدادی برج متوالی باشد. هر بلوک حداقل شامل یک برج باشد. لزومی ندارد بلوک‌ها اندازه‌ی یکسانی داشته باشند. طبیعتاً هر برج متعلق به دقیقاً یک بلوک خواهد بود. + هر بلوک به صورت مستقل به صورت غیرنزولی مرتب سازی شود. بدیهی است اگر تنها یک بلوک در نظر بگیریم که شامل همه‌ی برج‌ها باشد، با الگوریتم بالا همه‌ی برج‌ها بصورت غیرنزولی مرتب می‌شوند. اما از آنجا که بچه‌ها می‌خواهد جلوی نابغه خودی نشان دهند، تصمیم گرفته‌اند با بیشترین تعداد بلوک این کار را انجام دهند. به بچه ها کمک کنید که تعداد ماکزیمم بلوک‌ها را محاسبه کنند. # ورودی در خط اول $n$ (تعداد برج‌ها) آمده است. در خط بعدی $n$ عدد که نشان دهنده ارتفاع برج‌ها ($h_i$ها) از چپ به راست هستند آمده است. $$1 \leq n \leq 10^6$$ $$1 \leq h_i \leq 10^9$$ # خروجی در تنها خط خروجی شما باید ماکزیمم تعداد بلوک‌ها را که منجر به مرتب‌سازی برج‌ها می‌شود را چاپ کنید. # مثال‌ها ## ورودی نمونه ۱ ``` 3 1 2 3 ``` ## خروجی نمونه ۱ ``` 3 ``` ## ورودی نمونه ۲ ``` 4 2 1 3 2 ``` ## خروجی نمونه ۲ ``` 2 ```

برج‌های شنی

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

یک روز گرم تابستانی بچه‌ها تو ساحل مشغول ساخت برج های شنی هستند. تا پایان روز آن‌ها موفق به ساخت $n$ برج شنی در یک ردیف می‌شوند. آن‌ها برج‌ها را از چپ به راست با شماره های ١ تا $n$ شماره گذاری می‌کنند. ارتفاع برج $i$ ام برابر $h_i$ است. در هنگام رفتن از ساحل نابغه متوجه می‌شود که برج‌ها به ترتیب ارتفاع نیستند و ظاهری زشت دارند. آن ها تصمیم می‌گیرند که ترتیب برج‌ها را به صورتی دربیاورند که برای هر $i$ بین $1$ تا $n - 1$ داشته باشیم $h_i \leq h_{i+1}$ .

نابغه الگوریتم زیر را برای مرتب‌سازی پیشنهاد می‌کند:

برج‌ها به بلوک‌هایی افراز شوند که هر بلوک شامل تعدادی برج متوالی باشد. هر بلوک حداقل شامل یک برج باشد. لزومی ندارد بلوک‌ها اندازه‌ی یکسانی داشته باشند. طبیعتاً هر برج متعلق به دقیقاً یک بلوک خواهد بود.
هر بلوک به صورت مستقل به صورت غیرنزولی مرتب سازی شود.

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

به بچه ها کمک کنید که تعداد ماکزیمم بلوک‌ها را محاسبه کنند.

ورودی🔗

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

$1 \leq n \leq 10^6$ $1 \leq h_i \leq 10^9$

خروجی🔗

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

مثال‌ها🔗

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

3
1 2 3

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

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

4
2 1 3 2

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

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- علی که حوصله اش از قطعی اینترنت سر رفته، برای خودش یک بازی یک نفره‌ی بسیار سرگرم کننده طرح کرده است. در این بازی، او ابتدا به یک سایت تولید عدد تصادفی ملی می‌رود، و یک عدد تصادفی مثل $n$ دریافت می‌کند. حال بازی شروع می‌شود و در هر مرحله او یک عدد طبیعی بزرگتر از ١ مثل $x$ را انتخاب می‌کند به طوری که $n$ بر $x$ بخش پذیر باشد، و $n$ را با $\frac{x}{n}$ جایگزین می‌کند. او این کار را تا زمانی که $n \neq 1$ است ادامه می‌دهد. علی دوست دارد تعداد مراحل بازی بیشینه شود تا حوصله اش کمتر سر رود. می‌دانیم عدد $n$ به شکل $\frac{a!}{b!}$ قابل نمایش است که در آن $a$ و $b$ اعدادی صحیح و مثبت هستند. با توجه به هیجان انگیز بودن بازیِ علی، دوستان او هم تصمیم گرفته‌اند این بازی را انجام بدهند. شما باید با دریافت تعدادی $n$ از ورودی، به ازای هر $n$ حداکثر تعداد مراحلی که یک نفر می‌تواند بازی را ادامه دهد را در خروجی چاپ کند. # ورودی در ورودی ابتدا عدد $k$ می‌آید که نشان دهنده‌ی تعداد بازی‌هاست. سپس در هر یک از $k$ خط بعدی دو عدد $a$ و $b$ می‌آیند، که مقادیر خط $i$ام مربوط به بازی $i$ام هستند. $$1 \leq k \leq 10^5$$ $$1 \leq b \leq a \leq 10^6$$ # خروجی شما باید $k$ خط خروجی تولید کنید که در خط $i$ام حداکثر تعداد مراحلی که بازی $i$ام می‌تواند طول بکشد نوشته شده باشد. # مثال‌ها ## ورودی نمونه ۱ ``` 2 3 1 6 3 ``` ## خروجی نمونه ۱ ``` 2 5 ```

بازی با اعداد

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

علی که حوصله اش از قطعی اینترنت سر رفته، برای خودش یک بازی یک نفره‌ی بسیار سرگرم کننده طرح کرده است. در این بازی، او ابتدا به یک سایت تولید عدد تصادفی ملی می‌رود، و یک عدد تصادفی مثل $n$ دریافت می‌کند. حال بازی شروع می‌شود و در هر مرحله او یک عدد طبیعی بزرگتر از ١ مثل $x$ را انتخاب می‌کند به طوری که $n$ بر $x$ بخش پذیر باشد، و $n$ را با $\frac{x}{n}$ جایگزین می‌کند. او این کار را تا زمانی که $n \neq 1$ است ادامه می‌دهد. علی دوست دارد تعداد مراحل بازی بیشینه شود تا حوصله اش کمتر سر رود. می‌دانیم عدد $n$ به شکل $\frac{a!}{b!}$ قابل نمایش است که در آن $a$ و $b$ اعدادی صحیح و مثبت هستند. با توجه به هیجان انگیز بودن بازیِ علی، دوستان او هم تصمیم گرفته‌اند این بازی را انجام بدهند. شما باید با دریافت تعدادی $n$ از ورودی، به ازای هر $n$ حداکثر تعداد مراحلی که یک نفر می‌تواند بازی را ادامه دهد را در خروجی چاپ کند.

ورودی🔗

در ورودی ابتدا عدد $k$ می‌آید که نشان دهنده‌ی تعداد بازی‌هاست. سپس در هر یک از $k$ خط بعدی دو عدد $a$ و $b$ می‌آیند، که مقادیر خط $i$ ام مربوط به بازی $i$ ام هستند.

$1 \leq k \leq 10^5$ $1 \leq b \leq a \leq 10^6$

خروجی🔗

شما باید $k$ خط خروجی تولید کنید که در خط $i$ ام حداکثر تعداد مراحلی که بازی $i$ ام می‌تواند طول بکشد نوشته شده باشد.

مثال‌ها🔗

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

2
3 1
6 3

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

2
5

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- اخیرا دولت پشمکستان با کسری بودجه‌ی شدیدی روبرو شده است. به همین علت تصمیم گرفته که جاده‌های کشور را به حراج بگذارد. این طرح به این صورت است که دولت با تعدادی شرکت خصوصی قرارداد می‌بندد و هرکدام از جاده‌ها را به یکی از شرکت‌ها واگذار می‌کند. هر شرکت مسئولیت نگهداری تعدادی از جاده‌ها را بر عهده می‌گیرد و از طریق گرفتن عوارض از کسانی که از آن جاده‌ها عبور می‌کنند، درآمدزایی می‌کند. پشمکستان بر خلاف سایر کشورها، دو پایتخت دارد که روزانه افراد زیادی در حال رفت وآمد بین این دو پایتخت هستند. هر شرکت تنها در صورتی با دولت قرارداد می‌بندد که درآمدزایی‌اش از کسانی که میان دو پایتخت سفر می‌کنند، تضمین شده باشد. به عبارت دیگر، دولت باید به گونه‌ای جاده‌ها را به هر شرکت اختصاص دهد که هر فرد مجبور باشد برای سفر از یکی از پایتخت ها به دیگری، حداقل از یکی از جاده‌های متعلق به آن شرکت عبور کند. دولت قصد دارد تا با بیشترین تعداد شرکت ممکن قرارداد ببندد تا سود خود از این طرح را بیشینه کند. برای کمک به دولت حداکثر تعداد شرکت ممکن برای قرارداد را اعلام کنید. # ورودی در خط اول ورودی، دو عدد $n$ (تعداد شهرهای پشمکستان) و $m$ (تعداد جاده های پشمکستان) آمده است. $$1 \leq n, m \leq 10^5$$ در خط دوم، دو عدد $s$ و $t$ آمده‌اند که شماره‌ی پایتخت‌های پشمکستان هستند. (شهر های پشمکستان از ١ تا $n$ شماره‌گذاری شده‌اند.) $$1 \leq s, t \leq n$$ در هرکدام از $m$ خط بعدی، دو عدد $a$ و $b$ آمده است. به این معنی که جاده‌ای دو طرفه میان شهرهای $a$ و $b$ وجود دارد. $$1 \leq a, b \leq n$$ # خروجی در تنها خط خروجی، حداکثر تعداد شرکتی را چاپ کنید که دولت می‌تواند با آن‌ها قرارداد ببندد. # مثال‌ها ## ورودی نمونه ۱ ``` 4 4 1 4 1 2 1 3 2 4 3 4 ``` ## خروجی نمونه ۱ ``` 2 ```

جاده‌فروشی

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

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

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

دولت قصد دارد تا با بیشترین تعداد شرکت ممکن قرارداد ببندد تا سود خود از این طرح را بیشینه کند. برای کمک به دولت حداکثر تعداد شرکت ممکن برای قرارداد را اعلام کنید.

ورودی🔗

در خط اول ورودی، دو عدد $n$ (تعداد شهرهای پشمکستان) و $m$ (تعداد جاده های پشمکستان) آمده است.

$1 \leq n, m \leq 10^5$

در خط دوم، دو عدد $s$ و $t$ آمده‌اند که شماره‌ی پایتخت‌های پشمکستان هستند. (شهر های پشمکستان از ١ تا $n$ شماره‌گذاری شده‌اند.)

$1 \leq s, t \leq n$

در هرکدام از $m$ خط بعدی، دو عدد $a$ و $b$ آمده است. به این معنی که جاده‌ای دو طرفه میان شهرهای $a$ و $b$ وجود دارد.

$1 \leq a, b \leq n$

خروجی🔗

در تنها خط خروجی، حداکثر تعداد شرکتی را چاپ کنید که دولت می‌تواند با آن‌ها قرارداد ببندد.

مثال‌ها🔗

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

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

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- مدتی پیش سینا به بیماری سخت «بینتی» دچار شد. او پس از مدت‌ها مبارزه، موفق شد بیماری را شکست داده و سلامتی خود را به دست آورد. پس از این اتفاق او تصمیم گرفت برای کمک به افراد مبتلا به بینتی پیش قدم شده و به جمع آوری کمک های مالی بپردازد. اما در حین آماده‌سازی متوجه شد بیماری‌های دیگری نیز وجود دارند که فرآیند درمان آن‌ها بسیار هزینه بر است. به همین دلیل او تصمیم به ایجاد $n$ موسسه‌ی خیریه گرفت که هر کدام برای کمک به افراد مبتلا به یک بیماری خاص فعالیت کنند. علاوه بر این، سینا ساختاری برای این موسسسه‌ها ایجاد کرد تا کمک‌های مالی منحصر به یک بیماری نشوند. در این ساختار برای موسسه‌ی $i$ام، محدودیت مالی $a_i$ تومان در سال در نظر گرفته شده است. به این ترتیب اگر مجموع دریافتی موسسه‌ی $i$ ام از $a_i$ فراتر برود، مبلغ اضافه تا پایان سال به صورت خودکار به موسسه‌ی $i + 1$ ام منتقل می‌شود. در صورتی که دریافتی سال جاری موسسه‌ی $i + 1$ ام نیز به محدودیت مالی آن رسیده باشد، این روند ادامه پیدا می‌کند و مبلغ اضافه به موسسسه‌ی $i + 2$ ام منتقل خواهد شد. اگر پس از اتمام محدودیت مالی موسسه‌ی $n$ ام کمکی به آن برسد، مبلغ دریافت شده به صورت جداگانه برای ایجاد موسسه های جدید ذخیره می‌شود. متاسفانه با توجه به ساختار نوین این موسسه‌ها ابزار مناسبی برای رسیدگی به امور حساب داری آن وجود ندارد. بنابراین سینا از شما کمک خواسته است که یک برنامه‌ی حساب داری برای موسسه‌هایش پیاده سازی کنید. به طور دقیق‌تر برنامه‌ی شما باید به دو نوع درخواست پاسخ دهد: + ثبت کمک مردمی به مبلغ $x$ تومان به موسسه‌ی $p$ام. + اعلام موجودی موسسه‌ی $k$ ام. به سینا کمک کنید تا تراکنش‌های مالی موسسه‌هایش را مدیریت کند. # ورودی در خط اول دو عدد $n$ و $q$ با یک فاصله آمده‌اند که به ترتیب تعداد موسسه‌های خیریه و تعداد درخواست‌ها را نشان می‌دهند. $$1 \leq n, q \leq 2 \times 10^5$$ در خط دوم $n$ عددهای $a_1, a_3, \dots, a_n\,$ با فاصله آمده‌اند که محدودیت مالی موسسه‌ها را نشان می‌دهند. در $i$ امین خط از $q$ خط بعدی ابتدا یک عدد $t_i$ آمده است که نوع درخواست را نشان می‌دهد. اگر $t_i$ یک باشد، پس از آن دو عدد دیگر $x_i$ و $p_i$ آمده‌اند که به ترتیب موسسه‌ی هدف و میزان کمک در این تراکنش را نشان می‌دهند. در غیر این صورت $t_i$ برابر دو است و بعد از آن یک عدد $k_i$ آمده است که شماره‌ی موسسه‌ی خیریه‌ای است که موجودی آن درخواست شده است. $$1 \leq p_i, k_i \leq n$$ $$1 \leq a_i, x_i \leq 10^9$$ # خروجی در خروجی به ازای هر درخواست از نوع دو یک خط چاپ کنید که موجودی موسسه‌ی درخواست شده در آن آماده است. # مثال ## ورودی نمونه ۱ ``` 3 6 15 20 18 1 1 22 2 2 1 1 16 1 3 12 2 2 2 3 ``` ## خروجی نمونه ۱ ``` 7 20 ٓ15 ```

خیریه

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

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

اما در حین آماده‌سازی متوجه شد بیماری‌های دیگری نیز وجود دارند که فرآیند درمان آن‌ها بسیار هزینه بر است. به همین دلیل او تصمیم به ایجاد $n$ موسسه‌ی خیریه گرفت که هر کدام برای کمک به افراد مبتلا به یک بیماری خاص فعالیت کنند. علاوه بر این، سینا ساختاری برای این موسسسه‌ها ایجاد کرد تا کمک‌های مالی منحصر به یک بیماری نشوند. در این ساختار برای موسسه‌ی $i$ ام، محدودیت مالی $a_i$ تومان در سال در نظر گرفته شده است. به این ترتیب اگر مجموع دریافتی موسسه‌ی $i$ ام از $a_i$ فراتر برود، مبلغ اضافه تا پایان سال به صورت خودکار به موسسه‌ی $i + 1$ ام منتقل می‌شود. در صورتی که دریافتی سال جاری موسسه‌ی $i + 1$ ام نیز به محدودیت مالی آن رسیده باشد، این روند ادامه پیدا می‌کند و مبلغ اضافه به موسسسه‌ی $i + 2$ ام منتقل خواهد شد. اگر پس از اتمام محدودیت مالی موسسه‌ی $n$ ام کمکی به آن برسد، مبلغ دریافت شده به صورت جداگانه برای ایجاد موسسه های جدید ذخیره می‌شود.

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

ثبت کمک مردمی به مبلغ $x$ تومان به موسسه‌ی $p$ ام.
اعلام موجودی موسسه‌ی $k$ ام.

به سینا کمک کنید تا تراکنش‌های مالی موسسه‌هایش را مدیریت کند.

ورودی🔗

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

$1 \leq n, q \leq 2 \times 10^5$

در خط دوم $n$ عددهای $a_1, a_3, \dots, a_n\,$ با فاصله آمده‌اند که محدودیت مالی موسسه‌ها را نشان می‌دهند. در $i$ امین خط از $q$ خط بعدی ابتدا یک عدد $t_i$ آمده است که نوع درخواست را نشان می‌دهد. اگر $t_i$ یک باشد، پس از آن دو عدد دیگر $x_i$ و $p_i$ آمده‌اند که به ترتیب موسسه‌ی هدف و میزان کمک در این تراکنش را نشان می‌دهند. در غیر این صورت $t_i$ برابر دو است و بعد از آن یک عدد $k_i$ آمده است که شماره‌ی موسسه‌ی خیریه‌ای است که موجودی آن درخواست شده است.

$1 \leq p_i, k_i \leq n$ $1 \leq a_i, x_i \leq 10^9$

خروجی🔗

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

مثال🔗

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

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

7
20
ٓ15

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- فامیل دور به مغازه‌ی شکلات فروشی رفته تا برای فرزندانش شکلات بخرد. در مغازه شکلات فروشی $n$ بسته‌ی شکلات وجود دارد که بسته $i$ام $a_i$ شکلات دارد (یک بسته ممکن است هیچ شکلاتی نداشته باشد.) بچه‌های فامیل دور که تعداد آن‌ها $m$ است با دیدن بسته‌های شکلات خوشحال می‌شوند. فامیل دور می‌داند برای آنکه دعوایی میان بچه‌ها پیش نیاید باید به هر نفر تعداد یکسانی شکلات برسد. در ضمن او می‌داند باید کل یک بسته شکلات را بخرد و نمی‌تواند بخشی از یک بسته را بخرد. او باید حداقل یک بسته شکلات را خریداری کند تا بچه‌ها با دیدن بسته‌های شکلات خوشحال شوند. فامیل دور می‌خواهد بداند آیا می‌تواند تعدادی از بسته‌ها را انتخاب کند که هم بچه‌ها خوشحال شوند و هم دعوایی میان آن‌ها پیش نیاید. # ورودی در خط اول ورودی، دو عدد $n$ (تعداد بسته‌های شکلات) و $m$ (تعداد بچه‌ها) آمده است. در خط دوم $n$ عدد آمده است که عدد $i$ام نشان دهنده‌ی تعداد شکلات‌های بسته $i$ام است. $$1 \leq n \leq 5 \times 10^5$$$$2 \leq m \leq 5 \times 10^3$$ $$0 \leq a_i \leq 10^9$$ # خروجی در تنها خط خروجی، اگر فامیل دور می‌تواند با شرایط مورد نظرش شکلات بخرد `YES` و در غیر این صورت `NO` چاپ کنید. # مثال‌ها ## ورودی نمونه ۱ ``` 3 7 1 3 4 ``` ## خروجی نمونه ۱ ``` YES ``` ## ورودی نمونه ۲ ``` 3 7 1 3 5 ``` ## خروجی نمونه ۲ ``` NO ``` ## ورودی نمونه ۳ ``` 1 101 0 ``` ## خروجی نمونه ۳ ``` YES ```

شکلات فروشی

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

فامیل دور به مغازه‌ی شکلات فروشی رفته تا برای فرزندانش شکلات بخرد. در مغازه شکلات فروشی $n$ بسته‌ی شکلات وجود دارد که بسته $i$ ام $a_i$ شکلات دارد (یک بسته ممکن است هیچ شکلاتی نداشته باشد.) بچه‌های فامیل دور که تعداد آن‌ها $m$ است با دیدن بسته‌های شکلات خوشحال می‌شوند. فامیل دور می‌داند برای آنکه دعوایی میان بچه‌ها پیش نیاید باید به هر نفر تعداد یکسانی شکلات برسد. در ضمن او می‌داند باید کل یک بسته شکلات را بخرد و نمی‌تواند بخشی از یک بسته را بخرد. او باید حداقل یک بسته شکلات را خریداری کند تا بچه‌ها با دیدن بسته‌های شکلات خوشحال شوند. فامیل دور می‌خواهد بداند آیا می‌تواند تعدادی از بسته‌ها را انتخاب کند که هم بچه‌ها خوشحال شوند و هم دعوایی میان آن‌ها پیش نیاید.

ورودی🔗

در خط اول ورودی، دو عدد $n$ (تعداد بسته‌های شکلات) و $m$ (تعداد بچه‌ها) آمده است. در خط دوم $n$ عدد آمده است که عدد $i$ ام نشان دهنده‌ی تعداد شکلات‌های بسته $i$ ام است.

$1 \leq n \leq 5 \times 10^5$ $2 \leq m \leq 5 \times 10^3$ $0 \leq a_i \leq 10^9$

خروجی🔗

در تنها خط خروجی، اگر فامیل دور می‌تواند با شرایط مورد نظرش شکلات بخرد YES و در غیر این صورت NO چاپ کنید.

مثال‌ها🔗

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

3 7
1 3 4

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

YES

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

3 7
1 3 5

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

NO

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

1 101
0

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

YES