n خان رستم

سلام، این سوال رو فعلن داشته باشید، بعدن راه حل و توضیحات رو اضافه می‌کنم. :)

رستم می‌خواد «n-خان رستم» رو پشت سر بذاره تا برای خودش اسطوره‌ای بشه. برای این کار باید به ترتیب خان یکم تا خان n-ام رو پشت سر بذاره. در خان i-ام باید از پس اژدهای i-ام بر بیاد. قدرت اژدهای i رو با p_i نشون می‌دیم. قدرت هر اژدها یه عدد صحیح مثبته. رستم تو خان i می‌تونه به اژدها مقدار c_i تومن رشوه بده و اینطوری اون اژدها همدست رستم می‌شه و دیگه باهاش نمی‌جنگه. اژدها‌ها زیاد دنبال پول نیستن، در نتیجه هر اژدها یا ۱ تومن یا ۲ تومن رشوه می‌خواد. اگه رستم به اژدهای i-ام رشوه نده اون موقع باید با اون اژدها بجنگه. اژدها در صورتی تو مبارزه با رستم و همدستاش پیروز می‌شه که قدرتش از مجموع قدرت اژدها‌های همدست رستم بیشتر باشه. قدرت خود رستم تاثیری تو مبارزه نداره. حالا رستم می‌خواد با کمترین هزینه n-خان رستم رو پشت سر بذاره. الگوریتمی از O(n^۲)  بدید که کمترین هزینه‌ای که رستم باید از جیبش بده رو حساب کنه. واضحه که رستم باید حتمن به اژدهای خان یکم رشوه بده،‌ چون در ابتدا قدرتی نداره.

به روز رسانی: راه حل و توضیحات اضافه شد. (۱۸ دی ۹۱) (۹ دی ۹۱)

مساله «جاده‌ها»

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

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

می‌دانیم N از ۲۰،۰۰۰ بیشتر نیست. همچنین M‌ حداکثر ۱۰۰،۰۰۰ است و K بین ۰ تا N-۱ می‌باشد.

مساله «طولانی‌ترین دنباله»

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

یک آرایه C از اعداد صحیح ناصفر به شما داده می‌شود. هر عضو C یکی از شرط‌ها را تعیین می‌کند.

اگر C_i مثبت بود مجموع هر C_i عضو متوالی از دنباله باید مثبت باشد.

اگر C_i منفی بود مجموع هر -C_i عضو متوالی از دنباله باید منفی باشد.

طول بلندترین دنباله‌ای را حساب کنید که همه‌ی این شرایط را دارد. اگر طول دنباله محدودیتی ندارد طولش را -۱ در نظر بگیرید.

می‌دانیم تعداد اعضای C از ۵۰ بیشتر نیست و هر عضو C بین -۱۰۰۰ و ۱۰۰۰ است و با صفر فرق می کند.

مساله «آرایه قوی»

دنباله a_۱, a_۲, ..., a_n به شما داده شده است. زیردنباله a_L, ..., a_R را از این دنباله در نظر بگیرید. K_s برابر با تعداد بارهایی است که عدد s در این زیر دنباله ظاهر شده است. قدرت عدد s برابر است با K_s.K_s.s. قدرت زیردنباله برابر با مجموع قدرت تمام اعداد طبیعی است (چون تعداد اعداد دنباله محدود است قدرت زیر دنباله نیز محدود است). دنباله a_۱, a_۲, ..., a_n به شما داده می‌شود. شما باید در تعدادی پرسش مقدار L و R را دریافت کنید و قدرت زیردنباله a_L, ..., a_R را چاپ کنید. می‌دانیم تعداد پرسش‌ها و تعداد اعداد دنباله از ۲۰۰،۰۰۰ بیشتر نیست. همچنین هر عضو دنباله بین ۱ تا ۱۰۰۰،۰۰۰ است.

مساله «عکاسی از گاوها»

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