جهان در زندان!
شاید عجیب باشه که من سوال الگوریتم بدم ولی ببخشید دیگه به بزرگی خودتون. این سوال چندان سخت نیس ایده ی ساده ای داره واسه آزمون المپیاد لهستانه ولی سر ازمونش افراد کمی زدنش. من سوالو می گم راه حلشم احتمالن چن روز بعد می زارم.
سوال می گه که یه ساختمون n طبقه داریم. جهان تو یه طبقه اش زندانی شده. در هر مرحله می تونیم یکی از سوالات زیر رو بپرسیم و زندانبان که دم در ساختمون وایستاده جواب رو بهمون بگه. همیشه هم راست می گه ولی خب آدم پولکی ایه. بابت هر سوالی که جوابش بله باشه a دلار و بابت هر سوالی که جوابش نه باشه b دلار می گیره. جهان برامون خیلی ارزشمنده باید پیداش کنیم پس حاضریم این مبلغ رو بپردازیم ولی خب ما می خواییم با کمترین هزینه بفهمیم جهان تو طبقه چندمه ( :-فکر اقتصادی) :D
سوال نوع یک. آیا جهان در طبقه i ام و بالاتر است؟ (i عدد دلخواه بین 1 تا n)
سوال نوع دوم. آیا جهان در طبقه i ام و پایین تر است؟ (i عدد دلخواه بین 1 تا n)
n <= 1000000000
a <= 10000
b <= 10000
راه حل: (افزوده شده در 15 اسفند)
یک داینامیک ساده می زنیم! ابتدا یه سقف برای جواب در نظر می گیریم. فرض کنیم همون باینری سرچ عادی رو بزنیم. با خرج کردن حداکثر max(a,b) * lgn دلار به جهان می رسیم(در بدترین حالت) :D که این مقدار حداکثر برابر 300000 هست!
dp[i]
را برابر بیشترین تعداد طبقاتی قرار می دهیم که با i دلار هزینه بتونیم جهان رو توش پیدا کنیم! جواب برابر است با اولین i ای که:
dp[i] >= n
و این داینامیک این گونه آپدیت می شه:
dp[i] = 2 * min(dp[i - a], dp[i - b])
:)
پ.ن: سوال یه راه حل واضح با اردر n^2 داره که خب مسلمن قابل قبول نیست :D
پ.ن2: من واقعن نمی تونم رسمی پست بنویسم :-" بازم به بزرگی تون ببخشید :D
پ.ن3: روز نیکوکاری (14 اسفند) و درختکاری رو بهتون تبریک می گم :D
ابوالفضل اسدی
