بچه ها سوال!

سلام بچه‌ها، خوبین؟
خب همون طور که تو نظرات گفته بودیم، قرار بود بعد امتحانا پست جدید بزاریم! واسه همین چندتا سوال الگوریتم واستون آماده کردیم! سوالا به ترتیب سختی مرتب شدن(البته ممکنه شما سوال سخت تر رو راحت تر حل کنید :دی)
قرار بودش سوالا برنامه نویسی باشن که به دلیل کمبود امکانات به این شکل درومد! پس حتما اگه سوالی رو حل کردید، کدش رو هم بزنید!
خب اینم از سوالا:
۱-  پویا و حاج سعید یه بازی جدید درست کردن، تو این بازی هرکدوم یه عدد تو بازه‌ی ۱ تا ۱۰۰۰۰۰۰۰۰۰ (۱۰ به توان ۹) انتخاب میکنن و پویا اگه عددش بر عدد حاج سعید بخش پذیر باشه می‌بره، حالا می‌دونیم که پویا عدد 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 |

نتایج آمد!

سلام!

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

به هر حآل تو این آزمون 448 نفر و 32 مدرسه شرکت کردند. مرسوم ه که همیشه نمره ی بهترین فرد اعلام میشه ولی خب من اول این رو بگم که نفر آخر این امتحان تونست یه رکورد بزنه و -29 بشه! یعنی همه تست ها رو غلط بزنه! (مطمئن باشید از قصد کرده :دی) لیست نفرات برتر رو هم می تونید از اینجا ببینید.

سطح سوالات امتحان هم یه کم سخت تر از مرحله 1 واقعی بود و میانگین شرکت کننده ها 21 درصد بود.

برای دیدن نتایج هم ما تا فردا رمز عبور رو به میلتون می فرستیم و با وارد شدن در این سایتمی تونید نتیجه خود را ببینید.

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

گله یا شکایت (!!!) : ما قرار بود 8 نفر برتر رو اعلام کنیم ولی نفر 8ام از علامه طباطبایی بود . از اونجایی که اسامی جعلی به جای اسامی دانش آموزان به ما داده شد تا فقط خود مدرسه بتونه تشخیص بده دانش آموزانش چه عملکردی داشتن و برای ما و خود دانش آموزان مقدور نباشه، 7 نفر برنر اعلام شدند!

نکته : اگر همچنان علامه طباطبایی به همکاری نکردن پافشاری کرد، دانش آموزان این مدرسه کافیست پاسخ نامه ی خود را به شاززز میل کنند تا کارنامه ی ایشان مستقیما به خودشان و نه به مدرسه، داده شود.

از همه ی مسئولین و مدارسی که با ما همکاری کردند و دانش پژوهانی که این امتحان رو دادند و نیز از دوستانی که صبر کردند تا اعلام نتایج ، سپاس گذاریم!

خب حدود یک ساعت از سال 2012 گذشته ، امیدوارم که سال خوبی باشه براتون!

موفق باشید!

---

رمز های عبور به میل شرکت کننده ها ارسال شد.

(ممکنه spam شده باشه! spam رو هم چک کنید!)

(اگه هنوز نشده هم بگید!)