بچه ها سوال!

سلام بچه‌ها، خوبین؟
خب همون طور که تو نظرات گفته بودیم، قرار بود بعد امتحانا پست جدید بزاریم! واسه همین چندتا سوال الگوریتم واستون آماده کردیم! سوالا به ترتیب سختی مرتب شدن(البته ممکنه شما سوال سخت تر رو راحت تر حل کنید :دی)
قرار بودش سوالا برنامه نویسی باشن که به دلیل کمبود امکانات به این شکل درومد! پس حتما اگه سوالی رو حل کردید، کدش رو هم بزنید!
خب اینم از سوالا:
۱-  پویا و حاج سعید یه بازی جدید درست کردن، تو این بازی هرکدوم یه عدد تو بازه‌ی ۱ تا ۱۰۰۰۰۰۰۰۰۰ (۱۰ به توان ۹) انتخاب میکنن و پویا اگه عددش بر عدد حاج سعید بخش پذیر باشه می‌بره، حالا می‌دونیم که پویا عدد n رو انتخاب کرده، احتمال این رو به‌‌دست بیارین که پویا برنده بشه( چون حاج سعید از فکر کردن اصلا خوشش نمیاد!!!، عددش رو کاملا تصادفی انتخاب می‌کنه) الگوریتم شما باید از ((O(sqrt(n  باشه (sqrt تابع رادیکال هستش)

۲- حامد و فرنود که به بازی پویا حسودیشون شده بود!!! یه بازی جدید ساختن، تو این بازی n دسته سنگ ریزه قرار داره که توی یه ردیف پشت سر هم چیده شدن و تو هر کدوم حداکثر n تا سنگ ریزه است! حامد و فرنود به ترتیب روی سنگ ریزه‌ها بازی می‌کنن! هر کس تو نوبت خودش می‌تونه از یکی از دو دسته‌ی سمت راست که خالی نیستن(در صورت وجود) مقدار ناتهی مهره برداره. هرکس که نتونه مهره برداره، می‌بازه. چون حامد و فرنود بسیار بسیار باهوش هستن، هر دوشون به طور کاملا بهینه بازی می‌کنن. حالا شما باید تعیین کنید که چه کسی برنده می‌شه. الگوریتم شما باید از(O(n^4 باشه.(این سوال راه حل بهتر هم داره، که یکم سخت می‌شه)!

۳- بعد از مدت کوتاهی بازی‌ای که فرنود درست کرده بود بسیار معروف شد! به خاطر همین علیرضا تصمیم گرفتش که یه سری مسابقات برگزار کنه تا توش ماهر ترین نفرات این بازی مشخص بشن. تو این دوره از مسابقات n نفر شرکت کردن و هر دو نفری دقیقا یه بار با‌هم بازی می‌کنن. یه فرد مثل a برنده حساب می شه، به طوری که به ازای هر فرد دیگه مثل b دنباله‌ای از نفرات مثل

a,x1,x2,...,b

وجود داشته باشه که هر کس(به غیر از b) نفر بعدی تو دنبال رو برده باشه. حالا علیرضا با داشتن اطلاعات بازی‌ها می‌خواد برنده یا برنده‌های مسابقه رو معلوم کنه، اما از اون جا که حال کد زدن نداره (بین خودمون بمونه، بلد نیستش!!!) نتایج تمام بازی‌ها رو به شما می‌ده و از شما می‌خواد که این کارو براش بکنید. الگوریتم شما باید از(O(n^2 باشه.

۴- بعد از این که پویا توی مسابقات برنده شد، به فکر این افتاد که واسه معروف شدن بیشترش، یه بازی جدید بسازه. این بازی رو یه جدول n*n بازی می‌شه(n*n تا مربع هم اندازه و به اندازه‌ی واحد) و پویا مختصات مرکز  n دایره و شعاع آن ها را می‌ده(شعاع‌ و مرکز‌ دایره‌ها لزوما برابر نیستند) و شرکت کننده باید به طور سریع تعداد مربع‌های جدول رو بگه که توی حداقل یکی از دایره‌ها هستن( یه مربع رو می‌گیم توی یه دایره هستش به طوری که مرکزش داخل یا روی اون دایره باشه) و هرکس که سریع‌تر جواب بده، برنده می‌شه.
عمو مایک(میرزایانوو) که توی مسابقات قبلی دوم شده بود(شرکت کننده‌ها نوب بودن!!!)، تصمیم گرفته به هر شکلی این دفعه اول بشه ولی چون اون هم مثل حاج سعید حوصله فکر کردن نداره ، می‌خواد یه برنامه بنویسه که جواب مساله رو تعیین کنه! حالا اگه شما برنامه‌ی این مساله رو ننویسین، حتما در رقابت با عمو مایک بازنده می‌شین و جزو نوب‌ها به حساب میاین!!! به خاطر همین از شما خواسته شده تا یک الگوریتم با ((O(n^2*log(n طراحی کنید که به مساله جواب بده!

نوشته شده توسط علیرضا فرهادی(سابق) در سه شنبه ۲۷ دی۱۳۹۰ و ساعت 23:7 |