+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- فروت که شکلات دوست داره وارد واندرلند (همون جایی که آلیس رفته بود) می‌شه و از همون اول چشمش میوفته به ردیفی از شکلات‌ها به طول $n$. فروت میاد همه‌ی شکلات‌ها رو بخوره که ناگهان چشایر (همون گربه‌ای که توی دود میومد و می‌رفت)‌ ظاهر می‌شه و به فروت میگه فقط می‌تونی شکلات‌ها رو در قالب بازه‌های متوالی به طول $k$ بخوری! فروت که جا خورده از شما کمک می‌خواد تا بهش بگید می‌تونه همه‌ی شکلات‌ها رو بخوره یا نه! |![](https://quera.org/qbox/view/lJfDHH7Uik/A.jpg)| |:--------:| | شنیدم شکلات دوست داری | # ورودی ورودی تنها شامل یک خط است که در آن دو عدد طبیعی $n$ و $k$ با فاصله از هم آمده‌اند. $$1 \le n, k \le 10^9$$ # خروجی خروجی شما باید شامل یک خط باشد. اگر فروت می‌تونه همه‌ی شکلات‌ها رو بخوره چاپ کنید `YES` در غیر این صورت چاپ کنید `NO`. # مثال ## ورودی نمونه ۱ ``` 10 10 ``` ## خروجی نمونه ۱ ``` YES ``` فروت در حرکتی انتحاری کل شکلات‌ها رو درجا می‌خوره. ## ورودی نمونه ۲ ``` 12 4 ``` ## خروجی نمونه ۲ ``` YES ``` یکی از روش‌ها: اول شکلات‌های ۵ و ۶ و ۷ و ۸ بعد شکلات های ۹ و ۱۰ و ۱۱ و ۱۲ و سپس ۱ و ۲ و ۳ و ۴. ## ورودی نمونه ۳ ``` 100 52 ``` ## خروجی نمونه ۳ ``` NO ``` فروت در حرکت اول اگر ۵۲ تا شکلات رو هر جوری بخوره ۴۸ تا شکلات باقی می‌مونه که با هیچ حرکتی نمی‌تونه بخورتشون. چشایر بعد از این تست رو به فروت کرد و گفت دیدی دوستات هم نمی‌تونن کمکت کنن.

شکلات

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

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

فروت میاد همه‌ی شکلات‌ها رو بخوره که ناگهان چشایر (همون گربه‌ای که توی دود میومد و می‌رفت)‌ ظاهر می‌شه و به فروت میگه فقط می‌تونی شکلات‌ها رو در قالب بازه‌های متوالی به طول $k$ بخوری!

فروت که جا خورده از شما کمک می‌خواد تا بهش بگید می‌تونه همه‌ی شکلات‌ها رو بخوره یا نه!


شنیدم شکلات دوست داری

ورودی🔗

ورودی تنها شامل یک خط است که در آن دو عدد طبیعی $n$ و $k$ با فاصله از هم آمده‌اند. $1 \le n, k \le 10^9$

خروجی🔗

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

مثال🔗

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

10 10

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

YES

فروت در حرکتی انتحاری کل شکلات‌ها رو درجا می‌خوره.

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

12 4

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

YES

یکی از روش‌ها: اول شکلات‌های ۵ و ۶ و ۷ و ۸ بعد شکلات های ۹ و ۱۰ و ۱۱ و ۱۲ و سپس ۱ و ۲ و ۳ و ۴.

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

100 52

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

NO

فروت در حرکت اول اگر ۵۲ تا شکلات رو هر جوری بخوره ۴۸ تا شکلات باقی می‌مونه که با هیچ حرکتی نمی‌تونه بخورتشون.

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

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- فروت مُرد (چشایر خوردش و غیب شد! به همین دلیل اطلاعات دیگری در دسترس نیست). پارسا که دید فروت از دور خارج شده کلیدهای فروت رو برداشت و یکی از درهای واندرلند رو باز کرد که ناگهان وارد محفل شعر به صرف چای شد. همین که پارسا از در وارد شد‌ رادمان یه سینی چایی $n \times n$ بهش داد و گفت قند بریز داخل چایی ها. از اونجایی که پارسا عدالت طلبه می‌خواد این قندها رو طوری پخش کنه که شرایط زیر برقرار باشه: ۱- تعداد قندهای ریخته شده در چایی‌های هر سطر و هر ستون از سینی دقیقا $k$ باشد. ۲- اختلاف بیشترین و کمترین میزان قند ریخته شده در هر سطر و در هر ستون کمترین مقدار ممکن باشد. |![](https://quera.org/qbox/view/eytOfZxzCZ/B.jpg)| |:--------:| | تا وقتی چایی هست چرا قهوه! | # ورودی ورودی تنها شامل یک خط است که در آن دو عدد طبیعی $n$ و $k$ با فاصله از هم آمده‌اند. $$1 \le n \le 500$$ $$1 \le k \le 10^9$$ # خروجی خروجی شما باید یک جدول $n$ در $n$ باشد که نشان دهنده‌ی تعداد قندهای داخل چایی‌ها باشد و همچنین جدول شرایط مسئله را داشته باشد. # مثال ## ورودی نمونه ۱ ``` 2 9 ``` ## خروجی نمونه ۱ ``` 4 5 5 4 ``` ## ورودی نمونه ۲ ``` 5 6 ``` ## خروجی نمونه ۲ ``` 1 1 1 1 2 1 2 1 1 1 1 1 2 1 1 1 1 1 2 1 2 1 1 1 1 ``` ## ورودی نمونه ۳ ``` 3 6 ``` ## خروجی نمونه ۳ ``` 2 2 2 2 2 2 2 2 2 ```

عدالت پارسا

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

فروت مُرد (چشایر خوردش و غیب شد! به همین دلیل اطلاعات دیگری در دسترس نیست).

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

همین که پارسا از در وارد شد‌ رادمان یه سینی چایی $n \times n$ بهش داد و گفت قند بریز داخل چایی ها. از اونجایی که پارسا عدالت طلبه می‌خواد این قندها رو طوری پخش کنه که شرایط زیر برقرار باشه:

۱- تعداد قندهای ریخته شده در چایی‌های هر سطر و هر ستون از سینی دقیقا $k$ باشد.
۲- اختلاف بیشترین و کمترین میزان قند ریخته شده در هر سطر و در هر ستون کمترین مقدار ممکن باشد.


تا وقتی چایی هست چرا قهوه!

ورودی🔗

ورودی تنها شامل یک خط است که در آن دو عدد طبیعی $n$ و $k$ با فاصله از هم آمده‌اند. $1 \le n \le 500$ $1 \le k \le 10^9$

خروجی🔗

خروجی شما باید یک جدول $n$ در $n$ باشد که نشان دهنده‌ی تعداد قندهای داخل چایی‌ها باشد و همچنین جدول شرایط مسئله را داشته باشد.

مثال🔗

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

2 9

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

4 5
5 4

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

5 6

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

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

3 6

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

2 2 2
2 2 2
2 2 2

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- پارسا مُرد (از منابع موثق خبر رسیده که به دلیل ناعدالتی‌های زیاد در واندرلند، کل چایی‌های سوال قبلی رو خورده و ترکیده). محمد که به دنبال گرفتن انتقام بود، اولین چیزی که توجهش رو جلب کرد وصیت نامه‌ی پارسا بود که با این شعر شروع می‌شد: عدالت آن بود ای مرد آگاه / که برداری وجود خویش از راه واندرلند و زمین مبادلات مالی زیادی با هم دارند و یکی از این نوع مبادلات شامل سه نوع شکلات می‌باشد. شکلات قهوه‌ای، شکلات سفید و شکلات جادویی که قیمت هر کدام در بازار واندرلند به تریب $a$، $b$، $$c دلار است اما در زمین قیمت‌ها به ترتیب، $A$, $B$, $C$ دلار است. همچنین به دلیل اصل عرضه و تقاضا‌، به ازای هر شکلات قهوه‌ای که خریده می‌شود، $X$ دلار به قیمت آن اضافه خواهد شد و به ازای هر شکلات سفید که خریده می‌شود، $Y$ دلار به قیمت آن اضافه می‌شود. دقت کنید که شکلات جادویی به دلیل جادویی بودن از این اصل پیروی نمی‌کند و حداکثر $T$ عدد از این نوع موجود است اما برای شکلات قهوه‌ای و سفید محدودیت خرید نداریم. حال محمد می‌خواهد $P$ عدد شکلات در واندرلند بخرد و در زمین بفروشد و این وظیفه‌ی شماست که بیشترین سود ممکن را برای او محاسبه کنید (دقت کنید ممکن است محمد ضرر نیز بکند که در این صورت، کمترین مقدار ضرر مطلوب است). |![](https://s6.uupload.ir/files/f7f506fc95651386d081a07445d43659_omp7.jpg)| |:--------:| |مارس هستم تا بیشتر از این نابود نشدم کمک کنید| # ورودی در تنها خط ورودی به ترتیب $c, b, a$ سپس $C, B, A$ و سپس دو عدد $Y, X$ و در آخر دو عدد $P, T$ آمده‌اند. $$1 \le a, b, c, A, B, C, X, Y, T, P\le 10^6$$ # خروجی در تنها خط خروجی بیشترین سود ممکن محمد را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 1 1 1 20 30 40 4 6 2 10 ``` ## خروجی نمونه ۱ ``` 210 ``` ۴ تا از شکلات قهوه‌ای و ۴ تا از شکلات سفید و ۲ تا هم شکلات جادویی می‌خرد. ## ورودی نمونه ۲ ``` 3 1 4 18 72 34 2 1 10 9 ``` ## خروجی نمونه ۲ ``` 603 ``` ۹ تا از شکلات سفید می‌خرد و در زمین می‌فروشد.

انتقام به سبک محمد

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

پارسا مُرد (از منابع موثق خبر رسیده که به دلیل ناعدالتی‌های زیاد در واندرلند، کل چایی‌های سوال قبلی رو خورده و ترکیده).

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

عدالت آن بود ای مرد آگاه / که برداری وجود خویش از راه

واندرلند و زمین مبادلات مالی زیادی با هم دارند و یکی از این نوع مبادلات شامل سه نوع شکلات می‌باشد. شکلات قهوه‌ای، شکلات سفید و شکلات جادویی که قیمت هر کدام در بازار واندرلند به تریب $a$ ، $b$ ، c دلار است اما در زمین قیمت‌ها به ترتیب، $A$ , $B$ , $C$ دلار است. همچنین به دلیل اصل عرضه و تقاضا‌، به ازای هر شکلات قهوه‌ای که خریده می‌شود، $X$ دلار به قیمت آن اضافه خواهد شد و به ازای هر شکلات سفید که خریده می‌شود، $Y$ دلار به قیمت آن اضافه می‌شود. دقت کنید که شکلات جادویی به دلیل جادویی بودن از این اصل پیروی نمی‌کند و حداکثر $T$ عدد از این نوع موجود است اما برای شکلات قهوه‌ای و سفید محدودیت خرید نداریم.

حال محمد می‌خواهد $P$ عدد شکلات در واندرلند بخرد و در زمین بفروشد و این وظیفه‌ی شماست که بیشترین سود ممکن را برای او محاسبه کنید (دقت کنید ممکن است محمد ضرر نیز بکند که در این صورت، کمترین مقدار ضرر مطلوب است).


مارس هستم تا بیشتر از این نابود نشدم کمک کنید

ورودی🔗

در تنها خط ورودی به ترتیب $c, b, a$ سپس $C, B, A$ و سپس دو عدد $Y, X$ و در آخر دو عدد $P, T$ آمده‌اند. $1 \le a, b, c, A, B, C, X, Y, T, P\le 10^6$

خروجی🔗

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

مثال🔗

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

1 1 1 20 30 40 4 6 2 10

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

۴ تا از شکلات قهوه‌ای و ۴ تا از شکلات سفید و ۲ تا هم شکلات جادویی می‌خرد.

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

3 1 4 18 72 34 2 1 10 9

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

۹ تا از شکلات سفید می‌خرد و در زمین می‌فروشد.

+ محدودیت زمان: ۴ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- محمد مُرد (محمد پس از انتقام خون پارسا به کتاب‌های صادق هدایت روی آورد و پس از مدتی به هیچ رسید "دنیا همه هیچ و اهل دنیا همه هیچ! / ای هیچ برای هیچ بر هیچ مپیچ." و سپس در روز ۹/۱۵ ...). رومینا وضعیت رو که دید گفت خودم میرم دنبال آلیس پیداش می‌کنم. اما امان از کرونا. کرونا باعث شده بود آلیس افسردگی بگیره و خودش رو توی اتاق سحر آمیز حبث کنه. رومینا می‌خواست آلیس رو پیدا کنه و از کنج تنهایی درش بیاره که دستگیره‌ی در گفت برای باز شدن باید باید مسئله‌ی زیر را حل کنی! یک رشته به طول $n$ شامل کاراکترهای $[ , ] , (, )$ داریم. تعداد براکت گذاری‌های معتبر به طول $k$ با حذف هیچ یا تعدادی از کاراکترهای این رشته را می‌خواهیم. رشته‌ی $S$ یک براکت گذاری معتبر است اگر از کنار هم گذاری دو براکت گذاری معتبر $T, F$ به صورت $TF$ یا از یک براکت گذاری معتبر $T$ به صورت $[T]$ یا $(T)$ به دست آید. دقت کنید که رشته‌های مقابل براکت گذاری‌های معتبری هستند: $[ ( ) ] , [ ], ( ) , [ ( [ ] ) ( ) ]$ و رشته‌های مقابل نامعتبرند :‌ $[ ( ] ) , ( ]$ |![](https://quera.org/qbox/view/aDfTwQcuDx/D.jpg)| |:--------:| | میخوای دست به دماغم بزنی باید سوال جواب بدی :/ | # ورودی ورودی شامل دو خط است که در خط اول دو عدد طبیعی $n$ و $k$ با فاصله از هم آمده‌اند. $$1 \le n \le 10^5$$ $$1 \le k \le 16$$ در خط دوم یک رشته به طول $n$ از کاراکتر‌های $[ , ] , (, )$ آمده است. # خروجی در یک خط باقی مانده‌ی تعداد براکت گذاری‌های معتبر به طول $k$ را بر $10^9 + 7$ چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 6 2 ((())) ``` ## خروجی نمونه ۱ ``` 9 ``` به ۳ حالت می‌توانیم پرانتز باز را انتخاب کنیم و به ۳ حالت پرانتز بسته را، در نتیجه ۹ حالت داریم. ## ورودی نمونه ۲ ``` 6 2 ([()]) ``` ## خروجی نمونه ۲ ``` 5 ``` اگر دو کاراکتر انتخاب شده پرانتز باشند ۴ حالت داریم در غیر این صورت تنها یک حالت داریم. پس جواب نهایی ۵ می‌شود.

آلیس افسرده می‌شود

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

محمد مُرد (محمد پس از انتقام خون پارسا به کتاب‌های صادق هدایت روی آورد و پس از مدتی به هیچ رسید "دنیا همه هیچ و اهل دنیا همه هیچ! / ای هیچ برای هیچ بر هیچ مپیچ." و سپس در روز ۹/۱۵ ...).

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

یک رشته به طول $n$ شامل کاراکترهای $[ , ] , (, )$ داریم. تعداد براکت گذاری‌های معتبر به طول $k$ با حذف هیچ یا تعدادی از کاراکترهای این رشته را می‌خواهیم.

رشته‌ی $S$ یک براکت گذاری معتبر است اگر از کنار هم گذاری دو براکت گذاری معتبر $T, F$ به صورت $TF$ یا از یک براکت گذاری معتبر $T$ به صورت $[T]$ یا $(T)$ به دست آید.

دقت کنید که رشته‌های مقابل براکت گذاری‌های معتبری هستند: $[ ( ) ] , [ ], ( ) , [ ( [ ] ) ( ) ]$
و رشته‌های مقابل نامعتبرند :‌ $[ ( ] ) , ( ]$


میخوای دست به دماغم بزنی باید سوال جواب بدی :/

ورودی🔗

ورودی شامل دو خط است که در خط اول دو عدد طبیعی $n$ و $k$ با فاصله از هم آمده‌اند. $1 \le n \le 10^5$ $1 \le k \le 16$ در خط دوم یک رشته به طول $n$ از کاراکتر‌های $[ , ] , (, )$ آمده است.

خروجی🔗

در یک خط باقی مانده‌ی تعداد براکت گذاری‌های معتبر به طول $k$ را بر $10^9 + 7$ چاپ کنید.

مثال🔗

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

6 2
((()))

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

به ۳ حالت می‌توانیم پرانتز باز را انتخاب کنیم و به ۳ حالت پرانتز بسته را، در نتیجه ۹ حالت داریم.

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

6 2
([()])

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

اگر دو کاراکتر انتخاب شده پرانتز باشند ۴ حالت داریم در غیر این صورت تنها یک حالت داریم. پس جواب نهایی ۵ می‌شود.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- رومینا مُرد (رفته بود آلیس رو از افسردگی در بیاره که خودش هم دچار افسردگی شد و ...). واندرلند تا مدت‌ها روی آرامش رو به خود می‌دید که سهراب وارد واندرلند شد. آوازه‌ی سهراب توی کل واندرلند پیچیده شده بود. ملکه‌ی قرمز دستور داد تا او را بیاورند. واندرلند شامل $n$ شهر است که با $m$ جاده به هم متصل شده است. به دلیل دعوای بین ملکه‌ی قرمز و ملکه‌ی سفید، می‌بایست کشور به دو بخش مجزا تقسیم شود که هر شهر در یک بخش به زوج تا از شهرهای داخل بخش خودش جاده داشته باشد (دقت کنید یکی از بخش‌ها می‌تواند تهی باشد). |![](https://quera.org/qbox/view/1xWxfyKMWK/E.jpeg)| |:--------:| | خودت زشتی ! | # ورودی ورودی شامل $n + 1$ خط است که در خط اول آن عدد طبیعی $n$ آمده است. $$1 \le n \le 500$$ در $n$ خط دیگر یک ماتریس $n$ در $n$ شامل $0, 1$ داده می‌شود. درایه‌ی $a_{i,j}$ نشان دهنده‌ی خانه‌ی واقع در سطر $i$ و ستون $j$ است. اگر $a_{i,j} = 1$ باشد یک جاده بین شهرهای $i$ و $j$ وجود دارد. تضمین می‌شود که $a_{i,j} = a_{i,j}$ و همچنین همواره $a_{i,i} = 0$ است. # خروجی خروجی باید شامل $4$ خط باشد: + خط اول تعداد شهرهای گروه اول. + خط دوم شهرهای گروه اول با فاصله از هم. + خط سوم تعداد شهرهای گروه دوم. + خط چهارم شهر های گروه دوم با فاصله از هم. اگر چندین حالت برای گروه بندی شهرها موجود بود به دلخواه یکی را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 4 0 1 1 1 1 0 0 0 1 0 0 0 1 0 0 0 ``` ## خروجی نمونه ۱ ``` 1 1 3 2 3 4 ``` ## ورودی نمونه ۲ ``` 4 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 ``` ## خروجی نمونه ۲ ``` 1 4 3 1 2 3 ```

ملکه قرمز

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

رومینا مُرد (رفته بود آلیس رو از افسردگی در بیاره که خودش هم دچار افسردگی شد و ...).

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

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


خودت زشتی !

ورودی🔗

ورودی شامل $n + 1$ خط است که در خط اول آن عدد طبیعی $n$ آمده است. $1 \le n \le 500$ در $n$ خط دیگر یک ماتریس $n$ در $n$ شامل $0, 1$ داده می‌شود.
درایه‌ی $a_{i,j}$ نشان دهنده‌ی خانه‌ی واقع در سطر $i$ و ستون $j$ است. اگر $a_{i,j} = 1$ باشد یک جاده بین شهرهای $i$ و $j$ وجود دارد.
تضمین می‌شود که $a_{i,j} = a_{i,j}$ و همچنین همواره $a_{i,i} = 0$ است.

خروجی🔗

خروجی باید شامل $4$ خط باشد:

خط اول تعداد شهرهای گروه اول.
خط دوم شهرهای گروه اول با فاصله از هم.
خط سوم تعداد شهرهای گروه دوم.
خط چهارم شهر های گروه دوم با فاصله از هم.

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

مثال🔗

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

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

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

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

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- سهراب مُرد (چون دیر به سهراب کمک رسید و در این مدت سهراب ذلت رو به عزت ترجیج داد و در شامگاهی ...) واندرلند پس از مرگ سهراب روی خوش به خود ندید. اما طبق معمول کوشان که تکالیف و ددلاین‌ها برایش اهمیت بیشتری داشت تصمیم گرفت از فضای واندرلند دور بشه و شروع به تنظیم برنامه‌ی هفته آیندش کنه. در واندرلند همه چیز عجیبه! مثلا در واندرلند یک هفته $n$ روز داره و کوشان نیز $n$ تمرین برای تحویل داره که تمرین $i$ام می‌بایست تا پایان روز $a_i$ تحویل داده بشه و به دلیل حجم بالای تمارین، هر تمرین یک روز کامل را برای حل کردن به خودش اختصاص می‌ده. حال به کوشان کمک کنید تا برنامه خود را جوری تعیین کنه که هر تمرین تا پایان زمان مورد نظر تموم بشه و در عین حال کمترین نابه‌جایی را در ترتیب کارها اعمال کنه. |![](https://quera.org/qbox/view/5BNsB5LKrb/F.jpg)| |:--------:| | سمت چپ اون چایی به دسته | # ورودی خط اول شامل عدد طبیعی $n$ است. در خط بعدی $n$ عدد آمده‌ است که $i$امین آن‌ها مهلت تحویل تمرین $i$ام است.$$1 \le n \le 10^5$$ $$1 \le a_i \le n$$ # خروجی اگر کوشان نتواند طوری تمارین رو انجام دهد که هر تمرین تا پایان روز تعیین شده به پایان برسد $-1$ و در غیر این صورت از بین تمامی جایگشت‌های ممکن نابه‌جایی آن جایگشتی از انجام تمارین را خروجی دهید که کمترین نابه‌جایی را دارد. # مثال ## ورودی نمونه ۱ ``` 3 3 2 1 ``` ## خروجی نمونه ۱ ``` 3 ``` در این نمونه مجبوریم کارها را به ترتیب ددلاینشان انجام دهیم. پس باید کارها را به ترتیب ۱ ۲ ۳ انجام دهیم که تعداد نابه‌جایی‌هایش ۳ می‌باشد.

ددلاین در واندرلند

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

سهراب مُرد (چون دیر به سهراب کمک رسید و در این مدت سهراب ذلت رو به عزت ترجیج داد و در شامگاهی ...)

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

در واندرلند همه چیز عجیبه! مثلا در واندرلند یک هفته $n$ روز داره و کوشان نیز $n$ تمرین برای تحویل داره که تمرین $i$ ام می‌بایست تا پایان روز $a_i$ تحویل داده بشه و به دلیل حجم بالای تمارین، هر تمرین یک روز کامل را برای حل کردن به خودش اختصاص می‌ده.

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


سمت چپ اون چایی به دسته

ورودی🔗

خط اول شامل عدد طبیعی $n$ است. در خط بعدی $n$ عدد آمده‌ است که $i$ امین آن‌ها مهلت تحویل تمرین $i$ ام است. $1 \le n \le 10^5$ $1 \le a_i \le n$

خروجی🔗

اگر کوشان نتواند طوری تمارین رو انجام دهد که هر تمرین تا پایان روز تعیین شده به پایان برسد $-1$ و در غیر این صورت از بین تمامی جایگشت‌های ممکن نابه‌جایی آن جایگشتی از انجام تمارین را خروجی دهید که کمترین نابه‌جایی را دارد.

مثال🔗

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

3
3 2 1

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

در این نمونه مجبوریم کارها را به ترتیب ددلاینشان انجام دهیم. پس باید کارها را به ترتیب ۱ ۲ ۳ انجام دهیم که تعداد نابه‌جایی‌هایش ۳ می‌باشد.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- کوشان مُرد (از استرس زیاد رسیدن به ددلاین‌ها ...). بعد از مرگ کوشان واندرلند به آرامش رسید و مردم واندرلند سعی در انجام بازی‌های مفرح کردند. یکی از این بازی‌ها بزن و بشکن است. بازی بزن و بشکن یک بازی دو نفره است که در ابتدا مجموعه‌ای شامل $n$ قارچ (فرض کنید $n$ همواره زوج است) به قد ۱ موجود است. حال نحوه‌ی بازی این‌گونه است که در هر مرحله، نفر اول دو قارچ انتخاب کرده و از بازی حذف می‌کند. سپس نفر دوم می‌تواند یکی از دو حرکت زیر را انجام دهد:‌ ۱- بزن: در این حرکت نفر دوم یک قارچ به قدِ مجموع قد دو قارچ انتخاب شده به مجموعه اضافه می‌کند. ۲- بشکن: در این حرکت نفر دوم یک قارچ به قدِ اختلاف قد دو قارچ انتخاب شده به مجموعه اضافه می‌کند (دقت کنید اینجا واندرلند است و قارچ با قد صفر نیز داریم!). و سپس این حرکات انقدر ادامه پیدا می‌کند تا یکی از دو شرط زیر برآورده شود: ۱- قد همه‌ی قارچ‌ها برابر صفر شده باشد. ۲- یک قارچ با قد بزرگتر از مجموع قد قارچ‌های دیگر وجود داشته باشد. نفر اولی که بازی را شروع می‌کند به اندازه‌ی تعداد قارچ‌های موجود در مجموعه از نفر دوم دلار می‌گیرد. بنابراین نفر دوم می‌خواهد کمترین مقدار دلار ممکن را به نفر اول بدهد و نفر اول نیز می‌خواهد بیشترین مقدار ممکن دلار را دریافت کند. حال سپهر و رائین می‌خواهند این بازی را $q$ بار با هم انجام دهند و هر بار هم سپهر بازی را شروع می‌کند. اما چون $n$ یکتا نیست و در شرط $2l \le n \le 2r$ صدق می‌کند، سپهر و رائین هر کدام $n$ مدنظر خودشان را پیشنهاد می‌دهند. به عبارتی دیگر رائین می‌خواهد $n_1$ای را بدهد که کمترین میزان دلار را به سپهر بدهد و سپهر می‌خواهد $n_2$ای را بدهد که بیشترین دلار را از رائین بگیرد. |![](https://quera.org/qbox/view/JXnS7eizvG/G.jpg)| |:--------:| | قارچ صفر | # ورودی خط اول شامل یک عدد طبیعی $q$ است. سپس در $q$ خط بعدی، در هر خط دو عدد آمده‌ است که نشان دهنده‌ی $l, r$ است.$$1 \le q \le 10^5$$ $$1 \le l \le r \le 10^{18}$$ # خروجی خروجی شامل $q$ خط میبایست باشد که خط $i$ام به ترتیب شامل دو عدد که تعداد دلار داده شده در حالت شروع بازی با $n_1$ و $n_2$ قارچ است. # مثال ## ورودی نمونه ۱ ``` 2 2 6 8 10 ``` ## خروجی نمونه ۱ ``` 1 2 1 2 ``` برای query اول در ابتدا انتخاب می‌کنیم که ۲ قارچ باشد. با این کار وقتی که بازی شروع شود با انتخاب این دو قارچ و هر عملیاتی که انجام شود، تنها یک قارچ می ماند و باید یک دلار داده شود که این مقدار کمینه است. برای حالت بیشینه باید شش قارچ انتخاب کنیم که اثبات می شود اگر هر دو طرف بهینه بازی کنند ۲ دلار باید داده شود.

قارچ صفر

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

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

بعد از مرگ کوشان واندرلند به آرامش رسید و مردم واندرلند سعی در انجام بازی‌های مفرح کردند. یکی از این بازی‌ها بزن و بشکن است. بازی بزن و بشکن یک بازی دو نفره است که در ابتدا مجموعه‌ای شامل $n$ قارچ (فرض کنید $n$ همواره زوج است) به قد ۱ موجود است. حال نحوه‌ی بازی این‌گونه است که در هر مرحله، نفر اول دو قارچ انتخاب کرده و از بازی حذف می‌کند. سپس نفر دوم می‌تواند یکی از دو حرکت زیر را انجام دهد:‌

۱- بزن: در این حرکت نفر دوم یک قارچ به قدِ مجموع قد دو قارچ انتخاب شده به مجموعه اضافه می‌کند.
۲- بشکن: در این حرکت نفر دوم یک قارچ به قدِ اختلاف قد دو قارچ انتخاب شده به مجموعه اضافه می‌کند (دقت کنید اینجا واندرلند است و قارچ با قد صفر نیز داریم!).

و سپس این حرکات انقدر ادامه پیدا می‌کند تا یکی از دو شرط زیر برآورده شود:

۱- قد همه‌ی قارچ‌ها برابر صفر شده باشد.
۲- یک قارچ با قد بزرگتر از مجموع قد قارچ‌های دیگر وجود داشته باشد.

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

حال سپهر و رائین می‌خواهند این بازی را $q$ بار با هم انجام دهند و هر بار هم سپهر بازی را شروع می‌کند. اما چون $n$ یکتا نیست و در شرط $2l \le n \le 2r$ صدق می‌کند، سپهر و رائین هر کدام $n$ مدنظر خودشان را پیشنهاد می‌دهند. به عبارتی دیگر رائین می‌خواهد $n_1$ ای را بدهد که کمترین میزان دلار را به سپهر بدهد و سپهر می‌خواهد $n_2$ ای را بدهد که بیشترین دلار را از رائین بگیرد.


قارچ صفر

ورودی🔗

خط اول شامل یک عدد طبیعی $q$ است. سپس در $q$ خط بعدی، در هر خط دو عدد آمده‌ است که نشان دهنده‌ی $l, r$ است. $1 \le q \le 10^5$ $1 \le l \le r \le 10^{18}$

خروجی🔗

خروجی شامل $q$ خط میبایست باشد که خط $i$ ام به ترتیب شامل دو عدد که تعداد دلار داده شده در حالت شروع بازی با $n_1$ و $n_2$ قارچ است.

مثال🔗

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

2
2 6
8 10

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

1 2
1 2

برای query اول در ابتدا انتخاب می‌کنیم که ۲ قارچ باشد. با این کار وقتی که بازی شروع شود با انتخاب این دو قارچ و هر عملیاتی که انجام شود، تنها یک قارچ می ماند و باید یک دلار داده شود که این مقدار کمینه است. برای حالت بیشینه باید شش قارچ انتخاب کنیم که اثبات می شود اگر هر دو طرف بهینه بازی کنند ۲ دلار باید داده شود.