آزمون مرحله 3

سلام!

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

قراره یه سری امتحان به سبک مرحله 3 برگزار کنیم. چون داریم به مرحله 3 نزدیک می شیم پس باید براش آماده بشید حتی اگر امتحان ترم 2 دارید ، چون دیگه بعد امتحان ها وقت زیادی ندارید.

درباره ی خود آزمون ها باید بگم که هر آزمون 3 تا سوال داره و زمانش هم 2 ساعت ه . آزمون ها در روز های پنجشنبه ساعت 4 بعد از ظهر شروع میشه.

آزمون ها رویhttp://sh44zzz.gigfa.com/m3برگزار میشه . یه سری سوال هم به عنوان تمرین قراره رو سایت باشه که میتونید حل کنید و سابمیت کنید. 

سایتhttp://goharshady.blog.irهم آزمون میگیره که خب میتونید آزمون های اون جا رو هم شرکت کنید.  

موفق باشید!

---

‌‫حامد:‌ حامد ولیزاده و سعید و علیرضا و محمدرضا ملکی هم تیم شدن! وقت نشد پست بزنیم براشون از همین جا بهشون تبریک می گیم ایشالا با ۴ تا طلا از ایتالیا بر می گردن :)

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

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

---

امتحان اول امروز ساعت ۴ بعد از ظهر شروع میشه و طولش ۲ ساعته اگه هنوز ثبت نام نکردید دراینجاثبت نام کنید. وقتی مسابقه شروع شه سوالا از روی سایت مسابقه و وبلاگ قابل دسترس ه. در حین امتحان میتونین در سایت سابمیت کنید و نتیجه آن را ییینید. نتایج نهایی بعد امتحان اعلام می‌شه.

پ.ن:‌ساعت سرور خرابه. امتحان راس ساعت ۱۶:۰۰ رسمی شروع می‌شه. می تونین ازاینجاببینین ساعت رسمی رو!

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

نتایج امتحان اول آماده است میتونین ازاینجاببینین.

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

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

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

پاسخ سوالات مرحله ۲

سلام!

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

ما هم جواب سوالا رو با کمک حامد ولیزاده و سامان سامی و دانیال مهرجردی آماده کردیم براتون. امیدوارم به دردتون بخوره ;-)

فعلا الان میتونید جوابای روز ۱ رو ازاینجادانلود کنید.صورت سوالات

سوالای روز ۲ رو هر هروقت آماده شد می‌زاریم!آماده شد میتونید ازاینجادانلود کنید.صورت سوالات

خدافظ!

!!!! از مرحله ۳ هم غافل نشیدا! حتا اگه بد دادین! یهو دیدین معجزه شد. قبول بشین سر مرحله ۳ بیفتین بدتره!

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

۱- بزرگترین مجموعه مستقل گراف شهر‌ها رو در نظر می‌گیریم، اندازه‌ی این مجموعه مستقل حداکثر می‌تونه ۱۰ باشه. چون این مجموعه مستقل بیشینه هستش، پس هر راس خارج از اون، حداقل ۱ یال به مجموعه مسقل داره. پس حداقل ۹۰ یال به مجموعه مستقل وارد شده. حالا اگه این مجموعه مستقل رو از گراف حذف کنیم،یه گراف ۹۰ راسی باقی می‌مونه که بازم خواص گراف اولیه رو داره. پس اگه مجموعه مستقلش رو در نظر بگیریم، حداقل ۸۰ یال بهش وارد شده. اگه همین کارو ادامه بدیم، بدست می‌یاد که گراف حداقل

90+80+70+...+10=450

یال داره. می‌شه یه گراف ساخت یه دقیقا همین قدر یال داشته باشه، مثلا اگه ۱۰ تا K10( گراف کامل ۱۰ راسی) کنار هم بزاریم، یه گراف ساخته می‌شه که خواص گفته شده تو مسئله رو داره و ۴۵۰ تا یال داره.

۲- اعداد ۱،۲،۴،۸،۱۶ رو کنار می‌گزاریم. حالا واسه‌ی هر انتخاب از ۹۵ عدد باقی مونده، بود یا نبود این ۵ عدد با توجه به باقی‌مانده‌ی آن بر ۳۲ به طور یکتا تعیین می‌شه( چرا؟) پس جواب مسئله می‌شه ۹۵^۲.

۳- حکم رو با استقرا بر روی i+j اثبات می‌کنیم. پایه به ازای i+j=0 طبق گفته‌ی مسئله درسته! حالا فرض کنید، می‌خوایم حکم رو واسه خونه‌ی (i,j) ثابت کنیم و می‌دونیم به ازای هر خونه‌ی (x,y) که x+y

i xor k = i xor j -> k = j (چرا؟؟)

حالا فقط لازمه بگیم که تمام اعداد کوچیکتر از i xor j، توی سطر یا ستونش اومدن
برای این‌کار فرض کنید، می‌خوایم عدد 

k

رو بسازیم، برای این می‌یایم رقم های i و j رو در مبنای ۲ از سمت چپ پیمایش می‌کنیم. اولین خونه‌ی رو در نظر بگیرید که xor اون رقم توی i و j برابر k نمی‌شه،حتما یکی از بیت های دو عدد، تو این رقم ۱ هستش( چرا؟) بعد می‌یام یکی از اون یک هارو انتخاب می‌کنیم و ۰ اش می‌کنیم و توی رقم های بعد، هر وقت مشکلی پیش اومد، رقم این عدد رو تغییر می‌دیم تا درست بشه. توی راهی که گفته شد، دقیقا یکی از اعداد تغییر می‌کنه و عدد تغییر کرده حتما کوچیک‌تر از مقدار اولیش می‌شه(چرا؟). پس متناظر با یکی از خونه‌های هم سطر یا ستونشه. پس حکم اثبات شد.

۴- یک گراف ۱۰۰ راسی درست می‌کنیم که در آن هر راس نشان‌گر یک عدد است. حالا واسه هر دو عدد که جمعشون گویا می‌شه، یک یال بین رئوسشون می زاریم.حال ادعا می‌کنیم که گراف درست شده، دور فرد ندارد. فرض کنید یک دور فرد شامل راس‌های

x1,x2,....,x(2k+1)

در آن پیدا کردیم. طبق نحوه‌ی ساخت گراف، می‌دونیم که تمام جمع‌های زیر گویاست:
x1+x2
x2+x3
.
.
.
x(2k+1)+x1
پس عبارت زیر نیز گویاست:
(x1+x2)-(x2+x3)+(x3+x4)-.....-(x(2k)+x(2k+1))-(x(2k+1)+x1)
از طرفی مقدار این عبارت برابر 

-2x(2k+1)

می‌شه، که گویا بود اون نتیجه می‌ده که خود (x(2k+1 گویاست، که تناقضه. چون گراف مورد نظر دور فرد نداره، پس ۲ بخشی هستش. پس حداقل یک بخش آن وجود داره که شامل ۵۰ راس باشه.

سوال

سلام!

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

1- به تازگی قراره که تو شاززز آباد جاده کشی شه. میدونیم که شاززز آباد 100 تا شهر داره و یک نوع جاده کشی مطلوبه اگه هر 11 تا شهرو که در نظر بگیریم حداقل 2 تا باشن که بینشون یه جاده هست ، حالا ثابت کنید َیک جاده کشی مطلوب حداقل 450 تا جاده دارد. یک مثال هم بزنید که شامل دقیقا 450 جاده است.

2- علی کلید که متخصص باز کردن گاوصندوقه ، جدیدا به یه گاوصندوق برخورده که زیاد عادی نیست. رمز این گاوصندوق یک عدد ه (خب این که عادیه :) ) ولی نکته ای که هست اینه که این رمز ، جواب این مساله است که روی گاوصندوق حک شده : « تعداد زیرمجموعه های {100,...,1,2,3} را بیابید که مجموع اعضای آن بر 32 بخشپذیر باشد. » حالا شما به علی آقا کمک کنید تا بتونه کاوصندوق رو بازکنه و به پاداشش برسه ، یه بخشیش رو هم میده به شما.

3- علی کلید باز به یه گاوصندوق عجیب رسیده. این گاوصندوق این طوریه که 100 تا سوال به این شکل میپرسه. « بیتینگ جفت (i , j) چند است ؟ » میدانیم بیتینگ (0,0) مساوی 0 است. و برای سایر جفت ها به این شکل محاسبه می شود : کوچکترین عددی که در بیتینگ هیچ کدام از جفت های (i,0) , (i,1) , ... , (i,j-1) و  (i-1,j) ، .... ، (1,j) ، (0,j) نیامده است. به دلیل زمانبر بودن محاسبه ی این کار علی آقا حدس میزند که بیتینگ (i , j) مساوی است با i xor j است. اما این تنها یک حدس است به او کمک کنید که درستی یا نا درستی حدسش را بفهمد.

4- تقی و نقی دوقلو ان. تقی المپیاد ریاضی و نقی المپیاد کامپیوتر. یه روز که نقی دنباله سوال بوده از تقی یه سوال ترکیبیات میخواد. تقی هم این سوال رو میده :

« 100 تا عدد گنگ داریم. ثابت کنید 50 تاشون هستند که جمع دو به دو ی آنها گنگ ست. »

نقی وقتی سوال رو میشنوه میگه من گفتم ترکیبیات نه جبر و تِنظریه اعداد که! تقی هم بلافاصله جواب سوال رو میگه و معلوم میشه که سوال واقعا ترکیبیاته. حال شما مثل نقی عمل نکنید و رو سوال بدون این که فکر کنید  ریاضویه فکر کنید.

---

رور اول مرحله دوم ، تشریحیه ، میتونید خوشحال باشید!منبع خبر  هم کاملا موثقه.

بالاخره اومد !

سلا م

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

۱. ببینین بچه ها ، هر سال ۱ سری از بچه هایی که طلا گرفته بودن میومدن می گفتن مهم نیست قبول نشدن و این حرفا و خوب شما [و ما] هم می گفتیم خوب اینا که دیگه طلا شونو گرفتن و از این حرفا ... !
اما من الان به عنوان ۱ آدمی که نزدیک کنکوره دارم حرف میزنم .

اول از همه بدونین که اگه هدفتون صرفا دانشگاه رفتنه و به المپیاد به دید ۱ پل نگاه می کنین ، مطمئن باشین که کنکور خیلی خیلی راه ساده تریه .

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

پس مثل بچه آدم برین مرحله ۲ و ۳ و ... بدین ، فارق از اینکه قبول می شین یا نمی شین .

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

پس مطمئن باشین سوالای مرحله ۲ در حدیه که می تونین حلشون کنین و هیچ وقت سوالای فضایی نمیدن ! (-;

۳. دید آدم به امتحان و سوالا خیلی مهمه ،
اگه ۱ سوال خیلی ساده رو بزارن جلوی آدم و بگن این سوال open ه ، به احتمال خیلی زیاد حلش نمی کنه .
این چیزیه که باعث میشه سر امتحان آدم سوالایی که بلده رو هم حل نکنه .
چون ۱ غول از مرحله ۲ ساخته برای خودش .
اما اگه دید این باشه که همه ی سوالای مرحله ۲ رو من می تونم حل کنم ، مطمئنا خیلی نتیجه بهتری گرفته میشه .
به نظر من اهمیت این دید و اعتماد به نفس از چیز بلد بودن خییلی بیشتره .

پس سعی کنین از امروز قبول کنین که هیچ سوالی نیست که نتونین حل کنین و با این دید به سوالا نگاه کنین .

***
با وجود همه ی این حرفایی که من زدم بازم همون آشه و همون کاسه ،‌ فکر نکنین خوب حالا همه همینطور نگاه می کنن به مرحله ۲ ، نه ! D:

در ضمن از مراحل بعدی و کد زدن و اینام غافل نشین .

سوالای مرحله ۲ های سالای قبل رو هم حتما از خودتون امتحان بگیرین . (لینک سوالای سالای قبل)

همچنین قراره ۱ سری سوال هم به زودی گذاشته بشه که آمادس !

موفق و سربلند و پیروز و از این حرفا باشین و تعطیلات خوش بگذره

---

راستی سایتinoiیه پست جدید گذاشته ، اگه ببینیدش بد نیست

کلید مرحله ۱

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

امسالم با بچه ها نشستیم کلید آزمون رو در اوردیم(بچه ها = ما و حامد ولیزاده و سامان)اگههمفک می کنین سوالی غلط ه، حتما بگین!

همین دیگه موفق باشین ؛-)

بعضی سوالا اشتباه وارد شده بود، کلید به روز شد!(سوال ۲۷ هم دوباره اصلاح شد!)

کد ۱:

اگه عکس نمیاد ازاین لینکببینید!

کد ۲:

اگه عکس نمیاد ازاین لینکببینید!

---

// بعدا نوشت :: بچه ها لطفا خربازی در نیارین ! D:
// آخه اگه قرار بود ۳۰۰ نفر مرحله اول انتخاب شن ، قطعا توی بخشنامه ها می نوشتن که به مدارس ابلاغ شده ، یا تو سایت می نوشتن . تازه اونم قبل از امتحان .
// بعدشم نظر سنجی و اینا کلا کشکه ، ولش کنین ! D:
// هر سال نظر سنجی که می زاشتن کف میشد ۱۰ مثلا اما هیچ وقت کف بیشتر از ۷ نبوده تا حالا . امسال هم فکر نمی کنم باشه . (-;

جواب سوال

سلام

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

1- در واقع برای حل این سوال اگر عدد حاج سعید یکی از مقسوم علیه های عدد پویا باشد، پویا برنده است و در غیر این صورت حاج سعید. حال اگرd(x) را مساوی تعداد مقسوم علیه هایxتعریف کنیم ، بنابراین جواب مساله می شود.d(n)/10^9پس در واقع الان بایدd(n)را درO(sqrt(n))حساب کنیم . برای این فرض کنیدn=a*b که(aدر این صورتaاست (چرا؟).پس اگر ما مقسوم علیه های کوچکتر از n را در ((O(sqrt(n حساب کنیم. سایر مقسوم علیه ها هم پیدا می شوند.

کد سوال

      2- برای حل این سوال از برنامه ریزی پویا استفاده می کنیم.

Win[i][j][k]: بازی را کهi دسته ی سمت چپ تا حالا دست نخورده باشند و سپس یک دسته باjسنگریزه داشته باشد و بعد از آن یک دسته باkسنگریزه در نظر بگیرید. حالWin[i][j][k]یک است اگر نفر اول ببرد و در غیر این صورت صفر است.

حال بعد از این تعریف برای بروزرسانی کردن می توانید 3 مجموعه ی زیر را در نظر بگیرید.        

A={Win[i][j][1] , Win[i][j][2], … , Win[i][j][k-1]}

B={Win[i][1][k], Win[i][2][k], … , Win[i][j-1][k]}

C={Win[i-1][a[i]][j], Win[i-1][a[i]][k]}

حال اگر همه ی اعضای A ,B, C یک بود،Win[i][j][k]=0ودر غیر این صورت یک. (چرا؟). 

نکته : با استفاده از ارایه ی کمکی زمان الگوریتم را بهO(n^3)قابل کاهش است.

کد سوال

 

3-   3- ابتدا تعاریف زیر را در نظر بگیرید :

تورنمنت : به هر گراف جهت داری که بین هر دو راسش دقیقا یک یال جهت دار باشد ، می گوییم.

پادشاه : در گراف جهت دار به راس هایی که به تمامی راس های دیگر با فاصله حداکثر دو مسیر دارند ، پادشاه می گوییم.

لم : هر تورنمنت حداقل یک پادشاه دارد.

اثبات : ثابت می کنیم در یک تورنمت راس با درجه ی خروجی بیشینه پادشاه است. راسvرا راس با این خاصیت در نظر بگیرید. حال سایر راس ها را به دو دسته یAوBتقسیم کنید که دسته یAراس هایی هستند که از راسvبه آنها یال وارد شده است و دسته یBراس هایی که از آنها بهvیال وارد شده است. واضح است که چون گرافمان تورنمنت است هر راس جزvیا درAاست یا درB. حال یک راس ازBمانندuرا در نظر بگیرید. اگر راسی مثلwوجود داشت که  (w->u)پس مسیر(v->w->u)یک مسیر به طول دو ازvبهuاست. اگر هیچ راسی مثلwنباشد در این صورت یعنیu به همه ی اعضایAیال خروجی داشته است و چون یال(u->v)را هم داریم پس درجه ی خروجیuحداقل یکی بیشتر ازvاست که این با فرض ما در تناقض است. پسvبه هر راس ازBمسیری به طول دو و به هر راس ازAمسیری به طول یک دارد . پس حکم اثبات شد.

حال به حل مساله ی اصلی می پردازیم. صورت گرافی مساله می شود:

« در یک تورنمنت تمامی راس هایی را بیابید که به همه ی راس های دیگر مسیر دارند.»

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

کد سوال

      4- برای راحتی کار به مربع های داخل دایره سیاه و به بقیه سفید می گوییم.

حال ما برای این که تعداد خانه های سیاه جدول را بشماریم می توانیم تعداد خانه های سیاه هر سطر را حساب کنیم و سپس حاصل جمع را چاپ  کنیم. اگر بتوانیم تعدد خانه های سیاه هر سطر را درO(n*log(n))حل کنیم با توجه به این کهnسطر داریم پیچیدگی کل مسالهO(n^2*log(n))می شود که همان چیزی است که مساله می خواهد.

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

دایره یiام را در نظر بگیرید. اگر چپ ترین و راست ترین خانه ی این سطر که توسط این دایره سیاه شده اند را به ترتیبL[i]  وR[i]بگیریم.(ستون ها را با 1 تاnاز چپ به راست شماره گذاری کنید.) واضح است که تمامی خانه های بینL[i]وR[i]نیز سیاه می شوند. حال اگر اکنون به هر دایره بازه ی[L[i],R[i]]را نسبت دهیم باید تعداد اعداد داخل کل اینnبازه را به دست آوریم.

برای این ، بازه ها را به صورت اجتماع این بازه ها را ، به صورت چند بازه ی بدون اشتراک حساب می کنیم و سپس اندازه ی بازه های جدید به دست آمده را با هم جمع می کنیم تا به عدد مطلوب برسیم.

حال برای این که اجتماع اینnبازه را به صورت تعدادی بازه ی بدون اشتراک بنویسیم به صورت زیر عمل میکنیم:

بازه ها را بر حسب ابتدای شان مرتب میکنیم. سپس از ابتدا روی بازه ها شروع به حرکت می کنیم. فرض کنید الان روی بازه یiام هستیم و اجتماعi-1بازه ی قبلی به درستی حساب شده اند. حال اگر بازه یiرا در نظر بگیرید این بازه فقط می تواند روی آخرین بازه ی اجتماعi-1بازه ی اول تغییر ایجاد کند. در این صورت اگر انتها ی آخرین بازه قبل از شروع بازه یiبود ، اجتماعiبازه ی اول میشود اجتماعi-1بازه ی اول و بازه یi. در غیر این صورت بازه ی آخر اجتماعi-1بازه را به روز رسانی میکنیم.

کد سوال(در کد برای جلوگیری از پیچیدگی ، مرکز دایره ها روی مراکز مربع ها در نظر گرفته شده اند.)

  

 

بچه ها سوال!

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

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

آزمون اینترنتی

مثل همیشه سلام بچه ها !

آزمون اینترنتی آزمایشی مرحله ۱ قراره چهار شنبه ی همین هفته‌ ( ۳۰ آذر‌ )‌ برگزار شه .

زمانش ساعت ۴:۰۰ بعد از ظهر و آدرس جایی که باید توش امتحان داد همsh44zzz.gigfa.comه .
البته اون آدرسه از سه شنبه آماده میشه .

فقط ( اگه زحمتی نیست و اینا‌ ) قبل از شروع آزمون ثبت نام کنین . ( برای شرکت باید ثبت نام کرد حتما )
ثبت نام هم تو همون آدرسه ( بدیهیه که وقتی از سه شنبه آماده میشه ، از سه شنبه به بعد باید ثبت نام کرد ) .

شاد و خوش و خرم و موفق باشین 

---

الان سایت آماده شده و می تونین توش ثبت نام کنید! (دقت داشته باشید که این تاخیر ها فقط به خاطر شروع ناگهانی دوره تیم ما بود و همچنین تاخیری که در اعلام نتایج رخ خواهد داد :-سوت)

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

(به علت ناتوانی گیگفا در ارسال میل فعلا باید صبر کنید تا بتونید از این قسمت استفاده کنید!)

ساعت آزمون اینترنتی هم به ۵ بعد از ظهر تغییر یافت!

---

آزمون اینترنتی هم به خوبی و خوشی برگزار شد! همونطور که فهمیدین هم سوال ۶ حذف شده بود ولی سوالای دیگه مشکلی نداشتن.

نظرات هم باز شده!

پاسخ نامه هم به زودی می ذاریم!گذاشتیم! الان تو قسمت بالای سایت هم لینک به سوالات و هم لینک به پاسخنامه وجود دارد!

---

نتایج آماده شده ، اما gigfa خراب شده ظاهرا و باید تا درست شدنش منتظر باشید.