سطح مکعب

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

فردا تولد حیدریه!

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

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

به آن‌ها کمک کنید این کمینه مساحت را پیدا کنند.

ورودی🔗

ورودی تنها شامل یک عدد $V$ است. $1 \le V \le 1\ 000\ 000$

خروجی🔗

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

مثال🔗

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

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

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

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

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

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

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

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

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- فردا تولد حیدریه! دوستان حیدری می‌خواهند برای او تولدی در یک کله‌پزی بگیرند و به همین دلیل به توصیه جعفر گوش کرده‌اند: جعفر توصیه کرده بود که امروز برای بررسی شرایط به کله‌پزی سر بزنند. جعفر و سلطانی که از دوستان با وفای حیدری هستند سوار ماشین شده‌اند تا به کله‌پزی بروند. اما از بد روزگار سلطانی پشت فرمون نشسته و سر یک تقاطع پلیس دیده و به یاد جرم و جنایت‌هایش می‌افتد، به همین دلیل هول شده و تقاطع را اشتباه می‌پیچد. حالا آن‌ها در مرکز شهر گم شده‌اند ولی خوشبختانه جعفر همیشه یک نقشه از مرکز شهر با خودش حمل می‌کند. همه می‌دانیم که مرکز شهر رشت از تعدادی میدان تشکیل شده که در هر میدان یا می‌توان به چپ پیچید یا به راست، و در هر میدان یا می‌توان ساختمان تاریخی شهرداری رشت را دید یا نمی‌توان دید. با این‌که جعفر نقشه را دارد اما مشکل این‌جاست که آن‌ها نمی‌دانند در کدام میدان شهر قرار دارند! جعفر ادعا می‌کند که آن‌ها در میدان $A$ قرار دارند ولی سلطانی می‌گوید در میدان $B$ قرار دارند‌. طبق تجربه ما می‌دانیم همیشه دقیقاً یکی از این دو نفر راست می‌گوید. خوش‌بختانه جعفر نقشه‌اش را از مترو خریده و به همین خاطر روی آن برای هر میدان مشخص شده که آیا می‌توان از آن‌جا ساختمان شهرداری را دید یا نه. حالا آن دو تصمیم گرفته‌اند در شهر حرکت کنند و به هر میدان که می‌رسند از پنجره نگاه کنند که آیا شهرداری را می‌بینند یا نه‌. هم‌چنین با دنبال کردن نقشه یک بار با فرض این‌که ابتدا در میدان $A$ بوده‌اند و یک بار با فرض این‌که در میدان $B$ بوده‌اند و همچنین با توجه به مسیری که تا کنون پیموده‌اند می‌توانند تعیین کنند که آیا در حال حاضر باید بتوانند شهرداری را ببینند یا خیر. به محض این‌که معلوم شود آن‌ها در ابتدا در کدام شهر قرار داشته‌اند آن‌ها خوشحال می‌شوند. با این‌که ما می‌دانیم معمولاً سلطانی اشتباه می‌کند، ولی به آن‌ها بگویید حداقل چند بار باید در میدان های شهر بپیچند تا معلوم شود کدام یک راست می‌گوید، یا تعیین کنید که با این روش نمی‌توان محل آن‌ها را یافت و آن‌ها این سوال را با خود به گور می‌برند. # ورودی در خط اول ورودی ۳ عدد $n$ تعداد میدان‌های مرکز شهر، $A$ شهر مورد نظر جعفر، و $B$ شهر مورد نظر سلطانی با فاصله از هم آمده‌اند. تضمین می‌شود $A$ و $B$ متمایز هستند. سپس در $n$ خط بعدی در خط $i$ام ($i$ از ۰ تا $n$) به ترتیب $l_i$ میدانی که در صورت پیچیدن به چپ در میدان $i$ به آن می‌رسیم و $r_i$ میدانی که در صورت پیچیدن به راست در میدان $i$ به آن می‌رسیم و $t_i$ آمده است.اگر $t_i$ برابر ۱ باشد از میدان $i$ می‌توان ساختمان شهرداری را دید و اگر ۰ باشد نمیتوان. $$2 \le n \le 100\ 000$$ $$0 \le A, B < n$$ # خروجی در تنها خط خروجی کمینه طول مسیر (تعداد پیچیدن های به چپ و راست) را که جعفر و سلطانی باید انجام دهند تا بفهمند حق با کیست چاپ کنید. در صورتی که این کار ممکن نیست تنها عبارت `indistinguishable` را در خروجی چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 3 1 2 1 2 1 0 2 0 0 1 0 ``` ## خروجی نمونه ۱ ``` indistinguishable ``` ## ورودی نمونه ۲ ``` 2 0 1 1 1 1 0 0 0 ``` ## خروجی نمونه ۲ ``` 0 ``` ## ورودی نمونه ۳ ``` 3 1 2 1 2 0 2 0 1 0 1 1 ``` ## خروجی نمونه ۳ ``` 1 ```

غیر قابل تمایز

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

فردا تولد حیدریه!

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

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

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

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

با این‌که جعفر نقشه را دارد اما مشکل این‌جاست که آن‌ها نمی‌دانند در کدام میدان شهر قرار دارند! جعفر ادعا می‌کند که آن‌ها در میدان $A$ قرار دارند ولی سلطانی می‌گوید در میدان $B$ قرار دارند‌. طبق تجربه ما می‌دانیم همیشه دقیقاً یکی از این دو نفر راست می‌گوید.

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

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

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

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

ورودی🔗

در خط اول ورودی ۳ عدد $n$ تعداد میدان‌های مرکز شهر، $A$ شهر مورد نظر جعفر، و $B$ شهر مورد نظر سلطانی با فاصله از هم آمده‌اند. تضمین می‌شود $A$ و $B$ متمایز هستند.

سپس در $n$ خط بعدی در خط $i$ ام ( $i$ از ۰ تا $n$ ) به ترتیب $l_i$ میدانی که در صورت پیچیدن به چپ در میدان $i$ به آن می‌رسیم و $r_i$ میدانی که در صورت پیچیدن به راست در میدان $i$ به آن می‌رسیم و $t_i$ آمده است.اگر $t_i$ برابر ۱ باشد از میدان $i$ می‌توان ساختمان شهرداری را دید و اگر ۰ باشد نمیتوان. $2 \le n \le 100\ 000$ $0 \le A, B < n$

خروجی🔗

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

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

مثال🔗

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

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

indistinguishable

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

2 0 1
1 1 1
0 0 0

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

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

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

+ محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- فردا تولد حیدریه! به همین دلیل حیدری احساس می‌کند پیر شده و به فکر بازنشستگی افتاده است. اگر حیدری $M$ تومان پول در حسابش داشته باشد می‌تواند با خیال راحت بازنشسته شود. ولی متاسفانه در حال حاضر حساب حیدری خالیست! خوش‌بختانه دوست حیدری، سلطانی، یک مولتی میلیاردر است که هر چقدر حیدری پول بخواهد به او برای سرمایه‌گذاری در بورس می‌دهد. (البته داوود هم یک مولتی میلیاردر است ولی از آن‌جایی که داوود خیلی خودش را می‌گیرد حیدری هرگز از او پولی درخواست نمی‌کند.) در بازار بورس $n$ فرصت سرمایه‌گذاری وجود دارد که $i$-امی آن‌ها ابتدا به $c_i$ تومان پول برای شروع نیاز دارد پس از سرمایه‌گذاری هر روز $p_i$ تومان سود می‌دهد. حیدری در هریک از این فرصت‌ها می‌تواند حداکثر یک بار سرمایه‌گذاری کند، اما او می‌تواند در هر چند فرصت مختلفی که بخواهد سرمایه‌گذاری کند. (حیدری کامپیوتری است؛ برای همین تواسته سود روزانه این فرصت‌ها را محاسبه کند.) به حیدری کمک کنید تا روشی برای سرمایه‌گذاری انتخاب کند که در کوتاه ترین زمان بتواند تمام پول سلطانی را به او پس بدهد و برای خودش هم حداقل $M$ تومان پول بماند تا بتواند با خیال راحت بازنشسته شود. به او بگویید این کوتاه‌ترین زمان چند روز است. # ورودی در خط اول وروردی دو عدد طبیعی $n$ و $M$ با فاصله از هم آمده است. $$1 \le n \le 100\ 000$$ $$1 \le M \le 10^9$$ در $n$ خط بعدی در هر خط دو عدد آمده که به ترتیب $p_i$ و $c_i$ را نشان می‌دهد $$1 \le p_i, c_i \le 10^9$$ # خروجی در تنها خط خروجی کم‌ترین تعداد روزی که لازم است تا حیدری بعد از پس دادن پول سلطانی $M$تومان سود کند را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 2 5 4 10 10 15 ``` ## خروجی نمونه ۱ ``` 2 ``` ## ورودی نمونه ۲ ``` 4 10 1 8 3 12 4 17 10 100 ``` ## خروجی نمونه ۲ ``` 6 ``` ## ورودی نمونه ۳ ``` 3 5 4 1 9 10 6 3 ``` ## خروجی نمونه ۳ ``` 1 ```

سرمایه‌گذاری کم‌دردسر

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

فردا تولد حیدریه!

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

اگر حیدری $M$ تومان پول در حسابش داشته باشد می‌تواند با خیال راحت بازنشسته شود. ولی متاسفانه در حال حاضر حساب حیدری خالیست!

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

در بازار بورس $n$ فرصت سرمایه‌گذاری وجود دارد که $i$ -امی آن‌ها ابتدا به $c_i$ تومان پول برای شروع نیاز دارد پس از سرمایه‌گذاری هر روز $p_i$ تومان سود می‌دهد. حیدری در هریک از این فرصت‌ها می‌تواند حداکثر یک بار سرمایه‌گذاری کند، اما او می‌تواند در هر چند فرصت مختلفی که بخواهد سرمایه‌گذاری کند. (حیدری کامپیوتری است؛ برای همین تواسته سود روزانه این فرصت‌ها را محاسبه کند.)

به حیدری کمک کنید تا روشی برای سرمایه‌گذاری انتخاب کند که در کوتاه ترین زمان بتواند تمام پول سلطانی را به او پس بدهد و برای خودش هم حداقل $M$ تومان پول بماند تا بتواند با خیال راحت بازنشسته شود.

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

ورودی🔗

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

خروجی🔗

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

مثال🔗

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

2 5
4 10
10 15

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

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

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

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

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

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- فردا تولد حیدریه! حیدری دوستانش را خیلی عجیب انتخاب می‌کند به همین دلیل دوستان او یا روس هستند (`A`) یا سفید (`B`) یا سیاه (`C`). دوستان حیدری به مناسبت تولدش به خانه او آمده‌اند و خودشان به دل‌خواه دور میز دایره‌ای شکل داخل آشپزخانه نشسته‌اند. از آن‌جایی که حیدری اعتقاد دارد سیاه‌ها باید کنار هم بنشینند و هم‌چنین سفیدها هم باید کنار هم بنشینند و از همه جالب تر این‌که روس‌ها هم باید کنار هم بنشینند، به او کمک کنید که از کم‌ترین تعداد مهمان‌ها بخواهد صندلیشان را با همدیگر عوض کنند به صورتی که به اعتقادات او لطمه‌ای نخورد. (روس‌ها کنار هم، سفیدها کنار هم، و سیاه‌ها کنار هم بنشینند.) تعویض صندلی به این صورت انجام می‌شود که ابتدا همه‌ی افراد منتخب می‌ایستند، صندلی‌شان را با یکدیگر تعویض کرده، و سپس همه می‌نشینند. # ورودی در خط اول ورودی $n$ تعداد دوستان حیدری آمده است. $$1 \le n \le 100\ 000$$ سپس در خط دوم ورودی یک رشته به طول $n$ آمده است متشکل از حروف `A`، `B` و `C` که ترتیب نشستن دوستان حیدری دور میز را نشان می‌دهد. (دقت کنید که میز دایره‌ایست!) # خروجی در تنها خط خروجی کمترین تعداد نفراتی را چاپ کنید که باید از آن‌ها بخواهیم تا صندلیشان را عوض کنند. # مثال ## ورودی نمونه ۱ ``` 5 ABABC ``` ## خروجی نمونه ۱ ``` 2 ``` ## ورودی نمونه ۲ ``` 12 ABCABCABCABC ``` ## خروجی نمونه ۲ ``` 6 ``` ## ورودی نمونه ۳ ``` 4 ACBA ``` ## خروجی نمونه ۳ ``` 0 ``` ## ورودی نمونه ۴ ``` 6 BABABA ``` ## خروجی نمونه ۴ ``` 2 ``` ## ورودی نمونه ۵ ``` 9 ABABCBCAC ``` ## خروجی نمونه ۵ ``` 3 ```

حیدری نژادپرست

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

فردا تولد حیدریه!

حیدری دوستانش را خیلی عجیب انتخاب می‌کند به همین دلیل دوستان او یا روس هستند (A) یا سفید (B) یا سیاه (C).

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

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

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

ورودی🔗

در خط اول ورودی $n$ تعداد دوستان حیدری آمده است. $1 \le n \le 100\ 000$ سپس در خط دوم ورودی یک رشته به طول $n$ آمده است متشکل از حروف A، B و C که ترتیب نشستن دوستان حیدری دور میز را نشان می‌دهد. (دقت کنید که میز دایره‌ایست!)

خروجی🔗

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

مثال🔗

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

5
ABABC

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

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

12
ABCABCABCABC

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

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

4
ACBA

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

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

6
BABABA

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

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

9
ABABCBCAC

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

+ محدودیت زمان: ۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- فردا تولد حیدریه! ولی از آن‌جایی که حیدری خیلی ذوق تولدش را دارد تا الان $T$ مهمانی تولد گرفته و در هرکدام تعدادی کادو از دوستانش دریافت کرده است. حیدری بعد از هر مهمانی ‌کادوهایش را به ترتیب باز می‌کند، و بعد از باز کردن هر کادو به اندازه مجموع ارزش کادوهایی که تا به الان باز کرده خوش‌حالی می‌کند. برای مثال اگر او ۲ کادو به ارزش ۲ تومان و ۷ تومان هدیه بگیرد پس از باز کردن اولی ۲ بار خوش‌حالی می‌کند، و پس از باز کردن دومی ۲ + ۷ = ۹ بار خوش‌حالی می‌کند. این به این معناست که در آخر شب او مجموعاً ۲ + ۹ = ۱۱ بار خوش‌حالی کرده است. می‌دانیم همه دوستان حیدری کادوهایشان را از مغازه علی‌آقا می‌خرند و اجناس مغازه علی‌آقا $M$ قیمت متفاوت دارد. حال حیدری به ازای هر مهمانی تولد به شما قیمت اجناس مغازه علی‌آقا و هم‌چنین عدد $N$ مجموع خوش‌حالی‌هایی را که آن شب کرده است می‌گوید، شما بیش‌ترین مجموع قیمت ممکن برای کادو‌هایی که حیدری دریافت کرده است را بگویید! # ورودی در خط اول ورودی $T$ تعداد مهمانی‌های حیدری داده شده است. برای هر مهمانی به ترتیب دو عدد $N$ مجموع خوش‌حالی‌های حیدری در آن شب و $M$ تعداد قیمت‌های متفاوت اجناس مغازه علی‌آقا در یک خط داده می‌شود. سپس در خط بعدی $M$ عدد متفاوت آمده است که نشان دهنده قیمت اجناس مغازه علی‌آقاست. می‌دانیم قیمت اجناس مغازه حداقل ۱ و حداکثر ۲۰ تومان است. $$1 \le T \le 20$$ $$1 \le N \le 5000$$ $$1 \le M \le 10$$ # خروجی در $T$ خط خروجی برای هر مهمانی، بیش‌ترین مجموع ارزش ممکن کادو‌هایی که حیدری گرفته است را چاپ کنید و اگر ممکن نیست همه اجناس از مغازه علی‌آقا خریداری شده باشد و حیدری دقیقاً $N$ بار خوش‌حالی کرده باشد عدد `-1` را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 4 29 3 7 3 2 15 1 1 16 1 1 6 2 3 1 ``` ## خروجی نمونه ۱ ``` 14 5 -1 3 ```

خوش‌حالی تولد

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

فردا تولد حیدریه!

ولی از آن‌جایی که حیدری خیلی ذوق تولدش را دارد تا الان $T$ مهمانی تولد گرفته و در هرکدام تعدادی کادو از دوستانش دریافت کرده است.

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

برای مثال اگر او ۲ کادو به ارزش ۲ تومان و ۷ تومان هدیه بگیرد پس از باز کردن اولی ۲ بار خوش‌حالی می‌کند، و پس از باز کردن دومی ۲ + ۷ = ۹ بار خوش‌حالی می‌کند. این به این معناست که در آخر شب او مجموعاً ۲ + ۹ = ۱۱ بار خوش‌حالی کرده است.

می‌دانیم همه دوستان حیدری کادوهایشان را از مغازه علی‌آقا می‌خرند و اجناس مغازه علی‌آقا $M$ قیمت متفاوت دارد.

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

ورودی🔗

در خط اول ورودی $T$ تعداد مهمانی‌های حیدری داده شده است.

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

سپس در خط بعدی $M$ عدد متفاوت آمده است که نشان دهنده قیمت اجناس مغازه علی‌آقاست. می‌دانیم قیمت اجناس مغازه حداقل ۱ و حداکثر ۲۰ تومان است.

$1 \le T \le 20$ $1 \le N \le 5000$ $1 \le M \le 10$

خروجی🔗

در $T$ خط خروجی برای هر مهمانی، بیش‌ترین مجموع ارزش ممکن کادو‌هایی که حیدری گرفته است را چاپ کنید و اگر ممکن نیست همه اجناس از مغازه علی‌آقا خریداری شده باشد و حیدری دقیقاً $N$ بار خوش‌حالی کرده باشد عدد -1 را چاپ کنید.

مثال🔗

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

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

کاغذ کادو چهارضلعی

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

فردا تولد حیدریه!

دوستان حیدری می‌دانند حیدری ۴ عدد مورد علاقه دارد که این ۴ عدد یک خاصیت عجیب دارند: هر کدام از آن‌ها را که انتخاب کنید حتماً از جمع ۳ تای دیگر کوچک‌تر است. (نکته جالب‌تر این که ممکن است در میان این ۴ عدد، عددی تکراری وجود داشته باشد.)

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

ورودی🔗

در تنها خط ورودی ۴ عدد $a$ و $b$ و $c$ و $d$ آمده است که نشان‌دهنده اعداد مورد علاقه حیدریست. $1 \le a, b, c, d \le 1\ 000$

خروجی🔗

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

مثال🔗

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

3 3 3 3

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

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

1 2 1 1

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

1.299038105676658

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

2 2 1 4

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

3.307189138830738

اعداد تپه‌ای

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

فردا تولد حیدریه!

به همین دلیل دوست حیدری حال ندارد برای این سوال داستان بنویسد.

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

برای مثال اعداد ۱۲۲۳۴۴۲۱، ۱۲، ۳۵۷، ۵۴۱ و ۱۲۳۲۱ حیدری-تپه‌ای هستند ولی اعداد ۱۲۳۲۱۳، ۱۰۱ و ۳۷۳۵ حیدری-تپه‌ای نیستند.

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

ورودی🔗

در خط اول ورودی $T$ تعداد اعداد داده می‌شود.

سپس در $T$ خط بعدی در هر خط یک عدد حداکثر ۷۰ رقمی به شما داده می‌شود.

خروجی🔗

در $T$ خط جواب سوال را چاپ کنید.

تضمین می‌شود همیشه جواب در متغیر ۶۴-بیتی جا می‌شود.

مثال🔗

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

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

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- فردا تولد حیدریه! اما حیدری به روز دقیق تولد اعتقادی ندارد و می‌خواهد جوری تولد بگیرد که همه یک عالمه خوشحال شوند. حیدری لیست تاریخ تولد همه دوستانش را دارد و می‌داند که همه دوستانش در جعبه فکر می‌کنند. بخاطر همین همه دوستانش دقیقاً در روز تولد خودشان مهمانی می‌گیرند. تو جهان خارج جعبه‌ی حیدری تقویم میلادی برقرار و امروز ۲۷ اکتبر است. تو این تقویم سال کبیسه وجود ندارد. حیدری *نوتیس* کرده که دوستانش وقتی از مهمانی تولدش خوشحال می‌شوند که زمان زیادی از آخرین مهمانی تولدی که گرفته شده گذشته باشد. بخاطر همین او روزی را انتخاب می‌کند که از آخرین تولد قبل از آن زمان زیادی گذشته باشد. حیدری طبعاً نمی‌خواهد روز تولدش با کسی یکسان شود. هم‌چنین اگر چندین تاریخ وجود داشته باشد که دوستانش به بیش‌ترین حالت ممکن خوشحال شوند، او نزدیک ترین تاریخ به امروز (۲۷ اکتبر!) را برای گرفتن تولد انتخاب می‌کند. اما این تاریخ نباید امروز باشد. ![در جهان خارج جعبه حیدری تمامی سال های میلادی به صورت تصویر بالاست!](https://quera.ir/qbox/download/t8cjaj6JpR/Screen%20Shot%201398-09-12%20at%2011.52.39(1).jpg) همچنین در نظر داشته باشید که در جهان خارج جعبه حیدری تمامی سال های میلادی به صورت تصویر بالا هستند! به حیدری کمک کنید بهترین روز را برای برگزاری مهمانی تولد انتخاب کند. # ورودی در خط اول ورودی $n$ تعداد دوستان حیدری می‌آید. سپس در $n$ خط بعدی به ترتیب در هر خط نام یکی از دوستان حیدری و سپس تاریخ تولد او می‌آید که با یک فاصله از هم جدا شده‌اند. نام دوستان حیدری رشته‌ای با حداکثر ۲۰ حرف متشکل از حروف بزرگ و کوچک انگلیسی است، و هم‌چنین تاریخ تولد هر نفر به صورت $dd$-$mm$ داده می‌شود که در آن $mm$ نشان‌دهنده ماه و $dd$ نشان دهنده روز تولد است. تضمین می‌شود که مقدار تاریخ‌های تولد درست است. $$1 \le n \le 100$$ # خروجی در تنها خط خروجی یک تاریخ به همان صورت $dd$-$mm$ چاپ کنید که بهترین روز برای برگزاری مهمنی تولد حیدریست. توجه داشته باشید در صورت وجود چند جواب حیدری روزی را انتخاب می‌کند که به امروز (۲۷ اکتبر!) نزدیک تر است ولی امروز نیست! **هم‌چنین تولد حیدری ممکن است در سال بعدی میلادی برگزار شود!** یعنی مثلاً بعد ماه آخر میلادی (دسامبر) ماه اول سال بعد (ژانویه) است سپس ماه دوم می‌آید و به همین ترتیب... # مثال ## ورودی نمونه ۱ ``` 3 Henk 01-09 Roos 09-20 Pietje 11-11 ``` ## خروجی نمونه ۱ ``` 09-19 ``` ## ورودی نمونه ۲ ``` 16 Henk 01-09 Luc 12-31 Jan 03-22 Roos 09-20 Pietje 11-11 Anne 02-28 Pierre 09-25 Dan 12-15 Lieze 11-17 Charlotte 05-01 Lenny 08-02 Marc 04-25 Martha 06-12 John 03-26 Matthew 01-20 John 01-20 ``` ## خروجی نمونه ۲ ``` 08-01 ``` ## ورودی نمونه ۳ ``` 3 JohnIII 04-29 JohnVI 10-28 JohnIIX 04-28 ``` ## خروجی نمونه ۳ ``` 04-27 ``` ## ورودی نمونه ۴ ``` 3 CharlesII 04-30 CharlesV 10-29 CharlesVII 04-29 ``` ## خروجی نمونه ۴ ``` 10-28 ```

تولد تاریخی

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

فردا تولد حیدریه!

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

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

تو جهان خارج جعبه‌ی حیدری تقویم میلادی برقرار و امروز ۲۷ اکتبر است. تو این تقویم سال کبیسه وجود ندارد.

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

حیدری طبعاً نمی‌خواهد روز تولدش با کسی یکسان شود. هم‌چنین اگر چندین تاریخ وجود داشته باشد که دوستانش به بیش‌ترین حالت ممکن خوشحال شوند، او نزدیک ترین تاریخ به امروز (۲۷ اکتبر!) را برای گرفتن تولد انتخاب می‌کند. اما این تاریخ نباید امروز باشد.

در جهان خارج جعبه حیدری تمامی سال های میلادی به صورت تصویر بالاست!

همچنین در نظر داشته باشید که در جهان خارج جعبه حیدری تمامی سال های میلادی به صورت تصویر بالا هستند!

به حیدری کمک کنید بهترین روز را برای برگزاری مهمانی تولد انتخاب کند.

ورودی🔗

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

نام دوستان حیدری رشته‌ای با حداکثر ۲۰ حرف متشکل از حروف بزرگ و کوچک انگلیسی است، و هم‌چنین تاریخ تولد هر نفر به صورت $dd$ - $mm$ داده می‌شود که در آن $mm$ نشان‌دهنده ماه و $dd$ نشان دهنده روز تولد است. تضمین می‌شود که مقدار تاریخ‌های تولد درست است.

$1 \le n \le 100$

خروجی🔗

در تنها خط خروجی یک تاریخ به همان صورت $dd$ - $mm$ چاپ کنید که بهترین روز برای برگزاری مهمنی تولد حیدریست.

توجه داشته باشید در صورت وجود چند جواب حیدری روزی را انتخاب می‌کند که به امروز (۲۷ اکتبر!) نزدیک تر است ولی امروز نیست!

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

مثال🔗

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

3
Henk 01-09
Roos 09-20
Pietje 11-11

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

09-19

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

16
Henk 01-09
Luc 12-31
Jan 03-22
Roos 09-20
Pietje 11-11
Anne 02-28
Pierre 09-25
Dan 12-15
Lieze 11-17
Charlotte 05-01
Lenny 08-02
Marc 04-25
Martha 06-12
John 03-26
Matthew 01-20
John 01-20

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

08-01

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

3
JohnIII 04-29
JohnVI 10-28
JohnIIX 04-28

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

04-27

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

3
CharlesII 04-30
CharlesV 10-29
CharlesVII 04-29

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

10-28

+ محدودیت زمان: ۱.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- فردا تولد حیدریه! حیدری در مغازه‌ش $n$ تا جنس برای فروش دارد و می‌خواهد به مناسبت تولدش جشنواره تخفیف برگزار کند. جشنواره حیدری به این صورت است که او یک زیرمجموعه از اجناس مغازه‌اش و یک عدد $X$ را اعلام می‌کند. سپس مشتری‌ها این اجناس را می‌خرند. اگر مشتری‌ای دقیقاً ۲ تا از اجناس آن زیر مجموعه را بخرد و جمع قیمت آن‌ها اکیداً بیش‌تر از $X$ باشد، آن مشتری تخفیف می‌گیرد. از آن‌جا که حیدری از تخفیف دادن متنفر است به او کمک کنید اندازه بزرگترین زیر مجموعه‌ای را برای جشنواره پیدا کند که کسی نتواند از او تخفیف بگیرد. # ورودی در خط اول ورودی دو عدد طبیعی $n$ و $X$ با فاصله از هم آمده است. سپس در خط دوم ورودی $n$ عدد آمده است که قیمت هر یک از اجناس مغازه را نشان می‌دهد. قیمت هر جنس حداکثر $10^9$ تومان است. $$1 \le n \le 100\ 000$$ $$1 \le X \le 10^9$$ # خروجی در خروجی یک عدد چاپ کنید که نشان دهنده بیش‌ترین تعداد اجناسیست که حیدری می‌تواند برای جشنواره انتخاب کند به صورتی که کسی نتواند از او تخفیف بگیرد. # مثال ## ورودی نمونه ۱ ``` 5 6 1 2 3 4 5 ``` ## خروجی نمونه ۱ ``` 3 ``` ## ورودی نمونه ۲ ``` 5 10 4 8 1 9 7 ``` ## خروجی نمونه ۲ ``` 2 ``` ## ورودی نمونه ۳ ``` 4 10 1 3 1 7 ``` ## خروجی نمونه ۳ ``` 4 ``` ## ورودی نمونه ۴ ``` 1 5 6 ``` ## خروجی نمونه ۴ ``` 1 ```

تخفیف جشنواره

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

فردا تولد حیدریه!

حیدری در مغازه‌ش $n$ تا جنس برای فروش دارد و می‌خواهد به مناسبت تولدش جشنواره تخفیف برگزار کند.

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

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

ورودی🔗

در خط اول ورودی دو عدد طبیعی $n$ و $X$ با فاصله از هم آمده است. سپس در خط دوم ورودی $n$ عدد آمده است که قیمت هر یک از اجناس مغازه را نشان می‌دهد. قیمت هر جنس حداکثر $10^9$ تومان است. $1 \le n \le 100\ 000$ $1 \le X \le 10^9$

خروجی🔗

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

مثال🔗

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

5 6
1 2 3 4 5

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

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

5 10
4 8 1 9 7

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

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

4 10
1 3 1 7

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

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

1 5
6