Challenger

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

Challenger

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

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

۶ مطلب با موضوع «الگوریتم» ثبت شده است

۰۳اسفند

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

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

بنیامین دلشاد
۳۰بهمن

Open Data Structures کتابی فوق العاده در مورد داده ساختار‌ها با پیاده سازی ++C !

محمد مهدی جهان آرا
۳۰بهمن

سلام


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


دریافت
حجم: 258 کیلوبایت
توضیحات: فینال دومین مسابقه‌ی برنامه نویسی بیان

موفق باشید !
محمد مهدی جهان آرا
۱۵دی

سلام

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

هفته ی آینده هم سری بعدی سوالات هفتگی و پاسخ این سری به همراه اسامی کسانی که به سوالات پاسخ درست دادند روی وبلاگ قرار میگیره .


پرسش هفته - 1
حجم: 93.4 کیلوبایت


موفق و سربلند باشید .


اصلاحیه سوال سه:

در این سوال جواب دقیقن یک عدد بین 1 تا 5 است و این اعداد از هم مستقل اند. ینی اگر 3 بلور لازم باشد 1 بلور لازم نیست.(برای درک بهتر می تونید رنگ در نظر بگیرید اینارو.)


محمد مهدی جهان آرا
۲۶خرداد

شرح مساله(ویکی پدیا) :

« در نظریه گرافها، یک مرتب سازی موضعی یا ترتیب موضعی یک گراف بدون دور جهت دار، یک ترتیب خطی از همه رئوس آن است به طوری که هر گره قبل از همه گره‌هایی می‌آید که از آن به آنها یال خارج شده است. »

 

شرح الگوریتم : 

در هر مرحله می توانیم راس هایی را که هیچ یال ورودی ایی ندارند را در لیست قرار بدهیم

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

محمد مهدی جهان آرا
۱۶بهمن

Longest common subsequence

شرح مساله(ویکی پدیا) :

دو رشته زیر را در نظر بگیرید:


S_{1}=ACCGGTCGAGTGCGCGGAGCCGGCCGAA\,\!


S_{2}=GTCGTTCGGAATGCCGTTGCTCTGTAAA\,\!

هدف مقایسه این دو رشته و پیدا کردن شباهت بین آنها است. بزرگترین زیردنباله مشترک این طور تعریف می‌شود که دنباله‌ای مانند S_{3} است به طوری که حروف موجود در S_{3} با حفظ ترتیب در S_{1} و S_{2} موجود باشد. اما مطلقاً لزومی ندارد که متوالی باشد. از طرفی S_{3} باید بزرگترین دنباله ممکن با خواص بالا باشد. به طور کلی اگر دو رشته X=\langle x_{1},x_{2},... ,x_{n}\rangle و Y=\langle y_{1},y_{2},... ,y_{n}\rangle را در نظر بگیریم٫ یک بلندترین زیر دنباله مشترک را می‌توان با استفاده از برنامه نویسی پویا پیدا کرد.

محمد مهدی جهان آرا