Challenger

المپیاد کامپیوتر , الگوریتم , برنامه نویسی , ترکیبیات , گراف , ....

Challenger

المپیاد کامپیوتر , الگوریتم , برنامه نویسی , ترکیبیات , گراف , ....

Challenger
طبقه بندی موضوعی
پیوندهای روزانه

۳ مطلب در اسفند ۱۳۹۱ ثبت شده است

۳۰اسفند

محمد مهدی جهان آرا
۰۵اسفند

پوستر مسابقات


(پنج‌شنبه 17 اسفند ) :
اولین دوره ی مسابقات بازی‌ریاضی یزد به همت بچه های دانشگاه یزد و کمک دانش آموزای مدرسه‌ی شهید صدوقی برگزار شد. هرچند به دلیل کم تجربگی ما ضعف هایی در برگزاری مسابقه‌ی دانش آموزی وجود داشت ولی امیدوارم شرکت در مسابقه برای همه‌ی تیم ها تجربه‌ی خوبی بوده باشه.
در نهایت تیم "کهکشانی ها" رتبه اول و تیم "Mohadisa" رتبه‌ی دوم بخش دانش‌آموزی رو کسب کردن که تلاششون واقعا قابل تقدیره ! :)

انشاا... سال های بعد مسابقه را بهتر و جذاب تر دوباره برگزار کنیم.
محمد مهدی جهان آرا
۰۳اسفند

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

 سوال می گه که یه ساختمون 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

بنیامین دلشاد