+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- فردا تولد حیدریه! حیدری به اجسامی با حجم دقیقاً $V$ علاقه‌ای خاص دارد؛ به همین دلیل دوستانش می‌خواهند جعبه‌ای به شکل مکعب مستطیل با اضلاعی به طول صحیح برای او بسازند که حجمی دقیقاً برابر $V$ دارد. از آن‌جایی که مقوا گران شده، دوستان حیدری به دنبال مکعبی با حجم $V$ هستند که مساحت مقوای به کار رفته برای ساخت آن کمینه باشد. به آن‌ها کمک کنید این کمینه مساحت را پیدا کنند. # ورودی ورودی تنها شامل یک عدد $V$ است. $$1 \le V \le 1\ 000\ 000$$ # خروجی در تنها خط خروجی کمترین مساحت مقوای لازم برای ساخت مکعب مورد نظر را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 1 ``` ## خروجی نمونه ۱ ``` 6 ``` ## ورودی نمونه ۲ ``` 4 ``` ## خروجی نمونه ۲ ``` 16 ``` ## ورودی نمونه ۳ ``` 3 ``` ## خروجی نمونه ۳ ``` 14 ``` ## ورودی نمونه ۴ ``` 5913 ``` ## خروجی نمونه ۴ ``` 2790 ``` ---------- <details class="orange"> <summary> راهنمایی ۱ </summary> از آن‌جایی که طول اضلاع مکعب اعدادی صحیحند پس حتماً آن‌ها همگی مقسوم علیه‌های $V$ هستند. اگر همه مقسوم‌علیه‌های $V$ را پیدا کنیم، می‌توانیم همه حالت اضلاع مکعب را چک کنیم، سپس جوابی را که کمترین مساحت را دارد بیابیم. در راهنمایی بعدی، شبه‌کد یافتن مقسوم علیه‌های یک عدد، و هم‌چنین شبه کد یافتن همه حالت‌های اضلاع مکعب توضیح داده می‌شود. </details> <details class="orange"> <summary> راهنمایی ۲ </summary> شبه کد یافتن مقسوم‌علیه های یک عدد: ```c for i in 1 -> n: if n % i == 0: divs.add(i) ``` شبه کد بررسی حالات اضلاع مکعب: ```c for a in divs: for b in divs: if V % (a * b) == 0: c = V / (a * b) //a, b and c are the edges ``` </details>

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- فردا تولد حیدریه! دوستان حیدری می‌خواهند برای او تولدی در یک کله‌پزی بگیرند و به همین دلیل به توصیه جعفر گوش کرده‌اند: جعفر توصیه کرده بود که امروز برای بررسی شرایط به کله‌پزی سر بزنند. جعفر و سلطانی که از دوستان با وفای حیدری هستند سوار ماشین شده‌اند تا به کله‌پزی بروند. اما از بد روزگار سلطانی پشت فرمون نشسته و سر یک تقاطع پلیس دیده و به یاد جرم و جنایت‌هایش می‌افتد، به همین دلیل هول شده و تقاطع را اشتباه می‌پیچد. حالا آن‌ها در مرکز شهر گم شده‌اند ولی خوشبختانه جعفر همیشه یک نقشه از مرکز شهر با خودش حمل می‌کند. همه می‌دانیم که مرکز شهر رشت از تعدادی میدان تشکیل شده که در هر میدان یا می‌توان به چپ پیچید یا به راست، و در هر میدان یا می‌توان ساختمان تاریخی شهرداری رشت را دید یا نمی‌توان دید. با این‌که جعفر نقشه را دارد اما مشکل این‌جاست که آن‌ها نمی‌دانند در کدام میدان شهر قرار دارند! جعفر ادعا می‌کند که آن‌ها در میدان $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 ``` ---------- <details class="orange"> <summary> راهنمایی </summary> `dp[i][j]` را برابر جواب سوال وقتی جعفر می‌گوید در راس $i$ هستیم و سلطانی می‌گوید در راس $j$ هستیم قرار می‌دهیم. وقتی $t_i$ و $t_j$ برابر نیستند حاصل دی‌پی برابر ۰ است. با شروع از این پایه ها می‌توان با پیاده کردن الگوریتم $BFS$ این دی‌پی را آپدیت کرد. مشکل این‌جاست که پیچیدگی زمانی این راه حل $n^2$ است، سعی کنید در زمان بهتر راه‌حل را بیابید. </details> <details class="orange"> <summary> راه حل </summary> ابتدا رابطه برابری بین دو راس $v$ و $u$ به این شکل تعریف می‌کنیم که این دو راس از همدیگر قابل تشخیص نیستند. گراف ساده $H$ با $n$ راس را تعریف می‌کنیم به این شکل که اگر دو راس $u$ و $v$ در گراف $H$ به یکدیگر مسیر داشته باشند با هم برابرند. و اگر $u$ و $v$ به هم مسیر نداشته باشند درباره برابر بودن یا نبودن آنها چیزی نمی‌دانیم. در ابتدا فرض می‌کنیم دو راس $A$ و $B$ با هم برابرند. با این فرض، در گراف $H$ باید یک یال بگذاریم. می‌دانیم که با چپ رفتن از دو راس برابر باید به دو راس برابر برسیم. (به همین شکل برای راست رفتن از آن دو راس) پس با فرض برابر بودن $A$ و $B$ به دو نتیجه جدید می‌رسیم. (برابر بودن راس های چپ $A$ و $B$ و همچنین راست آنها) سپس دوباره از نتیجه های جدید، به نتیجه های دیگری می‌رسیم و با هر نتیجه گراف $H$ را آپدیت می‌کنیم. \**لم:** اگر نتیجه جدیدی مانند برابری دو راس $u$ و $v$ کشف کردیم و قبلا می‌دانستیم $u$ و $w$ با هم برابرند، می‌توانیم فرض کنیم نتیجه جدیدمان برابری $v$ و $w$ است و برابری $u$ و $v$ را در نظر نگیریم. با توجه به این لم می‌توانیم به ازای هر مولفه در $H$ تنها یک راس را در نظر بگیریم و بقیه راس ها را حذف کنیم که این کار با داده ساختار $DSU$ به سادگی قابل انجام است. با هر نتیجه، یک راس از گراف $H$ حذف می‌شود. پس ادامه دادن نتایج تا جایی که نتیجه های جدیدی نداشته باشیم، در زمان $O(n)$ امکان‌پذیر است. می‌دانیم که برابر بودن دو راس $u$ و $v$ که از یکی میدان اصلی رشت معلوم است و از دیگری معلوم نیست، تناقض است. پس اگر در نتایجمان به چنین تناقضی رسیدیم، طبیعتاً متوجه می‌شویم که فرض برابر بودن $A$ و $B$ (راس‌های شروع) درست نیست. پس این دو راس از یک‌دیگر قابل تشخیصند. حال می‌خواهیم در کوتاه ترین زمان آنها را از هم تشخیص بدهیم. بدیهی است که این عمل معادل است با اینکه $A$ و $B$ را برابر بگیریم و در کوتاه‌ترین زمان (یعنی مثلا فرض کنید بین دو نتیجه یال جهت‌دار می‌گذاریم) به تناقض برسیم. این کار را می‌توانیم با الگوریتمی شبیه $BFS$ و ساختن نتیجه های جدید از نتیجه های قبلی انجام دهیم، و در هر مرحله که ۲ راس را برابر می‌کنیم در $DSU$ی تعریف شده آن دو را مرج کنیم. </details>

+ محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- فردا تولد حیدریه! به همین دلیل حیدری احساس می‌کند پیر شده و به فکر بازنشستگی افتاده است. اگر حیدری $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 ``` ---------- <details class="orange"> <summary> راهنمایی ۱ </summary> تلاش کنید با باینری سرچ روی جواب (کمینه تعداد روز) جواب را بیابید. هنگام زدن باینری سرچ، یک مقدار $d$ داریم و باید چک کنیم که آیا می‌توان به میزان $M$ سود در $d$ روز رسید یا خیر. در راهنمایی بعدی، روشی برای یافتن این که آیا در $d$ روز می‌توان به هدف رسید را توضیح می‌دهیم. </details> <details class="orange"> <summary> راهنمایی ۲ </summary> فرض کنید می‌خواهیم کار را در $d$ روز تمام کنیم. در این صورت وضوح بهتر است تمام فرصت‌هایی را که سودی که در $d$ روز می‌دهند بیش‌تر از سرمایه اولیه مورد نیاز آن‌هاست،‌ انتخاب کنیم. پس از انتخاب تمام فرصت ها با این ویژگی می‌توانیم چک کنیم که آیا پس از این $d$ روز توانسته‌ایم $M$ تومان سود کنیم یا خیر. </details>

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- فردا تولد حیدریه! حیدری دوستانش را خیلی عجیب انتخاب می‌کند به همین دلیل دوستان او یا روس هستند (`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 ``` ---------- <details class="orange"> <summary> راهنمایی ۱ </summary> ابتدا فرض می‌کنیم میز دایره‌ای شکل نیست و مهمان ها می‌خواهند روی یک خط کنار هم بنشینند. کافیست مسئله را برای این حالت ساده حل کنیم، و سپس برای حالت دایره‌ای روشی بیابیم. در این حالت نشستن نهایی آن ها ۳! = ۶ حالت دارد. (جایگشت های حروف $A$ و $B$ و $C$) پس همه این ۶ حالت را می‌توانیم چک کنیم و جواب بهینه را بیابیم. با داشتن یک جایگشت، با توجه به این که تعداد $A$ و $B$ و $C$ها مشخص است، دنباله‌ی نهایی مشخص خواهد بود. با داشتن دنباله‌ی اولیه و دنباله‌ی نهایی، می‌توان با مشاهده‌ی محل‌های اختلافشان، افرادی که باید جابجا شوند را مشخص کنیم. در راهنمایی بعدی روشی برای حل مسئله برای دایره ارائه می‌کنیم، بصورتی که زمان اجرایش کم بماند. </details> <details class="orange"> <summary> راهنمایی ۲ </summary> برای حل سوال در حالت دایره‌ای در هر یک از ۶ حالتی که در بالا توضیح داده شد، تعیین می‌کنیم حرفی که در اول خط آمده است از آخر خط نیز تا کجا آمده است (تفاوت حالت دایره‌ای به حالت خطی این است که ممکن است یک حرف هم اول خط بیاید هم آخر خط؛ چون در حالت دایره‌ای ابتدا و انتهای خط کنار هم قرار می‌گیرد!) حال اگر برای هر بازه تعداد حروف $A$, $B$ و $C$ را داشته باشیم زمان حل کم می‌ماند. یک بازه روی دایره را می‌توان با شکاندن دایره و تبدیل آن به خط، به یک بازه و یا اجتماع دو بازه تبدیل کرد. پس ابتدا دایره را با اعداد ۱ تا $n$ شماره‌گذاری می‌کنیم. اگر تعداد این حروف را (برای مثال $A$) برای زیر رشته ۱ تا هر $i$ در $dp[i]$ داشته باشیم تعداد این حرف در بازه $l$ تا $r$ به وضوح از رابطه زیر به دست می‌آید: ```c dp[r] - dp[l - 1] ``` روش پر کردن آرایه $dp$ هم می‌تواند به صورت زیر باشد: ```c for i in 1 -> n: dp[i] = dp[i - 1] if s[i] == 'A': dp[i] = dp[i] + 1 ``` </details>

+ محدودیت زمان: ۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- فردا تولد حیدریه! ولی از آن‌جایی که حیدری خیلی ذوق تولدش را دارد تا الان $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 ``` ---------- <details class="orange"> <summary> راهنمایی ۱ </summary> به کمک برنامه‌نویسی پویا جواب سوال را پیدا می‌کنیم. `dp[i][j]` را تعریف می‌کنیم: آیا می‌توان $i$ بار خوش‌حالی کرد و جمع ارزش کادو‌های دریافتی مجموعاً $j$ باشد یا خیر. مقدار این حالت `dp` برابر ۱ است اگر بتوان و در غیر این صورت برابر ۰ است. با کمی دقت می‌توان دیپی را آپدیت کرد. این موضوع در راهنمایی بعدی بیشتر توضیح داده خواهد شد. </details> <details class="orange"> <summary> راهنمایی ۲ </summary> آپدیت دی‌پی به این صورت انجام می‌گیرد که تعیین می‌کنیم کادوی آخری که باز می‌شود از کدام نوع است. به طور مثال می‌توان دی‌پی را به روش بازگشتی شبه‌کد زیر به‌روز کرد! ```c bool update(int tot, int score) { if tot < score: return False if visited[tot][score]: return dp[tot][score] for i in 1 -> M: if score >= price[i]: if update(tot - score, score - a[i]): dp[tot][score] = True visited[tot][score] = True return dp[tot][score] } ``` </details>

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- فردا تولد حیدریه! دوستان حیدری می‌دانند حیدری ۴ عدد مورد علاقه دارد که این ۴ عدد یک خاصیت عجیب دارند: هر کدام از آن‌ها را که انتخاب کنید حتماً از جمع ۳ تای دیگر کوچک‌تر است. (نکته جالب‌تر این که ممکن است در میان این ۴ عدد، عددی تکراری وجود داشته باشد.) به مناسبت تولد حیدری دوستانش می‌خواهند کادوی او را با یک کاغذ کادو به شکل ۴ ضلعی کادو کنند، به طوری که طول اضلاع این ۴ ضلعی برابر ۴ عدد مورد علاقه حیدری باشد. از آن‌جایی که دوستان حیدری می‌ترسند کاغذ کادو کم بیاید به آن‌ها کمک کنید ۴ ضلعی با بیشتری مساحت با این شرایط را پیدا کنند، و این بزرگ‌ترین میزان مساحت را چاپ کنید. # ورودی در تنها خط ورودی ۴ عدد $a$ و $b$ و $c$ و $d$ آمده است که نشان‌دهنده اعداد مورد علاقه حیدریست. $$1 \le a, b, c, d \le 1\ 000$$ # خروجی در تنها خط خروجی یک عدد اعشاری چاپ کنید که نشان دهنده جواب سوال است. توجه کنید تنها در حالتی جواب شما مورد قبول است که دقت آن ۶ رقم اعشار یا بهتر باشد. # مثال ## ورودی نمونه ۱ ``` 3 3 3 3 ``` ## خروجی نمونه ۱ ``` 9 ``` ## ورودی نمونه ۲ ``` 1 2 1 1 ``` ## خروجی نمونه ۲ ``` 1.299038105676658 ``` ## ورودی نمونه ۳ ``` 2 2 1 4 ``` ## خروجی نمونه ۳ ``` 3.307189138830738 ``` ---------- <details class="orange"> <summary> راهنمایی ۱ </summary> ابتدا ترتیب اضلاع ۴ ضلعی را مشخص می‌کنیم (تعداد کل حالات کم است) اندازه یک زاویه دل‌خواه را برابر $a$ فرض می‌کنیم، مساحت ۴ضلعی بر حسب تابعی از $a$ قابل محاسب است، و وقتی ماکسیمم است که مشتق آن برابر ۰ شود. پس می‌توانیم این ماکسیمم را با حل معادله مشتق بیابیم! </details>

+ محدودیت زمان: ۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- فردا تولد حیدریه! به همین دلیل دوست حیدری حال ندارد برای این سوال داستان بنویسد. یک عدد را حیدری-تپه‌ای می‌نامیم اگر ارقام آن از چپ به راست تا یک جایی کوچک نشوند (می‌توانند بزرگ شوند و یا ثابت بمانند) سپس از آن‌جا به بعد بزرگ نشوند (می‌توانند کوچک شوند و یا ثابت بمانند). برای مثال اعداد ۱۲۲۳۴۴۲۱، ۱۲، ۳۵۷، ۵۴۱ و ۱۲۳۲۱ حیدری-تپه‌ای هستند ولی اعداد ۱۲۳۲۱۳، ۱۰۱ و ۳۷۳۵ حیدری-تپه‌ای نیستند. به شما $T$ عدد داده می‌‌شود، به ازای هر عدد اگر آن عدد حیدری-تپه‌ای بود تعداد اعداد طبیعی حیدری-تپه‌ای کمتر یا مساوی آن را چاپ کنید و اگر حیدری-تپه‌ای نبود `-1` را در خروجی چاپ کنید. # ورودی در خط اول ورودی $T$ تعداد اعداد داده می‌شود. سپس در $T$ خط بعدی در هر خط یک عدد حداکثر ۷۰ رقمی به شما داده می‌شود. # خروجی در $T$ خط جواب سوال را چاپ کنید. تضمین می‌شود همیشه جواب در متغیر ۶۴-بیتی جا می‌شود. # مثال ## ورودی نمونه ۱ ``` 5 10 55 101 1000 1234321 ``` ## خروجی نمونه ۱ ``` 10 55 -1 715 94708 ``` ---------- <details class="orange"> <summary> راهنمایی ۱ </summary> به کمک برنامه نویسی پویا جواب سوال را پیدا می‌کنیم. `dp[i][j][2]` را تعریف می‌کنیم: چند عدد $i$ رقمی داریم که رقم آخر آن‌ها برابر $j$ است. بعد سوم `dp` نشان‌دهنده آن است که آیا تا به الان کوچک شدن رقم‌های عدد ما آغاز شده است یا خیر. در راهنمایی بعدی، بروز شدن `dp` دقیق‌تر توضیح داده می‌شود. </details> <details class="orange"> <summary> راهنمایی ۲ </summary> برای به‌روز کردن دی‌پی رقم آخر عددمان را فیکس میکنیم. حال اگر در استیتی باشیم که $i$ رقم داشته باشیم و رقم آخر عددمان $j$ تعیین شده باشد با ۲ حالت زیر روبه‌رو هستیم: **حالت اول:** کوچک شدن ارقام عددمان شروع شده است (بعد سوم دی‌پی ۱ باشد) در این صورت دی‌پی ما برابر جمع دی‌پی اعداد $i -1$ رقمی است که رقم آخرشان بزرگ‌تر یا مساوی $j$ باشد. **حالت دوم:** کوچک شدن ارقام اعدادمان شروع نشده است (بعد سوم دی‌پی ۰ باشد) در این صورت دی‌پی ما برابر جمع دی‌پی اعداد $i -1$ رقمی است که رقم آخرشان کوچک‌تر یا مساوی $j$ باشد. در زمان دادن خروجی باید حواسمان باشد تعداد اعدادی که کوچکتر از عدد داده شده هستند را چاپ کنیم! </details>

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- فردا تولد حیدریه! اما حیدری به روز دقیق تولد اعتقادی ندارد و می‌خواهد جوری تولد بگیرد که همه یک عالمه خوشحال شوند. حیدری لیست تاریخ تولد همه دوستانش را دارد و می‌داند که همه دوستانش در جعبه فکر می‌کنند. بخاطر همین همه دوستانش دقیقاً در روز تولد خودشان مهمانی می‌گیرند. تو جهان خارج جعبه‌ی حیدری تقویم میلادی برقرار و امروز ۲۷ اکتبر است. تو این تقویم سال کبیسه وجود ندارد. حیدری *نوتیس* کرده که دوستانش وقتی از مهمانی تولدش خوشحال می‌شوند که زمان زیادی از آخرین مهمانی تولدی که گرفته شده گذشته باشد. بخاطر همین او روزی را انتخاب می‌کند که از آخرین تولد قبل از آن زمان زیادی گذشته باشد. حیدری طبعاً نمی‌خواهد روز تولدش با کسی یکسان شود. هم‌چنین اگر چندین تاریخ وجود داشته باشد که دوستانش به بیش‌ترین حالت ممکن خوشحال شوند، او نزدیک ترین تاریخ به امروز (۲۷ اکتبر!) را برای گرفتن تولد انتخاب می‌کند. اما این تاریخ نباید امروز باشد. .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 ``` ---------- <details class="orange"> <summary> راهنمایی ۱ </summary> چون سال ۳۶۵ روز دارد، می‌توانیم از ۲۸ اکتبر امسال پیش برویم و روز برگزاری مهمانی را انتخاب کنیم، سپس فاصله این روز تا مهمانی برگزار شده قبلی را بیابیم، و بین تمام اعداد به دست آمده روزی را انتخاب کنیم که بیش‌ترین فاصله را با مهمانی قبلی داشته باشد. سعی کنید برنامه راه‌حل را بنویسید که برای این سوال راهنمایی بیش‌تری قرار نخواهد گرفت! </details>

+ محدودیت زمان: ۱.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- فردا تولد حیدریه! حیدری در مغازه‌ش $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 ``` ---------- <details class="orange"> <summary> راهنمایی ۱ </summary> همیشه بهترین حالت این است که اگر جواب سوال $k$ باشد، حیدری $k$ جنس با کم‌ترین قیمت را انتخاب کند. پس برای یافتن بهترین جواب، قیمت اجناس را به صورت صعودی مرتب می‌کنیم و سپس از ابتدا تا جایی پیش می‌رویم که جمع قیمت ۲ جنس با بیش‌ترین قیمت از $X$ کم‌تر باشد. در راهنمایی بعدی شبه کد روند یافتن جواب بیشتر توضیح داده می‌شود. </details> <details class="orange"> <summary> راهنمایی ۲ </summary> خب حالا ابتدا باید قیمت‌ها را به صورت صعودی مرتب کنیم سپس جواب را پیدا کنیم، برای این کار به روش زیر عمل می‌کنیم! ```c sort(prices) ans = n for i in 2 -> n: if prices[i] + prices[i - 1] > X: ans = i - 1 break ``` </details>