آزمون شماره دو

سلام!
خب همون طور که گفته بودیم، قراره این پنج شنبه هم آزمون بگیریم، آزمون این دفعه یکم نسبت به قبلی فرق کرده، تعداد سوالاتش شده ۴تا و وقتش رو هم کردیم ۲:۳۰ ساعت.
آزمون ساعت ۴ بعدازظهر به وقت تهران شروع می‌شه و به محض شروع آزمون سوالا هم روی سایت قرار می گیرن،اگه آزمون قبلی رو ندادین، لازمه برین اینجا ثبت نام کنید.

موفق باشید!

---

امتحان شروع شد سوالا رو میتونین از اینجا دانلود کنین.

امتحان تموم شد نتیج رو میتونین از اینجا ببینین.

راه حل ها هم آماده شد میتونین از اینجا دانلود کنید.

کد ها رو میتونین از آرشیو دانلود کنین. (فایل contest2-solutions.zip )

امتحان بعدی هم که آخرین امتحان ه ۵ شنبه هفته بعد برگزار میشه یادتون نره :)

مرحله ۲ نزدیکه ...

سلام!!

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

خوب خیلیا خوشحال شدن چون تستی چیز بدی بود مخصوصا برای کسایی که کلی نوشتن سوال تمرین کردن و می ترسیدن از این که تو تستی گند بزنن و برگه هاشون اصلا نگاه نشه! کلا هم این که برگه نگاه نشه خیلی بده دیگه چون بالاخره هر کی یه روز بد داره ولی احتمال این که هر دو روز رو بد شانسی بیاره پایینتره.

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

یه متن هم هست آقای اسفندیاری در مورد درست نوشتن نوشته که حتما بخونید!

ce.sharif.edu/~esfandiari/INOIwriting

در ضمن راهنمایی سوالای قبلی هم تو ادامه مطلب گذاشتیم :)

خوش باشید!

ادامه نوشته

بچه ها سوال!

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

سری دوم

سلام!!!

خوبین؟ :دی

سوالای دو هفته قبل خوب بود؟ حلشون کردید؟

خب سوالای این هفته هم آمادست، فقط چندتا نکته وجود داره:

۱- تقریباً استقبال از دفعه‌ی قبل کم بود ، اگه بخواد همین‌جوری پیش بره، ما دل سرد می‌شیم و مجبوریم ۱+۳ رو متوقف کنیم ( شاید این آخریش باشه :( )

۲- من یه عده‌ی زیادی رو دیدم که سوالا رو حل می‌کنن ولی نمیفرستن برای ما، خوب چرا؟ ما فقط قصدمون این که طرز نوشتنتون خوب بشه وگرنه سوال واسه حل کردن زیاده!مطمئن باشید اگه راه حل غلط باشه،نمی‌خندیم بهش! پس از فرستادن جواب نترسین!

۳- دوستان زحمت کشیدن راه‌حل سوالای قبلی رو آماده کردند که می‌تونید دانلودش کنین! فقط راه حل سوال ۱+ رو نیاوردیم تا بیشتر سرش فکر کنین ;)

۴- بازم مثل دفعه‌ی قبل باید جواباتون رو به آدرس sh44zzz[at]gmail[dot]com میل کنین!

همین دیگه! خوش باشید ... :)

---

جواب‌های سری اول

سوالات سری دوم

(صورت سوالات سری دوم به علت جا افتادن یک شرط از سوال ۱+ اصلاح شد! دوباره دانلود کنید!)