X
تبلیغات
شاززز - المپیاد کامپیوتر - مرحله دوم
سلام!

بعد از کلی انتظار بالاخره نتایج مرحله ۲ هم اومد! نتایج کامپیوتر رو از اینجا ببینین:

http://ysc.ac.ir/include_elam_com.php


تبریک به همه اونایی که قبول شدن و بالاخره بعد کلی تلاش به نتیجه شون رسیدن. برین خودتونو آماده کنید برای مرحله ۳ که حتی اگه قبولم نشین از بهترین روزهای عمرتون میشه ;) ایشالا کداتونم باگ نمی خوره و مرحله ۳ هم قبول میشین!
خود مرحله ۳ همون طور هم که احتمالا می دونین دو روزه که هر کدومش یه امتحان حدود ۵ سوال و ۳ ساعت وقت و ایناست که اگه اوضاع بر وفق مراد باشه جاج خواهد داشت. که تو این دوسال که مرحله ۳ برگزار شده اوضاع بر وفق مراد نبوده و جاج نصفه نیمه بوده! سال اول برق باشگاه وسط سری دوم روز اول رفت و شبکه هم روز دوم خراب شد! سال دوم هم از قصد چند تا سوال جاج نداشته! ولی کلا موجود شاخی نیست اگه درست کد زده باشین این مدت و سعی کنین باگ نزنین راحت رد میشه :)
کامپیوتر هایی هم که بهتون میدن روش ویندوز نصبه و dev و چند تا ادیتور دیگه احتمالا خواهید داشت (سال ما که فقط dev بود)
این هم لینک اطلاعات کلی  کمیته در مورد مرحله ۳ ه. دقت کنید که چون کلا دو سال برگزار شده مرحله ۳ به احتمال خوبی قوانین اون تغییر می کنه و این چیزایی که گفتم مال سال های قبله ولی تو همون حدودا باید باشه!

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

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

خوش باشید

+ نوشته شده توسط حامد صالح(سابق) در سه شنبه 30 خرداد1391 و ساعت 18:42 |
سلام!

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

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

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

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

خدافظ!

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

+ نوشته شده توسط حامد صالح(سابق) در چهارشنبه 13 اردیبهشت1391 و ساعت 1:31 |
سلام!!

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

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


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

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

ce.sharif.edu/~esfandiari/INOIwriting


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

خوش باشید!


ادامه‌ی مطلب
+ نوشته شده توسط علیرضا فرهادی(سابق) در پنجشنبه 17 فروردین1391 و ساعت 17:37 |
سلام!

عید رو با چند روز تاخیر تبریک میگم ، امیدوارم که تا امروزش واستون خوب شده باشه همینجوری هم ادامه پیدا کنه. چون داریم به مرحله 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 تاشون هستند که جمع دو به دو ی آنها گنگ ست. »

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


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

+ نوشته شده توسط سعید ایلچی(سابق) در جمعه 4 فروردین1391 و ساعت 13:32 |
سلا م

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

+ نوشته شده توسط پویا مصدق(سابق) در چهارشنبه 2 فروردین1391 و ساعت 13:10 |
سلام رفقا. خوبید؟ امتحانات خوب پیش میره؟ ;)


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

اونایی که اسمتون قاطی لیست قبولی ها نیست(نخواهد بود!)، اول از همه باید به احساسات خودتون مسلط باشید و بدانید و آگاه باشید که قبولی تو المپیاد اونقدرا هم که فکر می کنید چیز با ارزش و مهمی نیست. باور کنید خیلی چیزای خفنتری تو زندگی هست. بعدشم، «مدال المپیاد داشتن» خیلی کم ارزش تر از «المپیادی» بودنه. خوشبختانه ماها هممون المپیادی هستیم B-). ادامه توضیحاتم رو میتونید اینجا بخونید. ;)

خب، حالا که به روحیتون مسلط شدید. اگه حس میکنید نمرتون به نمره قبولی نزدیکه، حتما برید اعتراض کنید. حتما!

اونایی هم که قبول شدید، اصلا انتظار نداشته باشید قبل از اینکه شام قبولیتون رو بخورم بهتون تبریک بگم. ولی فعلا علی الحساب دعا میکنم همتون طلا بگیرید! ;) :پی

در ضمن، از فردای اونروزی که نتایج مرحله 2 اومد، باید شروع کنید خودتون رو واسه مرحله 3 آماده(تر) کنید.  (روز اعلام نتایج رو دیگه بزارید واسه شادی و پایکوبی. خرخونا!)

از «سوالات آزمون مقدماتی سال های گذشته» استفاده کنید. ما هم یه برنامه هایی واستون داریم. یادتونه که قبل عید یه سری مقاله آموزش برنامه نویسی میزاشتیم اینجا؟ قسمت بعدیش به زودی میاد.

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


خب بسه دیگه، برید به امتحاناتون برسید.

المپیادی باشید! ;)

+ نوشته شده توسط محمد زابلیان(سابق) در شنبه 21 خرداد1390 و ساعت 0:19 |
با سلام امیدوارم مرحله 2 خوبی داشته باشید.

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

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

خود سوالات


+ نوشته شده توسط افروز جبل عاملی(سابق) در چهارشنبه 7 اردیبهشت1390 و ساعت 16:32 |

سلام

خسته نباشید

من یه کیلید در اوردم که امیدوارم اشتباه نداشته باشه



چپترین رقم جوابش می‌شه ۱

ماکزیمم مجموع دور دایره ۵۰

ریسهٔ چراغ می‌شه آیدین ۵ و مرتضی‌ ۴

ماشین بازپرور می‌شه۳

تولد حسام ۷۳

بیشینه باقیماندهٔ برابر با صفر می‌شه ۳۶

افراز عدد می‌شه : منفی ۴

تلسکوپ می‌شه ۲۴۵۷۶

۱۰ جعبه ۰


ملاقات راس‌ها می‌شه ۱۶

خیکول و دستگاه خود پرداز می‌شه ۷۲۰

جدول ۳ در ۹ می‌شه ۱۹۲


۵۰ نقطه روی خط می‌شه ۶

مرتضی‌ و مصطفی می‌شه ۱

الگوریتم س ، خ ، ... می‌شه ۳۳

هشت وزن می‌شه ۳

دستگاه عجیب می‌شه ۵۱


تولد آیدا می‌شه ۳


[ویرایش: دیروز این کلید آماده بود، اما برای ایجاد استرس کمتر قرار شد امروز در دسترس عموم بره. کلید روز دوم رو هم به زودی همین‌جا می‌ذارم]

+ نوشته شده توسط افروز جبل عاملی(سابق) در چهارشنبه 7 اردیبهشت1390 و ساعت 13:42 |
سلام

سه تا از سوالهای نسبتا آسون دوره تابستون خودمون رو گذاشتم. وقتش 4 ساعت هستش ( کمتر هم میتونه باشه).

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

شاد باشید.

+ نوشته شده توسط نازنین علیپور(سابق) در پنجشنبه 1 اردیبهشت1390 و ساعت 22:10 |
سلام

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

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

الان حدود ۲ هفته دیگه تا مرحله دو مونده. انتظار میره تو این فرصت قابل توجهی که داشتید مباحث تئوری (شامل ترکیبیات٬ گراف و الگوریتم) رو تا حد خوبی جلو برده باشید. این حد خوب یعنی مباحث مربوط به اصول شمارش٬ استقرا٬ لانه کبوتری٬ ناوردایی٬ اکسترمال٬ رنگ‌آمیزی٬ نظریه گراف و الگوریتم ها رو در حد مقدماتی و مورد نیاز بلد باشید!

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

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

از قدیم‌الایام رسم بوده که توی این فاصله از مرحله ۲ بچه ها به حل سوالات سالهای گذشته مشغول می‌شدن(سوالات رو میتونید از خبرگاه المپیاد کامپیوتر دریافت کنید). طبیعتا توصیه ما هم به شما همینه! چونکه توی این مدت که نزدیک به مرحله ۲ هستیم وقتی که این سوالات رو حل کنید ایده‌های مفیدشون بهتر توی مغزتون طبقه‌بندی میشه و یه سری ایده‌ها که ممکنه مدتی از اونها استفاده نکرده باشید و یادتون رفته باشه دوباره یادتون میاد که ممکنه به دردتون بخوره!

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

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

استرس داشتن هم بی‌معنی هست واسه مرحله ۲! شما استرس دارید که امتحان رو خوب میدید یا نه در صورتی که میدونید اگه مضطرب نباشید نتیجه بهتری میگیرید(چی گفتم!؟)! پس از اول اضطراب به دلتون راه ندید.

سخن آخر هم اینکه امروز ساعت ۱۸:۳۵ درواقع تولد ۵ سالگی شاززز هست... میتونین به این مناسبت و نتایج اخیر لیگ برتر و آسیا جشن بگیرید و شادی کنید. و این رو بدونید اگه امروز شاززز محل خوبی واسه ما بچه‌های کامپیوتری هست دلیلش زحمات همه کسانی که اسم برخی از اونها توی قسمت نویسندگان وبلاگ اومده و ما صرفا موقتا اینجا رو با کمکشون اداره میکنیم و این وظیفه خطیر(!) رو بعدا خود شما ادامه میدید.

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

امیدوارم همتون مرحله ۲ قبول شید(!) و فعلا خدانگهدار

+ نوشته شده توسط حسین شایسته(سابق) در یکشنبه 21 فروردین1390 و ساعت 8:0 |
سلام
نتایج مرحله اول هم اعلام شد. امیدوارم خودتون از نتیجه راضی باشید و به همه‌ی کسایی هم که قبول شدن تبریک می‌گم.
بهتره که کم‌کم جو مرحله ۲ رو به خودتون بگیرید! برای همین احتمالاً یه مدت کمتر طرف برنامه‌نویسی می‌ریم و بیشتر مطلب/سؤال تئوری (گراف، ترکیبیات و الگوریتم) می‌ذاریم.
برای این دفعه، یه سری سؤال هست که یا جدیده، یا احتمال اینکه دیده باشید کمتره.
در مورد همه‌ی سؤال‌ها پیشنهاد می‌کنم قبل از اینکه به راهنمایی نگاه کنید، حداقل یک ساعت بهش فکر کرده باشید.

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

خوش باشید


۱. n لامپ را روی یک خط قرار داده‌ایم. همگی بجز لامپ اول در ابتدا خاموش هستند. در هر مرحله اگر لامپی با همسایه‌هایش در مرحله‌ی قبل در یک وضعیت بود در این مرحله خاموش می‌شود و در غیر این صورت روشن می‌شود. ثابت کنید:
الف) بی‌نهایت n داریم که زمانی می‌رسد که همه‌ی لامپ‌ها خاموش باشند.
ب) بی‌نهایت n داریم که هرگز همه‌ی لامپ‌ها خاموش نمی‌شوند.

۲. کمترین n را بیابید که اگر یالهای گراف کامل n راسی (Kn) را به هر شیوه ای با دو رنگ آبی و قرمز رنگ کنیم، حتما یا زیرگراف K4 داشته باشد که همه ی یالهای آن آبی باشد یا زیر گراف K3 داشته باشد که همه ی یالهای آن قرمز باشد.


۳. به یک «گراف وزن‌دار جهت‌دار همبند»، «گوجه» می‌گوییم. در صورتی که وزن یال‌های گوجه، اعداد طبیعی باشد به آن گوجه‌ی طبیعی، و اگر وزن یال‌ها اعداد حقیقی بزرگترمساوی یک باشد به آن گوجه‌ی حقیقی می‌گوییم.

در گوجه، کوتاهترین مسیر بین دو رأس، مسیریست که جمع وزن یال‌های درون مسیر را کمینه کند.
در گوجه، خفن‌ترین مسیر بین دو رأس، مسیریست که ضرب وزن یال‌های درون مسیر را کمینه کند.
در یک گوجه‌ی طبیعی، زشت‌ترین مسیر بین دو رأس، مسیریست که در صورت ضرب وزن یال‌های درون مسیر، تعداد صفرهای سمت راست آن کمینه باشد.

دانشمندان علوم کامپیوتر جدیداً دستگاه خفنی به نام «گرافسالار» ساخته‌اند که با دریافت ماتریس مجاورت یک گوجه‌ی حقیقی n-رأسی، طول کوتاهترین مسیر بین تمام زوج-رئوس را در مرتبه‌ی زمانی O(n2) می‌یابد. شما می‌توانید از گرافسالار برای حل هر بخشی از مسائل زیر کمک بگیرید:
الف) ماتریس مجاورت یک گوجه‌ی حقیقی n-رأسی داده شده. به ازای تمام زوج-رئوس، طول خفن‌ترین مسیر بین آن دو رأس را بیابید.
ب) ماتریس مجاورت یک گوجه‌ی طبیعی n-رأسی داده شده. به ازای تمام زوج-رئوس، طول زشت‌ترین مسیر بین آن دو رأس را بیابید.
سعی کنید بهترین الگوریتم از نظر زمان اجرا را بیابید.


۴. به اجتماع یک یا چند دور که یال مشترک نداشته باشند «ابردور» می‌گوییم. رابطه‌ای برای محاسبه‌ی تعداد ابردورها در گراف دلخواهG بدست آورید. در این رابطه می‌توانید از خواص گراف (مانند ماتریس مجاورت) استفاده کنید. سعی کنید رابطه‌ی نهایی تا حد ممکن ساده‌تر باشد.


مینی‌راهنمایی!

۱. به توان‌های ۲ فکر کنید.
۲. اعداد رمزی
۳. الف) log(a×b) = log(a) + log(b) ب) عوامل ۲ و ۵
۴. برای حل مسئله در حالتی که گراف همبند است، زیردرخت فراگیر را در نظر بگیرید...

+ نوشته شده توسط سید مهران خلدی(سابق) در پنجشنبه 19 اسفند1389 و ساعت 19:13 |
سلام!

خب مرحله ۱ هم تموم شد و احتمالا دیگه همتون سرگرم مرحله ۲ خوندن و برنامه نویسی کردن هستید (اگه نیستید بجنبید، داره دیر میشه‌ها!)

کمیته دیشب یه پست گذاشت تو سایتش که توش سرفصل‌های مطالب مرحله دوم المپیاد کامپیوتر و یه سری منابع خوب رو معرفی کرده،‌ حتما ببینیدش!

در ضمن، شما باید یه برنامه ریزی خوب واسه این ۲ ماه و خورده‌ای باقی مونده انجام بدید، برنامه ریزیتون باید خصوصیات زیر رو حتما داشته باشه:

۱. از تفریحات عیدتون کم نزارید! ;)

۲. تئوریتون رو (اعم از ترکیبیات و گراف و الگوریتم[که به نظرم به همین ترتیب ۱.ترکیبیات ۲.گراف ۳.الگوریتم باید خونده بشه]) قوی کنید.

۳. طی این مدت، حداقل به چشم تفریح، برنامه نویسی هم کار کنید، سعی کنید یه کم با ++C آشنا بشید، پستای آموزش برنامه نویسی خودمون رو بخونید و اگه تمرینی توش بود انجام بدید، تو سایتایی که تو قسمت پیوندها معرفی کردیم کد بزنید و ... (البته فعلا تا مرحله ۲ اولویتتون تئوری باشه و به برنامه نویسی به چشم fun نگاه کنید! (ولی حتما نگاه کنید!) بعد مرحله ۲ قضیه برنامه نویسی کردن، جدی‌تر خواهد شد.)

۴. دو یا سه هفته‌ی قبل مرحله ۲ باید مرحله ۲های سالای پیش رو از خودتون امتحان بگیرید (غیر از اولی‌ها که باید اینکارو سال دیگه انجام بدن). پس اون ۲~۳ هفته رو باید خالی بزارید.

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



راستی، نتایج نظر سنجی راجع به نمرات مرحله ۱تون هم اینه: (البته تا دیشب این بود!)



سعی کنید موفق باشید!

+ نوشته شده توسط محمد زابلیان(سابق) در دوشنبه 18 بهمن1389 و ساعت 11:14 |
سلام بر همگی!

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

البته به اولی‌ها توصیه میکنم که نهایتا سوالای دو یا سه دوره رو از خودشون امتحان بگیرن و بقیه رو نگاه نکنن و نگه دارن واسه سال دیگه که امتحانش تاثیر گذارتره!

در ضمن، دوستان(!) زحمت کشیدن و بایگانی سوالات مراحل اول و دوم و سوم رو تهیه کردن، البته هنوز کامل نیست، ولی قراره کامل بشه انشاالله! دستشون درد نکنه!

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

موفق باشید

+ نوشته شده توسط محمد زابلیان(سابق) در دوشنبه 29 آذر1389 و ساعت 2:50 |

سلام ، خوبین؟ چه خبرا؟ زندگانی خوب پیش میره؟

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

اول ، به زبان ساده اگه بخوام المپیاد رو ترسیم کنم، این شکلیه : یه سری مسابقات جهانی به اسم المپیاد برگزار می شه. خب ما ایرانیا هم باید تیم بفرستیم به این مسابقات دیگه. خب الان می خوایم یه تیم انتخاب کنیم که برن واسه مسابقات. سبک مسابقات ببینیم چه شکلیه. خب به هوش و خلاقیت و بلد بودن یه مباحثی نیاز داره. پس بیایم یه امتحان برگزار کنیم و از بین دانش آموزا یه سری رو انتخاب کنیم برای تیم. اونا که این مطالبو بلد نیستن ، پس یه امتحان می ذاریم که کسایی که یه چیزایی بلدن و خلاقیت هم دارن انتخاب شن بیان براشون کلاس بذاریم و بعد بفرستیم جهانی. یه امتحان خیلی درصد خطاش زیاده و ممکنه افراد شایسته تری باشن و انتخاب نشن. واسه این همه داوطلب هم که نمی شه یه عالمه امتحان گذاشت. پس بیایم یه تعداد بیشتری (30 الی 40 تا ) انتخاب کنیم و کلاس بذاریم و تعداد زیادی امتحان بگیریم تا بهترین ترکیب واسه تیم مشخص شه .(بالاخره دوست داریم تیممون که میره جهانی بهترین نتیجه ممکن رو بگیره دیگه) برای انتخاب این 30~40 نفر هم ، چون داوطلبا خیلی زیادن ، نمی شه امتحان تشریحی گرفت ، امتحان تستی هم خیلی مناسب نیست ، پس اول یه امتحان تستی می ذاریم و بعد از منتخب ها یه امتحان تشریحی می گیریم.

خب الان فرض کنید با یه سری امتحان از این 30~40 نفر تیم مشخص شد.  این بچه ها باید کلاس داشته باشن تا قوی بشن واسه مسابقات. بعد هم باید اعزام بشن و برن جهانی. خب پس کی اینا کنکور بخونن؟! درسته که بچه های خیلی با استعدادی هستن ، ولی خب وقتی کنکور نخونن ، چیزی نمی شن تو کنکور دیگه !(و تنها مجرای رفتن به دانشگاه کنکوره) پس بیاین معافشون کنیم از کنکور. یعنی می گیم آقا جون ، تو بیا وقتت رو بذار واسه تیم ، کنکورت با ما! (واسه اینکه باز هم درصد خطای انتخاب تیم کمتر شه ، دو برابر تعدادی که واسه تیم می خوایم رو انتخاب می کنیم و اسمشون رو می ذاریم طلا و از کنکور معافشون می کنیم و به بقیه هم چون تابستونشون رو گذاشتن واسه این کار و از کنکوریا عقب افتادن یه سهمیه می دیم که جبران بشه)

به همین سادگی! این بود نحوه ی به وجود اومدن المپیاد از نظر من.

اما ببینیم از بیرون چه شکلیه! :

اول کار بچه ها بیشتر واسه ی علاقه وارد المپیاد می شدن. مثلا یادمه راهنمایی که بودیم ، یه سری کلاسهایی توی تابستون می ذاشتن به اسم کارسوق ریاضی. حدود سه شبانه روز یه سری از بچه های اصفهان و یزد و قزوین و کرج و که با آزمون ورودی انتخاب شده بودیم ، دور هم جمع می شدیم و یه سری کلاس و کارگاه داشتیم. توی کلاسا مباحثی مطرح می شد که عموما مربوط به المپیاد ریاضی و کامپیوتر بود ، بدون اینکه اسمی از المپیاد برده بشه. خب من و خیلیای دیگه از این چیزا خیلی خوشمون میومد و دنبال می کردیم ( حتی در حد همون 3 روز ) بدون اینکه هدفی برای شرکت تو المپیاد داشته باشیم. اصلا اون موقع فکر می کردیم این المپیادی های مدال آور که تو تلویزیون نشون می ده ، یه سری آدم عجیب و خفن و خارق العاده و خرخون که هیچ چیز غیر درس خوندن بلد نیستن و هستن! ( ولی الان فهمیدم یه سری آدم معمولی هستن مثه خودم )

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

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

به نظر شما آیا این هدف برگزاری المپیاد بوده؟! هدف ایجاد نشاط علمی بوده یا ناراحتی طولانی مدت یه عده ی زیادی از دانش آموزا؟

بله ، این رو قبول دارم که بالاخره ذات انسان کمال طلبه و دوست داره همه جا موفق باشه. و طبیعتا اگه کسی توی هر یک از مراحل موفق نشه ، ناراحت می شه. اما این ناراحتی باید زود گذر باشه ، باید همراه با عزمی بیشتر برای کسب موفقیت توی زمینه دیگه باشه. به نظر شما فرق این دو نفر ، بعد از این که مرحله 2 قبول نشدن چیه ، قضاوت با خودتون! :

نفر اول از وقتی فهمیده اگه طلا بشه کنکور معاف می شه ، شروع کرده المپیاد می خونه ، سر بعضی کلاسها هم نمی ره ، چون می خواد حتما طلا بشه. همه فکر و ذکرش شده المپیاد و خیلی هم زحمت می کشه. شبا خواب طلا می بینه! اما توی مرحله 2 به هر دلیلی موفق نمی شه

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

این همه حرف زدم که بگم ، عزیزان من! این مباحث المپیادی رو اگه دوست دارین ، واسه خودش بخونین. هدف اصلیتون المپیاد و معافی و نباشه! شما حتی اگه مدال هم نگیرین ، هیچ ضرری نکردین. المپیاد کامپیوتر و کلا سوال حل کردن ذهنتون رو باز می کنه. دید خوبی بهتون می ده که بعدها  خیلی بهتون کمک می کنه. (حتی مباحث شمارشی که یاد می گیرین توی درس جبر سوم و گسسته ی پیش کمکتون می کنه)

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

در پایان! اگه هدف اصلیتون پیچوندن کنکوره ، اشتباه اومدین! بهتره برگردین از اول شروع کنید.

پی نوشت 1: من این پست رو یه هفته پیش نوشته بودم ، ولی بکاپ نگرفته بودم و مشکل پیش اومد و پرید! (البته چیزی که اون موقع نوشته بودم یه کم فرق داشت ، شاید قسمت بود که یه چیزایی رو نگم و یه چیزای دیگه بگم! ) الان ساعت 1:30 نصفه شبه دارم اینو می نویسم فردا هم 6 صبح قراره با بچه ها بریم کوه! چه طوری بیدار شم حالا؟‼

پی نوشت 2: اگه غلط املائی یا انشائی دیدین تو متن ، بگین تا درستش کنم!

 

+ نوشته شده توسط علیرضا ذاکری(سابق) در دوشنبه 14 تیر1389 و ساعت 1:43 |
سلام خسته نباشید مرحله دوم خوب بود ؟
اینم کلیدی که قول داده بودم... (با کمک بهروز)
سوال ۱:
حقوق هر فرد را در وضعیتی که iنفر در شرکت اول بروند Pi و در وضعیتی که به شرکت دوم بروند Fi می نامیم... برهان خلف می زنیم... فرض کنیم وضعیت جواب نداریم
اگر nنفر به شرکت اول بروند،   F1 > Pn است، (وگرنه وضعیت جواب بود)، ‌حالا اگر n-1 نفر به شرکت اول بروند Pn-1 < F2،‌اگر n-2 نفر بروند Pn-2 < F3 و ... و اگر یک نفر برود P0 < Fn است که نا مساوی آخر

تناقض است. ‍‍‍پس این بین یکی از نامساوی ها غلط بوده و حالت جواب بوده.
//=================================================
سوال ۲:
گراف جایگشت را می کشیم،‌طوری که از i به πi یالی جهت دار می کشیم. گراف افرازی از چند دور است. در هر عمل طول هر دور نصف می شود، (چرا ؟) پس از k مرحله همه دور ها طولشان یک می شود.
ب) جایگشت 2, 3, 4, ..., n-1, n, 1 را در نظر بگیرید و پس از هر مرحله جای یک را بررسی کنید...
//==================================================
سوال ۳:
الف) درخت را از یک راس آویزان می کنیم،‌حالا پایین ترین یال خراب (یالی که عوارض دو سرش یکسان شده اند) را در نظر بگیرید (و آن را uv بنامید، طوری که u پدر v باشد.) یکی از بچه‌های v مانند w را انتخاب می‌کنیم. عوارض یال vw را عوض می‌کنیم. با این حساب uv دیگر خراب نیست. از طرفی ممکن است چند یال مانند vx یا wy خراب شده باشند. (که همگی پایین‌تر از uv هستند.) ، و ... استقرا
پایه‌ی استقرا: برگ. چون عوارض صفر نداریم، ...
ب) *ها شهرها هستند. عوارض جاده‌ها درون پرانتز نوشته شده است.
*-(a,b)-*-(0,1)-*-(a,b)-*-(0,1)-*-(a,b)-*
بررسی کنید.
//==================================================
سوال ۴:
یک «وضعیت» را برای مسئله اینگونه تعریف می‌کنیم:
«جاده‌ی خروجی هر میدان کدام است؟ و ما کجا هستیم؟»
واضح است که تعداد حالات متناهی است. پس اگر از وضعیت ابتدایی شروع کنیم، بعد از طی چند مرحله به یک وضعیت تکراری برمی‌گردیم. دور حاصل از وضعیت‌ها (در گراف وضعیت) را در نظر می‌گیریم. ادعا می‌کنیم با پیمودن این دور، از همه‌ی شهرها گذشته‌ایم.
برهان خلف: شهری را در نظر بگیرید که در گراف وضعیت بازدید شده باشد و دارای حداقل یک همسایه‌ی بازدید‌نشده باشد. (آن را v بنامید) این دور را d_v (تعداد همسایه‌های v) بار طی می‌کنیم. حتما یک بار پلیس جاده‌ی منتهی به شهر بازدید نشده را باز می‌کند. تناقض...
//==================================================
سوال ۵:
توضیح بیشتر در مورد الگوریتم داده شده:
در ابتدا n دسته‌ی ۱ عضوی داریم. هر بار، دو دسته‌ی دلخواه را انتخاب می‌کنیم، و همه‌ی اعضای دسته‌ی کوچکتر را در دسته بزرگ می‌ریزیم و به اندازه‌ی تعداد اعضای دسته‌ی کوچک پول خرج می‌کنیم (به b اضافه می‌کنیم)
الف) در هر مرحله، اگر x دسته داشته باشیم، به x/2 تا دسته ۲تایی تقسیم می‌کنیم. و دو به دو با هم تلفیق می‌کنیم.
ب) هر عدد حداکثر در k عملیات جابه‌جایی شرکت داشته. (چرا؟) پس در کل k * 2^k تا عمل انجام شده.
(برای اطلاعات بیشتر در مورد کاربرد این الگوریتم، در مورد داده‌ساختار DisjointSet تحقیق کنید. منابع: ویکی‌پدیا، CLRS، Creative و JBL)


[پس از بررسی حل خود برای تخمین بهتر کف حتما در نظرسنجی شرکت کنید.]


+ نوشته شده توسط افروز جبل عاملی(سابق) در چهارشنبه 8 اردیبهشت1389 و ساعت 16:30 |
سلام
مرحله دوم خوب بود ؟ من که به شخصه  خیلی خوشم نیومد .

من یه کلید به سرعت در اوردم امیدوارم درست  باشه. 
سوال مربع و ۱۳۸۹ پارهخط میشه ۴۱۶۸ 
سوال  ۲۰۱۰ عدد کمتر از ۲ به توان ۱۳۸۹ میشه ۱۳۹۹
سوال ۲۰ سکه ی طلا  میشه ۱۰
سوال مکعب ۳*۳*۳ میشه ۶
سوال اشباع شده میشه 42
سوال سکه ها و پرتاب میشه ۱/۸
سوال مربع ۳*۳ میشه ۹ تا
سوال پست خونه میشه ۳۶ تا .
سوال n سکه میشه ۱۳۹۱
سوال ۳ کلید میشه k =3 
سوال مرتب کردن سکه میشه ۵ تا 
سوال دزد و تابلو ها میشه p(i)=max(vi+p(i-2),p(i-1)) in
سوال دانشجو و استاد میشه ۶
سوال راننده و جا ی پارک میشه ۱،۳،۲۹۹
سوال الگریتم s  و b  میشه ۷
سوال لیگ فوتبال میشه ۹
سوال طرح سوال میشه ۱۶۸
سوال الگوریتم رو a1 a2 a3 a4 میشه ۲۶
سوال مقدار کمینه s  میشه ۳۵
سوال ۶ لامپ میشه ۲۹
   
+ نوشته شده توسط افروز جبل عاملی(سابق) در سه شنبه 7 اردیبهشت1389 و ساعت 21:15 |
سلام
ببخشید یه کم دیر شد  سرم واقعن شلوغ بود. اول جواب سوال های خودمو میزارم
جواب ها را فقط راهنمایی میکنم تا اگه کسی خواست رو تکمیل کردنش فک کنه.
بعد هم یه لینک میزارم که توش سوال های جدیده. از خودتون امتحان بگیرید تو ۴ ساعت.
جواب ۱
ثابت کنید که اگر سطر اول را شطرنجی رنگ کنیم باقی سطرهای جدول باید شطرنجی باشن و در غیر این صورت یعنی اگه ۲ تا از خانهای مجاور سطر اول پس از رنگ آمیزی این سطر  همرنگ باشن   باقی سطر ها یکتا رنگ میشه .
جواب ۲
ثابت کنید اگر یک سطر و یک ستون را رنگ کنیم بقیش یکتا میشه .
جواب ۳
از استقرا روی n استفاده کنیم. در زیر درخت فراگیر مینیمم یک برگ مثل n +1 را در نظر بگیرید . برای n راس اول دور با وزن کمینه را c1،...cn بگیرید.  فرض کنید c1 راس مجاور برگn +۱ باشد.منظور از برگ راس  با درجه ی ۱ در درخت است. حال یال c1c2 را از دور کمینه حذف کنید و جاش ۲ یال جدید  c1,n+۱ و  c2n+۱ را اضافه کنید. و با توجه به فرض استقرا و خاصیت حمار حکم را ثابت کنید.
 جواب ۴
توجه : اگر و تنها اگر یعنی اینکه باید ثابت کنید اگر شرط اول باشد دومی هست و اگر نباشه دومی هم نیس.
ابتدا ثابت کنید n اگر ۲ و ۴ باشد جواب وجود ندارد .  این قسمت بسیار ساده است. حال برای حل از n به n +۲ استقرا بزنید. پایه های استقرا را ۳ و ۶ بگیرید.
n راس اول را s بگیرید. از n +۱ به سمت s یال بکشید از s به سمت n +۲ و از n+1 یال بکشید. یال های s را طبق فرض جهتدهی کنید. ثابت کنید حکم برقرار میشود.
جواب ۵
برای این سوال ۳ راه با استقرا وجود دارد .من در این جا ۲ تا شو راهنمایی میکنم. یکیش اینکه طولانی ترین مسیر را بگیرید و با فرض  این که دور  زوج ندارد  و با استفاده از راس های سر این مسیر ثابت کنید یا ۲ راس هس که تعداد یال های مرتبط با این ۲ تا ماکسیمم ۳ تا باشه یا این که یه راسه درجه یک داریم. که با حذف اینها حکم استقرا برقرارشود.      

راه دوم اینه که فرض کنید دوره زوج نداره  یه دور فرد را بگیرید ثابت کنید بدون یال های دور هیچ ۲ راسی از این دور بهم مسیر ندارند وگرنه یه دور زوج تولید میشه. حالا برا تیکه های دیگه ی گراف فرض استقرا  بزنین.
جواب ۶
از استقرا روی  سایز آرایه استفاده کنید. اولین جایی که m  صفر میشه  رو بگیرید. و از اون جا به بعد ارایه استقرا بزنید. این نکته را در نظر بگیرید که اگر عددی تو بیش از نصفش اومده باشه بعد از اون جایی که صفر میشه هم تو نصفش میاد.
اینم لینک سوال های جدید که طراح هاش آقایان طهماسبی، عابدی گزل آبادی،جلالی و بابایی چشمه احمد رضایی هستن.
      

ادامه‌ی مطلب
+ نوشته شده توسط افروز جبل عاملی(سابق) در یکشنبه 5 اردیبهشت1389 و ساعت 14:36 |
سلام بچه ها ، خوبین؟ چه خبرا؟ خوش می گذره؟ مرحله یک رو خوب دادین؟

ما هم خوبیم ، شکر!

از عنوان این پست پیداست که در چه مورد می خوام باهاتون صحبت کنم. آفرین ، مرحله 2!

چند نفر توی نظرات پرسیده بودن که چی کار کنیم و چی بخونیم و ...

والا ما خودمونم نمی دونیم قراره چه اتفاقاتی واسه مرحله دو بیفته ، همون طور که مرحله یک به جای 40 تا سوال 25 تا بود. اما خب ، در هر صورت غالب کلی کار ثابته. شما باید بتونید مسئله حل کنید و سر سوالا به قول بچه ها گفتنی IQ بزنین. یه سری میگفتن که تا دیدیم مرحله یک 25 تا سواله یا مثلا 2 ساعته یهو هول شدیم. من به اونا گفتم ، به شما هم میگم. شرایط برای همه یکسانه!! ( البته نه کاملا! ما سر مرحله دومون یه ماشین کنار حوزه بود و از اول تا آخر امتحان دزدگیرش داشت صدا می کرد ، فک کنم کلا صاحب نداشت! )

وقتی وقت امتحان برای تو 2 ساعته ، برای اون یکی هم 2 ساعته. خب دیگه هول شدن واسه چیه؟ تو باید فقط سعی کنی سوالا رو حل کنی با اتکا به هوشت و مطالبی که قبلا خوندی. حالا چه 40 تا چه 25 تا!

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

حالا بریم سراغ اصل مطلب. کلا شما باید یه سری مطالب رو بلد باشین ، مثله :

1- اصل استقرا و طریقه ی حل مسئله با آن

2- اصل لانه کبوتری

3- اصل ناوردایی

4- اصل اکسترمال

5- حل مسئله به کمک رنگ آمیزی

6- اصول شمارش

7- نظریه گراف

8- آشنایی مقدماتی با الگوریتم

و مهم تر از همه حل مسئله به تعداد زیاد!

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

1- الفبای المپیاد ریاضی و کامپیوتر - نویسنده: مرتضی محمد آبادی - این کتاب اکثر مطالب بالا رو به طور مختصر داره ولی استقراش خیلی کامله. حتما کل این کتاب رو بخونید.

2- استراتژی های حل مسئله - نویسنده: آرتو انگل - این کتاب موارد 1 تا 6 رو داره . مسئله هاش هم آسون داره هم خیلی سخت. اگر مسئله ای رو بعد از مدت زیاد نتونستین حل کنن ، راه حلش رو بخونین و یاد بگیرین.

3- ترکیبیات - نویسنده: علیرضا علیپور - این هم کتاب خیلی خوبیه و اکثر مطالبی که گفتم توش هست.

4- آشنایی با نظریه گراف - نویسنده: دوگلاس برنت وست - این کتاب که معولا بهش "وست" میگن در مورد گرافه! و خوبه که حداقل 2 فصل اولش رو بخونین و مسئله هاش رو حل کنین. بلد بودن قضایا و تعاریف بدون حل مسئله هیچ کمکی به شما نمی کنه. حتما تمریناش رو حل کنین.

5- مسئله های الگوریتمی - نویسنده: دکتر قدسی و دکتر مهدیان - توی این کتاب مسائل خیلی خوبی هست. البته بخش های اولش سوالای برنامه نویسیه که اونا رو نیاز نیست بخونید. شما سوالای گرافش و مسائل متفرقه اش رو حل کنید. مسائل این کتاب سختن و شما بعد از اینکه به مطالبی که قبلا گفتم مسلط شدید ، می تونید از این کتاب استفاده کنید.

6- معماهای الگوریتمی - کتابیه که توصیه می شه ، مخصوصا امسال که قراره سوالای الگوریتمی بیشتری داشته بشه! خودم نخوندمش و اطلاعی در موردش ندارم.

7- مسائل مرحله دوم سالهای پیش: مرحله دو های قبلی رو از خودتون امتحان بگیرید. بهتره با دوستانتون با هم اینکار رو بکنید. چون اینجوری می تونید جواباتون رو با هم چک کنید. این مهمترین کاریه که باید بکنید.

8 و 9- المپیادهای ریاضی لنینگراد - المپیاد های ریاضی شوروی : باز هم برای حل مسئله بیشتر می تونید از این کتابا استفاده کنید. البته همون طور که از اسمش پیداست ، مسائل المپیاد ریاضی و شما باید ترکیبیات هاش ( مسائل کامپیوتری ) رو حل کنید.

کلاً لذتی که توی حل یه مسئله بعد از چندین ساعت هست ، تو هیچ چیز دیگه ای نیست! سعی کنین المپیاد رو برای لذت بردن و تفریح! بخونید نه واسه ی پیچوندن کنکور. اگه هدفتون پیچوندن کنکور نباشه، حتی اگه مرحله 1 هم قبول نشین ، شکست نخوردین.

10- Introduction to algorithms - A creative approach - این کتاب هم انگلیسیش هست هم فارسیش. ( اسم فارسیش فک کنم "آشنایی با الگوریتم با رویکردی خلاقانه" باشه ) ، این رو فصلهایی که حس می کنین به دردتون می خوره رو بخونین و تمریناش رو حل کنید.

خوبه که یه آشنایی مقدماتی هم با زبان ++C داشته باشین ( متغیر ها ، حلقه ها ، ورودی گرفتن و خروجی چاپ کردن ... )

کتاب آموزش ++C هم دو تا معروف هست : یکیش ترجمه جعفر نژاد قومی یکی هم ترجمه قلزم.

اگه زبانتون خوبه هم که اینترنت بهترین منبعه! مثلا سایت www.cplusplus.com

بعد از این که یه کمی ++C یاد گرفتین ، توی سایتهای برنامه نویسی که برای این کار هستن عضو بشین و سوال حل کنید و کد بزنید. ( کد زدن ( coding ) اصطلاحیه به معنیه برنامه نویسی  ، مثلا کد این سوال رو زدم ، یعنی برنامه ای نوشتم که این سوال رو حل کنه! )

سایتهای خیلی زیادی هستن برای این کار ، ولی 2 تا سایت هست که از همه معروفترن و ملت معمولا توی این دو تا سایت کد می زنن:

1- المپیاد کامپیوتر آمریکا - USACO ( معروف به "یوساکو" ( با "ایساکو" فرق داره ها! ) ) 

2- سایت ای سی ام یک دانشگاه در روسیه! - SGU  ( معروف به "اس جی یو"! )

سایت های دیگه هم هست که توی پیوند ها می تونید پیدا کنید.

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

+ نوشته شده توسط علیرضا ذاکری(سابق) در جمعه 23 بهمن1388 و ساعت 15:19 |
سلام! خوبید؟!

یه دوره‌ای ۱۰ روزه قراره که برگزار بشه برای بچه‌هایی که پارسال مرحله دومشون رو خوب دادن!

از ۲۱ام هست تا ۲۹ام. توی دوره بیشتر برنامه نویسی کار می‌کنن و شایدم الگوریتم کار کردن یه کمی

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

اسامی در ادامه مطلب درج شده است.


ادامه‌ی مطلب
+ نوشته شده توسط حسام باقری نژاد(سابق) در یکشنبه 27 دی1388 و ساعت 14:59 |
سلام به همگی.

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

-اینا جواب هاییه که به ذهن من رسیده و ممکنه جواب های بهتر و قشنگ تری هم وجود داشته باشه. اگه کسی خواست می تونه جواب های خودش رو تو نظرات بنویسه.

اینم جواب ها:

۱- افراز متوازن:

اول یه لم مهم رو ثابت کنید: صورت لم همان صورت مساله است با این تفاوت که از شما خواسته اند وزنه ها را به دو دسته تقسیم کنید به طوریکه اختلاف آنها ۲ به توان k باشد. k را به شما می‌دهند و می دانید ۲ به توان k از همه وزنه ها مقدارش اکیدا بیشتر است. باید ثابت کنید تعداد راه های افراز وزنه ها با این شرایط صفر یا توانی از دو است.

این لم را می توانید با استقرا روی k و حالت بندی روی تعداد وزنه هایی که وزنشان ۲ به توان k-1 است(در گام استقرا) ثابت کنید.

مساله اصلی را نیز می توان با استقرا روی وزن بزرگترین وزنه و حالت بندی روی تعداد این وزنه ها و استفاده از لم بالا اثبات کرد.


۲- سپید و سیاه:

یک راه‌حل منطقی این است که ثابت کنید تا وقتی حداقل دو خانه سیاه داریم می توان تعداد خانه های سیاه را کم کرد. برای این کار دو خانه سیاه را در نظر بگیرید که فاصله شان از همه کمتر است. با این فرض می توان نتیجه گرفت که در زیر مستطیلی که این دوخانه در گوشه های قطری‌اش هسند هیچ خانه سیاه دیگری نیست. حالا با حالت بندی روی طول اضلاع این مستطیل سعی کنید تعداد خانه های سیاه را کاهش دهید. به این نکته هم دقت کنید که m و n (طول اضلاع جدول اصلی) هر دو حداقل ۳ هستند.


۳- گراف یابی:

ثابت کنید تعداد پرسش ها حداقل (C(2, n است. یعنی حالتی وجود دارد که مملی مجبور است به ازای هر جفت از راس ها از ففلی یک سوال بپرسد. (اگر ففلی به ازای هر سوال که مملی می پرسد بگوید فاصله آن دو راس بی نهایت است، یعنی آن دو به هم هیچ مسیری ندارند، مملی مجبور است همه جفت ها را از ففلی بپرسد).


۴- ماتریس کم تنوع:

کافی است که از روی یک ماتریس a*a با تنوع p و یک ماتریس b*b با تنوع q، یک ماتریس (ab)*(ab) با تنوع p.q بسازید.


موفق باشید.

خداحافظ!


+ نوشته شده توسط علی بابایی(سابق) در چهارشنبه 18 آذر1388 و ساعت 11:26 |

به نام خدا

سلام به همه رفقا. عید قربان با کمی تاخیر مبارک! عید غدیر هم پیشاپیش مبارک!

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

اما قبل از اینکه سوال ها رو بذارم چندتا نکته می گم:

- من خودم به نظرم الان سوال تئوری نمی‌ذاشتیم بهتر بود. چندتا دلیل هم دارم. اول اینکه به خاطر تغییرات المپیاد کامپیوتر سبک سوالات معلوم نیست چی جوری باشه. دوم اینکه سوال هایی که ما می ذاریم اکثرا از همون منابعیه که در دسترس همه هست (مثل کتاب های شوروی و وست و استراتژی و ..)، به جز اونایی که تو دوره دیدیم و ممکنه برای شما جدید باشه(این سوال هایی هم که در ادامه می‌نویسم ماله دوره تابستونیه خودمونه). سوم اینکه من تو آرشیو وبلاگ یه نگاه کردم دیدم کلی سوال تئوری وجود داره که می تونید از اون ها هم استفاده کنید. خب همین چندتا دلیل بسه دیگه!(D:).

- با این اوصاف چون ملت خواستند سوال بذاریم من ۴تا سوال می ذارم. این سوال هایی که خواهم نوشت مال امتحان های تئوری تابستون پارسال هستند که طراحاشون آقای زادی مقدم و آقای مهینی بودن.

- من پیشنهاد می کنم تا چند روز کسی در مورد جواب سوال ها تو بخش نظرات چیزی ننویسه، بعدش رو جواب ها بحث می کنیم. البته در مورد خود سوال ها یا چیزای دیگه اگه خواستید می تونید نظر بدید.

اینم سوال ها:

۱-افراز متوازن:

تعدادی عدد طبیعی که هر یک توانی از دو هستند به ما داده اند. می دانیم که از هر توان دو حداکثر دوتا به ما داده شده است. مثلا ممکن است به ما اعداد ۱و۱و۲و۴و۸و۳۲و۳۲ را بدهند. ثابت کنید تعداد روش‌های افراز این اعداد به دو دسته برابر یا صفر یا توانی از دو است. مثلا اعداد بالا را تنها به شکل (۸و۳۲) و (۱و۱و۲و۴و۳۲) می‌توان به دو دسته برابر افراز کرد.


۲-سپید و سیاه:

خانه های یک جدول m*n را با رنگهای سفید و سیاه رنگ کرده‌اند. ما در هر مرحله می‌توانیم یک زیر مستطیل این جدول را به شرطی که (این زیر مستطیل) شامل لااقل دو خانه سیاه باشد، انتخاب کرده و رنگ کل خانه های این زیرمستطیل را عوض کنیم. ثابت کنید که اگر m و n هر دو از ۲ بیشتر باشند، با تعدادی از این حرکات می توان به جدولی برسیم که حداکثر یک خانه سیاه دارد.


۳-گراف یابی:

ففلی یک گراف ساده n-راسی روی کاغذ کشیده است و به مملی نشانش نمی دهد. مملی در هر لحظه دو راس را انتخاب می کند و ففلی فاصله آن ها را به مملی می گوید. کمترین تعداد سوال که مملی باید بپرسد تا از شکل گراف آگاه شود بر حسب n چند است؟


۴- ماتریس کم تنوع:

یک ماتریس n*n که با اعداد ۱ تا n*n پرشده است داریم. رتبه یک درایه در این ماتریس برابر تعداد اعداد بزرگتر از درایه در کل سطر و ستونش می باشد. بنابراین رتبه هر درایه عددی بین ۰ تا 2-2n است. تعداد رتبه های مختلف که در این ماتریس مشاهده می شود برابر تنوع آن است. کترین تنوع در بین همه‌ی ماتریس‌های n*n با درایه های متفاوت را (T(N بنامید. ثابت کنید:

T(ab) <= T(a) * T(b)

موفق باشید.

خداحافظ!

+ نوشته شده توسط علی بابایی(سابق) در دوشنبه 9 آذر1388 و ساعت 23:29 |
آقای دکتر قدسی ، رئیس کمیته ملی المپیاد کامپیوتر لحظاتی پیش توضیحاتی در مورد المپیاد کامپیوتر امسال دادند که متن آن به شرح زیر می باشد: ( اُه! چه ادبی شد! )

:" به لینک
http://ce.sharif.edu/~ghodsi/inoi/inoi-new-chart.pdf
مراجعه و فایل مربوطه را دانلود کنید و آن را به دقت بخوانید. این فایل حاوی جزییات برنامه‌ی جدید است.

چند نکته‌ی فوری:
۱- کلاس‌های سومی از امسال می‌توانند در مرحله‌ی اول شرکت کنند. مرحله‌ی اول امسال ساده تر از سال‌های پیش است و حدود ۱۰۰۰ نفر از شرکت کنندگان سال اول تا سوم انتخاب می‌شوند تا در مرحله‌ی دوم شرکت کنند.
۲- مرحله‌ی دوم در دو روز برگزار می‌شود. دانش‌پژوهانی که در دوره‌ی تابستان ۸۸ برنز نگرفته اند از شرکت در مرحله‌ی اول و دوم معافند. اما برنزی ها مانند دانش‌پژوهان جدید باید شرکت کنند.
۳- از مرحله‌ی دوم کلا ۶۰ نفر انتخاب می‌شوند تا در آزمون برنامه نویسی ای که درست قبل از تابستان برگزار می‌شود شرکت کنند. تا بر اساس این نمره‌ی این آزمون و نمرات آزمون‌های مرحله‌ی اول و دوم، ۳۰ نفر برای دوره‌ی تابستان ۸۹ انتخاب شوند.
۴- حدس زده می‌شود که برخی از بچه‌های نقره‌ای تابستان ۸۸ که هم اکنون سال سوم هستند ترجیح می‌دهند که به دنبال کنکور بروند. اما اگر بخواهند می‌توانند بدون شرکت در مرحله‌ی اول و دوم و نیز آزمون برنامه نویسی در دوره‌ی تابستان ۸۹ شرکت کنند. البته این دانش‌پژوهان دیگر مجاز به شرکت در کلاس‌های درس تابستان نیستند ولی باید فقط در آزمون‌های آن شرکت نمایند.

موفق باشید "

+ نوشته شده توسط علیرضا ذاکری(سابق) در جمعه 24 مهر1388 و ساعت 11:41 |
خوب میگن مرده و  حرفش , كه مرده ایهام داره  فکر کنم
اعلام شد كه سال سومی ها هم میتونن المپیاد بدن  این هم لینکش 

http://ysc.ac.ir/showNews.aspx?id=342

از علیرضا هم عذر میخوام ولی چون من قول داده بودم گفتم

+ نوشته شده توسط رامتین رطبی(سابق) در جمعه 17 مهر1388 و ساعت 0:0 |

خب, يه مرحله ۲ ديگه هم تموم شد.
تبريك ميگم به اونايى كه قبول شدن و به اونايى كه قبول نشدن توصيه مي كنم بريد و اعتراض كنين
كافيه يک سوالتون رو بد خط نوشته باشين و 0  گرفته باشين اون موقع با اعتراض ۲۵ نمره مى گيرين و اوضاع فرق خواهد كرد
اصولا هر سال, ۳ يا ۴ نفر اعتراضى قبول ميشن.
چنان چه اعتراض هم دادين و قبول نشدين خيلى ناراحت نباشين چون راه تازه ای جلوى پاتون هست و قرار نيست همه المپیاد قبول بشن، به اين فرض بذارين كه صلاح نبوده كه قبول شين
يه كم كه بگذاره مى فهمين اينا همه بازی هاى بچهگونه بوده و دوامش تا دانشگاه هستش.  

به نظرِ مهم ترين چيزى كه المپیاد كامپيوتر داره اون قدرت استدلالی هست كه به آدم ميده و كلى چيز ياد گرفتين كه خيلى از مردم نمى دونن در موردش بجاى اينكه بريد بخونيد هل = آيا و رضاشاه آدم بدی بوده و فلانی خوب و  ...

اونايى كه مرحله ۲ قبول شدن خوبه كه يك كمى CLRS و WEST بخونن كه الگوریتم و گرافشون خوب شه چون تو دوره بايد درس پاس كنين و اگر ۲ تا درس بیفتین برنز ميشين.

البته نترسین آسون پاس كردن درس ها.

براى برنامه نويسى هم ++C جعفرنژاد قمى من خودم خوندم.

البته تو دوره درس ميدن ولى اينكه بتونين يک برنامه قبل دوره بنويسين خيلى مهمِه.

براى برنامه نويسى هم از سايت هاى المپیاد آمريكا و ACM روسیه استفاده كنين

acm.sgu.ru

ace.delos.com

يه كم بچرخید تو سايت ها ياد مى گيرين.

من همیشه  sgu رو ترجیح می دادم ولی خیلی ها می گن usaco بهتره چون درس میده. البته به زبان انگیلیسی.

 

+ نوشته شده توسط رامتین رطبی(سابق) در سه شنبه 26 خرداد1388 و ساعت 16:56 |

براى اين سوالها يه سرى لم داريم كه فرض ميكنيم  پذیرفتیم! 1 -يك گراف با n راس و n  یال حتما يك دور دارد - 2گراف G  يك  زیر گراف دو بخشى دارد كه بيش از نصف یال ها را دارد! -3قضيهِ هال: در گراف ۲ بخشى كه از دو بخشِ A و B تشكيل شده و هر زیرمجموعه مثل X از A داراى شرط:

|X|<=|N(X)|

 آنگاه تطابقی وجود دارد كه A را بپوشاند !

سری 1:

1 - طبق لم ۲ داريم كه اين گراف زير گرافی با بيش از نصف یال ها دارد !! ما   2*nتا یال را در نظر ميگيريم !!! فرض كنيد بخش هاى گراف ۲ بخشى بالا و پائين بنامیم
حالا يك سرى از یال ها جهت دار به سمتِ پائين هستند و يك سرى به سمتِ بالا! يكى از اين ۲ دسته یال, بيشتر از n تا است! اين n تا را در نظر بگيريد !
n
تا راس داريم و n تا یال پس طبق لم ۱ يك دور وجود دارد كه یالهایش همه به طرف يك بخش است پس خاصیت  مورد نظر را دارد

2 -ماتریسی كه در هر سطر و ستونش  k تا ۱ داريم را A بناميد

از روى A يك گراف 2 بخشی مى سازيم به ازاى هر سطر و ستونش يك راس مي گذاريم يعنى براى ماتریس 2*n, n*nتا راس داريم ! حالا اگر  A[i][j]=1 آنگاه از رأس  i بخشِ سطر به j بخشِ ستون ها وصل ميكنيم! حالا يك گراف ۲ بخشى داريم كه درجهِ همه راس ها k است با استفاده از لم ۳ ميتوان اثبات كرد كه هر گراف k َ منتظم ۲ بخشى داراى تطابق كامل است حالا هر بار يك تطابق بر ميداريم و تبدیل به یک گراف می کنیم و اگر یال i به j را بر داشتیم آنگاه در ماتریسی كه داريم مى سازيم درایه ی i و  j را ۱ ميكنيم !! حالا يك گراف k-1  منتظم  داريم و دوباره ميتوانيم يك تطابق كم كنيم به اين ترتيب ما k تا جدول خواهيم داشت كه جمعِ اين جدول ها ميشود  A

  3- همواره نفر اول مي برد به غير از n=1 , m=1 هميشه در حركتِ اول خانهِ (0,0)خرده ميشود فرض كنيد نفر اول فقط خانهِ (0,0) را ميخورد و در بهترين بازى می بازد
حركتِ اولِ نفر دوم را در نظر بگيريد !! اگر زيرِ نقطه (X,Y) را خرده باشد آنگاه نفر اول ميتوانند در حركتِ اول تا خانهِ (X,Y) رو بخورد و حالا تبديل به نفر دوم شود يعنى در واقع جاى خود را با نفر دوم عوض ميكند. حالا نفر اول حتما ميبرد چرا كه اگر نفر دوم ببرد آنگاه در حالتى كه نفر اول (0,0) را ميخورد و نفر دوم (X,Y) را نفر اول می توانسته برنده شود

 

4 - جواب نه است فرض كنيد توانستیم اين كار را انجام بدهيم !! براى اينكه اين كار را انجام بدهيم بايد ۴۰۰۴ تا معادل a=bc داشته باشيم !! يكى از b يا c بايد از ۲۰۰۳ كمتر باشد چون اگر نباشد b*c>2002*2002 ميشود خوب اگر سطری وجود داشته باشد كه اعداد هاى ۱ تا ۲۰۰۲ هيچ كدام را نداشته باشد و سطری وجود داشت كه از ۱ تا ۲۰۰۲ را نداشت آنگاه تقاطع  اين سطر و ستون جواب است ! اما اگر يك سطر فقط وجود داشت كه از ۱ تا ۲۰۰۲ را نداشت به اين صورت عمل ميكنيم ! چون در همه ستون ها از عددِ ۱ تا ۲۰۰۲ داريم پس هر ستون دقيقا يكى از اعداد هاى ۱ تا ۲۰۰۲ را دارد ستونی كه ۲۰۰۲ را دارد را در نظر بگيريد ! خوب كوچيكترين عددِ اين سطر و ستون ۲۰۰۲ است !! پس اگر b=2002 آنگاه c>2002  و b*c>2002*2002حالا  اگر همه سطر ها و ستون ها يك عدد كوچكتر از ۲۰۰۳ داشتند آنگاه خانه اى كه ۲۰۰۲ در ان قرار دارد خانه اى است كه مشكل دارد

__________________________________________

سری 2:

1-اولين صحنه اى را در نظر بگيريد كه يا همه سطر ها حداقل يك سفيد دارند يا حداقل يكى از ستون ها يك سفيد دارند (حتما هم وجود دارد(

در اين زمان خاصیت مورد نظر وجود دارد فرض كنيد در هر سطر يك سفيد داريم حالت اول : اگر در اين مرحله همه ستون ها هم يك سفيد داشتند فرض كنيد در آخرين مرحله در خانهِ (i,j) سفيد اضافه كرديم پس تا قبل اين حرکت ستون j سفيد نداشته و ديگر ستون ها همه سفيد داشتند و اينكه تمام سطر ها غير از i سفيد داشتند ! براى هر سطر يك خانهِ سفيد را انتخاب ميكنيم و به سمتِ ستونِ j حركت ميكنيم ، حتما يك خانهِ خالى پيدا ميشود چون اگر از سفيد به سياه تبديل شود كه مسأله حال است و اينكه تا آخر نمى تواند سفيد بمانند چون در ستون j ما سفيد نداشتيم !! پس حداقل در همه سطر ها غير از i يك خانهِ خالى داريم خانهِ (i,j+1) و (i,j-1) حتما خالى هستند (حد اقل يكى از اين دو خانه وجود دارد) چون با سياه كه پر نمى شوند چون در اين حالت مسأله حال است سفيد هم نيستند چون اولين جايى است كه سطر i خانهِ سفيد دارد. پس ۱۰ خانهِ خالى داريم در صورتى كه ۹۱ خانه از ۱۰۰ خانه پر است پس تناقص ! حالت دوم: اين است كه ستونی وجود داشته باشد كه سفيد نداشته باشد !! مثلا ستونِ t بگيريد !! اگر از سفيدِ هر سطر به سمتِ ستون t حرکت كنيم حتما يك خالى خواهيم ديد (اثبات مانندِ بالا)

 

2- ابتدا ثابت ميكنيم براى n هاى فرد نمى توان فرض كنيد در مرحله ى اى ام Xi تا واحد حركت داده ایم
 n-1
مرحله داريم و بايد Xi ها متفاوت باشند <=

  n*(n-1)/2 =سیگما(Xi) است و باید به هنگ n  مخالف 0 باشد (چرا كه اگر 0 شود يعنى روى صندلىِ تكرارى خواهيم نشست)  كه اين در حالتى رخ ميدهد كه  nبه 2  بخش پذیر باشد !! پس n بايد زوج باشد براى n هاى زوج هم الگوریتم وجود دارد: به ترتيب حركت هاى زير را انجام مى دهيم(تعداد چرخش ها)
n-1,2,n-3,4,n-5,6,....,1,n-2
اگر رسم كنيد ميبيند كه اين الگوریتم صحيح است و اثبات هم ميشود ! يعنى در واقع اگر از صندلىِ ۱ شروع كنيم به ترتيب روى 1,n,2,n-1,3,n-2 ,…  مى شنيم !

3-هميشه آرمين ميبرد و در حق من ستم ميشود

خوب فرض كنيد در مرحله اول رامتين سكه X تومنى را انتخاب ميكند و آرمين خودش اين سكه را بر ميدارد الان آرمين X تومان پول دارد و رامتين 0 تومان پول دارد پس نوبتِ آرمين است كه انتخاب كند !! اگر آرمين در ادامه ببرد كه برده !! فرض كنيد در ادامه ارمين هيچ راه بردى نداشته باشد !! ارمين سکه ی X  تومنى را به رامتين مي دهد و حالا رامتين X تومان پول دارد و آرمين 0 تومان و نوبتِ رامتين است كه بر دارد ،يعنى در واقع شرايط بده خودش را به رامتین ميدهد !!! چون در اين حالت كسى كه X تومان داشت  می باخت پس الان آرمين ميبرد چون X تومان دست رامتين است

4-

فرض كنيد در G متغير هاى زير را تعريف ميكنيم !!
x
=تعداد ۳ راسى هايى كه هيچ یالی بين آنها نيست
y
=تعداد ۳ راسى هايى كه يك یال بين آنها وجود دارد
z
=تعداد ۳ راسى هايى كه دو یال بين آنها قرار دارد
t
=تعداد مثلث ها(گراف K3)

معادله های زیر بر قرار است

x+y+z+t=(3 az n)

z+t=sigma(2 az di)

y+2*z+3*t=m*(n-2)

اگر 2 تا معادله اول را جمع کنیم و آخری را کم کنیم x+t  به دست می آید که همان چیزی است که می خواهیم

5- تعداد مثلث هاى جهت در را x بگيريد و مثلث هايى كه يك یال در خلاف جهت دارد تا y بگيريد

y=sigma(2 az di)

x+y=(3 az n)

=>

x=(3 az n)- sigma(2 az di)

 

6- فرض كنيد هيچ كس سر جاى خود نيست يك گراف جهت دار مى سازيم كه به ازاى هر صندلى يك راس ميگذاريم اگر كسى كه در خانهِ (x,y) نشسته  و بليطِ صندلىِ  (z,t) را دارد (یا z=x  یا  y=t ) از رأس (x,y) به رأس        (z,t) یال ميكشيم حالا يك گراف داريم كه درجه  خروجی هر راس ۱ است. در اين گراف حتما يك دوره جهت دار وجود دارد چون فرض كنيد از رأس  x شروع ميكنيم و حركت ميكنيم از یال  خروجى اين راس جلو ميرويم به y سپس از y خارج ميشويم تا به رأس تكرارى برسيم تا به رأس تكرارى نرسيديم ميتوانيم به وسيله یال خروجى از اين راس خارج شويم ! خوب حالا كافيست وقتى دوره جهت دار را پيدا كرديم اگر در دور از رأس  (x,y)به (z,t) یال بود فردى كه در   (x,y)نشسته را به مكان (z,t) ببريم و (z,t) را به سر جاى خودش و ...

قسمت دو : حداكثر يك نفر !! مثال : فرض كنيد به  m+n-1نفر بليطِ صندلىِ (۱،۱(را فروختیم
خوب سطر اول و ستون اول پر ميشوند حالا به  n-1 نفر (2و1(را می فروشیم و به  n-1 نفر ( 3و1(را می فروشیم

... و به  n-1 نفر(1,m)را می فروشیم ولى هيچ كدام از اين آدم هايى كه بليطِ (1,x) را دارند نمی توانند سر جاى خود بشینند چون سطر اول پر شده است !! فقط كسى كه در(1و1) نشسته سر جاى خود است

 

 

+ نوشته شده توسط رامتین رطبی(سابق) در چهارشنبه 26 فروردین1388 و ساعت 23:9 |
گفتم نزديكِ مرحله ۲ هستيم و يه كم سوالهاى كامپيوترى آپ كنم بد نيست !!

۹۱-۱ مهره ی سياه در يك جدول ۱۰*۱۰ قرار دارد
در هر مرحله ۱  مهره ی سياه را بر ميداريم و در يك خانهِ خالى  مهره ی سفيد مي گذاريم
اين كار را تا زمانى انجام مى دهيم كه ۹۱ مهره ی سفيد داشته باشيم
ثابت كنيد لحظه ای وجود دارد كه در ۲ خانهِ مجاور مهره ی سياه و سفيد قرار بگيرد. (85/3/12)


۲ -يك پسر بچه n بار سوار يك چرخ و فلك با n صندلى ميشود بعد از هر مرحله او چرخ و فلك را در جهتِ عقربه هاى ساعت كمتر از يك دور كامل می چرخاند و روى يك صندلىِ ديگر می نشیند
تعداد صندلی هایی كه در هر بار ميگذرد را طول چرخش می نامیم !!
براى چه nهايى او ميتوانند سواره هر nصندلى شود به شرطى كه طول همه ى n-۱ چرخش متفاوت باشد(85/3/12)

۳ - رامتین و آرمين مي خواهند ۲۵ سكه به ارزشِ ۱ تا ۲۵ را بين خود تقسيم كنند در هر حركت يكى از آنها سكه را انتخاب ميكند و ديگرى تصميم ميگيرد كه اين سكه به چه كسى تعلق بگيرد
در ابتدا رامتین سكه را انتخاب مي كند و در هر مرحله كسى سكه را انتخاب مي كند كه در آن لحظه پول بيشترى داشته باشد !!
اگر پولشان برابر باشد كسى كه مرحله ى قبل سكه را انتخاب كرده اين مرحله هم او انتخاب ميكند
در پايان كسى كه پول بيشترى داشته باشد برنده است !!
چه كسى استراتژی برد دارد ؟(85/12/10)

۴ - مجموع تعداد مثلث هاى G و مكمل G را بر حسب m ( تعداد یال ها) و n (تعداد راس ها) و دنباله درجات  بیابید. (85/12/17)

۵ -تعداد دور های جهت دار به طول ۳ را در يك تورنمنت بر حسب n(تعداد راس ها) و دنباله درجات ورودى پيدا كنيد.
تورنمنت گراف كاملى است كه یال هاى آن را جهت دار كرده ايم (85/12/17)

۶ - صندلى هاى يك سينما به صورت يك مستطیل m*n چيده شده است

m*n بليط فروخته شده است ولى اشتباهاً براى بعضى صندلى ها بيش از يك بليط فروخته شده است
مسئول سالن افراد را طورى روى صندلی ها نشانده است كه هر كس در سطر يا ستون درستى نشسته است

ثابت كنيد ميتوان افراد را طورى نشاند كه هر كس يا در سطر خود باشد يا در ستون خود و حداقل يك نفر سر جاى خود نشسته باشد!!

مسئول سينما در بدترين حالت حداكثر چند نفر را ميتوانند سر جاى خود بياورد!!!(85/12/25)

اين گلچينى از سوال هايى بود كه من تو ماه اسفند سالى كه مرحله ۲ داشتم حل كردم !
سؤالات ۱،۲،۳،۵ و ۶ رو خودم حل كردم
و ۴ را با راهنمایی

+ نوشته شده توسط رامتین رطبی(سابق) در سه شنبه 18 فروردین1388 و ساعت 13:11 |
۱------------------->

ابتدا به خانه ها وزن مى دهيم وزن خانهِ اى برابر (F(i است(كه (F(i تابع فیبوناچی هست) 
متغیر W را مجموع وزن ها تعريف ميكنم !
ثابت ميكنم كه W همواره ثابت است و برابرِ سیگما F(i) i=0 تا i=n
در حركتِ نوع اول كه بديهى است كه ثابت میماند چون تعريف فیبوناچی است

F(i)=F(i-1)+F(i-2)l

در حركتِ دوم كافيست ثابت كنيم كه

2F(i)=F(i-2)+F(i+1)l
از طرف چپ شروع ميكنيم !

2F(i)=F(i)+F(i)=[F(i+1)-F(i-1)]+[F(i-1)+F(i-2)]=F(i+1)+F(i-2) :D
خوب پس W همواره ثابت است !

حالا كه ثابت كرديم W ثابت است كافيست ثابت كنيم كه

sigma F(i)i=0 ta i=n < P>

استقرا ميزنيم روى n براى n=۰ كه بديهى است !
حالا از t=>t+1
ميدانيم 

 sigma F(i) i=0 ta i=t<>


به طرفین معادله (F(t+۱ اضافه ميكنيم و اثبات می شود! 
پس هيچ وقت مهره ای در خانهِ n+۲ قرار نميگيرد چون مجموع تغيير خواهد كرد !

۲-------------------->

اگر گراف لوپ (یالی که دو سر آن یک راس باشد ، یا دوری به طول یک) یا یالهای موازی(دو یال که دو راس های مجاور مشترک دارند یا دوری به طول 2) داشته باشد که دوری که طول آن بر 3 بخشپذیر نباشد را یافته ایم ، پس فرض کنیم گراف ساده است.مسیر ماکسیمالی در گراف که راس a یک انتهای آن است را در نظر می گیریم.a باید حداقل با دو راس دیگر به جز راس مجاورش در مسیر ماکسیمال همسایه باشد زیرا مسیر ماکسیمال است و مسیر نمی تواند از طرف a بزرگ شود ، این دو راس را به ترتیب از طرف a به انتهای دیگر گراف ، x و y می نامیم . سه دور را در نظر می گیریم، دوری که شامل مسیر ax ویال ax می باشد  ، دوری که شامل مسیر xy  و دو یال ay  و ax است .و دوری که شامل مسیر ay و یال ayاست. فرض کنیم که طول دور اولی بر 3 بخشپذیر باشد پس طول مسیر ax برابر 3k-1 است.همچنین فرض کنیم طول دور سوم نیز برابر 3k* است ، پس طول مسیر xy  برابر 3k*-2 است . طول مسیر ay برابر است با مجموع طول این دو مسیر ، پس بر 3 بخشپذیر است ، پس طول دوری که شامل مسیر و یال ay است بر 3 بخشپذیر نیست (برابر 3i+1 است )پس چنین دوری در گراف وجود دارد.

۳----------------->
به صورتِ دلخواه یال ها را جهت دار مي كنيم چون زوج یال داريم ميتوانيم بگوییم كه زوج راس داريم كه درجهِ خروجی آنها فرد است چون سیگما درجه خروجی انها برابرِ تعداد یال هاست
حالا ۲ راس را در نظر ميگيريم كه درجهِ خروجی ان ها فرد است چون گراف همبند است پس مسيرى بين اين ۲ راس وجود دارد (نه لزوما جهت دار)
تمام جهت هاى یال های اين مسير را بر عكس ميكنيم ! 
راس هایی كه در وسط مسير هستند كه زوجیت درجه خروجی شان تغيير نمى كند(بديهى است خود تون اثبات كنين)
۲ رأس انتهایی هم تغيير مي كند يعنى از فرد تبديل به زوج ميشوند !
پس هر مرحله ۲ تا از راس هاى بد تبدیل به خوب مي شوند و چون تعداد آنها زوج تا است زمانى تعداد راس هاي بد ۰ ميشود.
۴--------------------->

ثابت ميكنم كه يك بازه سفيد وجود درِ كه همه سیاه ها را در بر مي گيرد و براى سياه ها هم به طورِ مشابه است (فقط جاى سياه و سفيد عوض ميشود)
اولين بازه ی سياه كه بسته ميشود و آخرين بازه ی سياهى كه شروع ميشود را در نظر بگيرين!
چون اين ۲ تا بازه هر كدام با k تا بازه ی سفيد اشتراك دارند پس يك بازه هست كه با جفت بازه هاى در نظر گرفته شده اشتراك دارد(اين را انتخاب ميكنيم). اگر همچين بازه ای نباشه بايد حداقل 2*k بازه سفيد داشته باشيم !
ثابت ميكنيم بازه ای كه انتخاب كرديم با همه بازه هاى سياه اشتراك دارد!
بديهى است كه همه بازه ها يك نقطه بين اولين پايان و آخرين شروع را دارد اگر نداشته باشد اين ۲ نقطه تغيير ميكند !(اثباتش به عهدۀ خود تون ديگه خيلى بدیهیه)

۵------------------>

الف)
جعبه با بزرگترين سيب را بر ميداريم و سپس بر اساسِ تعداد سيب ها جعبه ها را مرتب ميكنيم !
حالا فرض كنيد جعبه ی شماره ۱ كمترين سيب را دارد و به ترتيب تا ۹۸   تعداد سيب ها افزايش مى يابد !
جعبه ها را دست بندى ميكنيم و جعبه ی 2*i و1+ ( 2*i)  را در يك بسته ميگذريم !
حالا ۴۹ بسته داريم و ميخواهيم ۴۹ جعبه انتخاب كنيم!
از هر بسته جعبه ای را انتخاب ميكنم كه بيشترين پرتقال را دارد!
اين يك جعبه بر داشتن خوب هستش چون بديهى است بيشتر از نصف پرتقال ها را dadad و در بد ترين حالت جعبه ۱،۳،۵،۹۷ انتخاب شده به همراه 99!
كه چون ۹۹ بيشتر از ۹۸ ، سيب دارد و ۹۷>۹۶ ،۹۵>۹۴ ،….. ۳>۲ و ۱>=1
پس نصف سيب ها برداشتِ شده’اند!
ب) به شكل بالا بر ميداريم اما اين بر بعد از بر داشتن جعبه با بيشترين سيب دست ها را ۳ تايى در نظر ميگيريم و در هسته جعبه با بيشترين پرتقال را بر ميداريم !
باز هم درست ميشود!

J)ابتدا جعبه با بيشترين سيب را بر ميدارم و سپس جعبه با بيشترين پرتقال !
حالا ۹۸ جعبه دارم و ميخواهم ۴۹ جعبه بر دارم!
A=بیش ترین سیب B=بیش ترین  پرتقال !
خوب ميام ميگم اگه من بتونم جعبه ها رو ۲ دسته بكنم كه اختلافِ سيب هاى ۲ طرف كوچيك تر مساوىِAباشد و اختلافِ پرتقال اين دست كم تر مساوىِ Bباشد مسأله حل است!
چون اون دسته با بيشترين موز رو بر ميداريم و با اون ۲ تا جعبه !
موز ها كه بیشترن و سيب ها هم بیشترن چون در بد ترين حالت  ما كمترين سيب رو بر ميداريم كه چون اختلافشون از A كمترِه با اون آمدنِ جعبه با بيشترين سيب جبران ميشه و براى پرتقال ها هم همين طور!
از اين به بعد a_i ميشه سيب جعبه i و b_i ميشه پرتقال  جعبه i.
پس كافيه ثابت كنيم اگر 2x جعبه داشته باشيم و ميخواهيم x جعبه انتخاب كنيم كه همه a_i ها ازA  کوچیکترند وb_i ها از B کوچیکترند ميتوان دستi ها را به ۲ قسمت تقسیم كرد كه اختلافِ سيب ها حد اكثر A باشد و پرتقال ها B باشد !
اين حكم را با استقرا ثابت ميكنيم
استقرا ميزنيم روى كه. از كه به k+۲ ميرسيم!
همين !
استقرا به عهدۀ خودتون( خيلى هم بديهى نيست پس يه کم فكر كنيد ،نگيد چون نگفته خيلى بدیهیه )

۶----------------------------->

مسأله را با استقرا روى تعداد یال ها حل ميكنيم

پایه استقرا( m=2 تعداد یالها)
چون گراف همبند است پس میتوانیم بگوییم كه خود گراف حداكثر ۳ راس دارد و كمتر هم ندارد! خود گراف P-۳ است
فرض استقرا :گرافی با زوج یال و همبند را ميتوان به P-۳ افراز كرد!
گام استقرا:m==>m+2
مسيرِ ماکسیمم را در نظر ميگيريم !
فرض كنيد كه راس ها به ترتيب در مسير a1,a2،….،ax باشد (به بدیهیت x>=۳ است زيرا اگر كمتر باشد آنگاه بزرگترين مسير به طول ۱ است و چون گراف همبند است پس گراف حداكثر ۲ راس دارد و گراف ميتوانند حداكثر ۱ یال داشته باشد !)

1)اگر a2 همسايه به غير از a1 و a3 داشته باشد آنگاه اون راس را u مینامیم
ثابت ميكنم اگر ما یال (a1-a2) و (a2- u) را بر داريم گراف هنوز همبند خواهد ماند!( در اينجا تعريف از همبندی بدون در نظر گرفتن راس های درجه ۰ است)
اگر درجهِ a1 صفر شود كه مشكلى نيست و با تعريف همبندى تناقص ندارد!
اما اگر درجه يه a1 بيشتر از صفر باشد آنگاه ميدانيم تمام همسايه هاى a1 در مسير هستند چون اگر همسایه ای بيرون از مسير داشته باشد ميتوانيم طول مسير را افزايش بديم كه با ماکسیمم بودنش تناقص دارد!
پس هنوز a1 به a2 مسير دارد چون اگر a1 به يك راسى مثل at برود و سپس به a_t-1 سپس به a_t-2 ...
به a2 میرسد.
براى رأس u هم همين اثبات كافيست چون رأس u اگر ۰ شود كه با تعريف همبندی تناقص ندارد اگر هم همسايه داشته باشد باز هم همسايه هایش در مسير هستند چون اگر نباشند آنگاه مسير ماکسیمم نبوده !

2)اگر a2 همسايه ای به غير از a1 و a3 نداشته باشد مسير a1-a2-a3 را حذف ميكنيم. a2 كه درجه ۰ ميگيرد ،a3 هم كه به مسير وصل است.
فقط مى ماند a1:
اگر درجهِ a1 صفر شود كه حله
اگر هم ۰ نشود آنگاه همسايه در مسير دارد كه باز هم گراف همبند مى ماند!

پس گراف هم چنان همبند است و m یال دارد ! (طبق فرض استقرا مسأله حل است)

 

+ نوشته شده توسط رامتین رطبی(سابق) در جمعه 17 آبان1387 و ساعت 10:29 |

سلام بچه ها. خوبين که؟

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

همونتور که ميدونين استقرا يکی از ابزار هايه کاربرديه مرحله 2 است! تجربه ثابت کرده هر سال تو مرحله 2 دو سه تا سوال استقرا ميدن...!خلاصه ستقرا ممکنه خيلی هال به آدم بده ديگه...

بگزريم بريم سره مساله ها (البتّه ممکنه راه حلّی به جز استقرا هم داشته باشن)

1)يه گرافه کامل با ۱+۲*n راس داريم که يال ها شو با 3 رنگه 1 و 2 و 3 رنگ کرديم. ثابت کنين ميتونيم يه رنگ و n+1 راس رو انتخاب کنيم به طوری که اگه بقيه راس هايه گراف رو دور بريزيم بتونيم با استفاده از این رنگ از هر راسه این مجموعه  n+1 تايی به هر راسه ديگه اش رفت

2)يه گراف همبند با زوج تا يال داريم ثابت کنين که ميتونيم يال هايه این گراف رو به مسير هايه به طوله 2 افراز کنيم

3) (این مساله سخته!) ثابت کنين مجموعه رءوس هر گراف رو ميتونيم به دو تا مجموعه A۱ و A۲ افراز کرد به توری که درجه هر راس در هر يک از زير گرافهاي القايی A۱ و A۲ زوج باشد

4)مساله يه 4 مرحله دوّم دوره يه 13 ام يه راه هلّه خيلی کوتاه استقرايی داره!

5) هر مريخی 100 روزه متوالی عمر ميکنه. اگه مريخ کلّن 9734123871 روز عمر کرده باشه و کلّن تو تاريخه مريخ تويه مرّيخ 12391230151511 ای آدم زندگی کرده باشه ثابت کنين هدّقل100 روز هست که تويه اون روزها "فرد" تا مريخی رويه مريخ زندگی کرده باشه

خوب بستونه ديگه . همينم زيادتون بود!خودتون برين استقرا کار کنينD:

اديو

+ نوشته شده توسط افشين(سابق) در جمعه 25 فروردین1385 و ساعت 12:18 |
به نام اول آموزگار             كه اول درسش عشق بود

سلام ملت چطورين، خوبين؟ اي بابا همچنان كه همتون زنده‌ايد! خوب چه خبرا؟ چه ميكنيد؟ خوشيد؟ سلامتيد؟ منم هي، بد نيستم، همچنان غرق الافي!

- متاسفانه - وبلاگمون داره پيش ميره به سمت علمي شدن كه البته خدارا شكر هنوز با اين نويسندگان شازي كه داره جاي نگراني وجود نداره، براي همين واسه اينكه لااقل از اين افشين كم نيارم گفتم بيام 2 تا سوال بدم، البته اينا مال بعضي از امتحان‌هاي ceoi بوده كه روشون الگوريتم BTM2 اجرا شده. براي همين يه دفعه ممكنه راه حل‌هايي آسون‌تر از اون چيزي كه تو ذهنمه داشته باشن و بعبارتي سوال سوت بشه. اما در هر صورت سوال‌هاي خوبين و جدا اونقدر قشنگ هستند كه كاملا پتانسيلشو دارن شبيهشون توي مرحله دوم بياد. در مورد اينكه حلشون رو بذاريم يا نه هنوز بحثش نشده، ولي احتمالا حلشون رو خواهم گذاشت. در مورد اينكه بچه‌ها حل كنند و واسمون ميل بزنن تا ما تصحيحشون كنيم هم هنوز تصميمي گرفته نشده. ا راستي يادم رفته بود ممكنه بعضي از افراد كوته‌فكر -كه اميدوارم ما از اين بازديدكننده‌ها نداشته باشيم- ندونن BTM2 چيه. محض اطلاعشون بگم BTM2 مخفف "بچپونش تو مرحله 2" هست. كه به شخصه معتقدم تعداد(شايد اندكي) از سوال‌هاي مرحله 2 و بسياري از سوالهاي مرحله 3 توسط همين الگوريتم BTM2 ويا BTM2++ = BTM3 ساخته شدن. در هر صورت اين هم سوال‌ها:

1) n عدد طبيعي روي يك خط چيده شده‌اند. با نام‌هاي a1 تا an. حالا ما يك حركت مجاز داريم و آن اينست كه يك i بين 1 تا كمتر از n در نظر بگيريم و ai و a i+1 را حذف كرده به جاش ai - ai+1 رو ميذاريم يعني ميشه n-1 عدد. حالا هي اين كار رو تكرار ميكنيم تا بشه 1 عدد. مثلا يك نمونه براي n=4 اينگونه عمل ميكنه:

1 12 4 9          --2-->         1 8 9         --2-->         1 -1         --1-->       2

حالا فرض كنيد در حالت خاصي از سوال داشته باشيم ai=2^i يعني اعداد اوليمون (الزامي براي رعايت اين شرط در ادامه‌ي مراحل وجود ندارد) 2 و 4 و 8 و 16 و ... است. سوال اينه كه ما در آخر كه فقط يك عدد مي ماند، چند حالت مختلف براي آن عدد وجود دارد؟(در حالت كلي سوال اينه كه حداكثر چند عدد مختلف وجود دارد به ازاي هر اعداد ابتدايي)

2) n پله با شماره‌هاي 1 تا n جلوي دروازه‌ي شهر الموت قرار دارد.(دروازه در پله‌ي n ام است) تعدادي متناهي سرباز روي اين پله‌ها ايستاده‌اند(در پله‌ي iام ai سرباز). اين سرباز‌ها كه مال چنگيزخان هستند، ميخوان بريزن و الموت رو تصرف كنند. شهردار الموت كه آدم صلح طلبي(بي بخاري) هست، واسه‌ي اينكه كشتار زيادي نشه مياد پيشنهاد يه بازي ميده و چنگيزخان هم كه ميبينه بازي شازي هست، قبول ميكنه. بازي اينجوريه كه هر مرحله چنگيزخان همه‌ي سربازهاش رو به دو دسته (نه الزاما مساوي و نه الزاما ناتهي) تقسيم ميكنه، شهردار يكي از دسته‌ها رو انتخاب ميكنه و اون دسته بر ميگردن مغلستان واسه دوره‌ي طلا(كه درحقيقت دودر ميشن)، اما اون دسته‌ي باقيمونده هركدوم يك پله ميان بالا. و بازي همينجور ادامه پيدا ميكنه. حالا اگه حداقل يك سرباز برسه به دروازه‌ي الموت(پله‌ي nام) شهردار، الموت رو تسليم ميكنه، اما اگر همه‌ي سربازها برگشتن... خوب معلومه ديگه چنگيزخان از دنيا سوت ميشه...

نكته اينجان كه شهردار الموت خيلي باهوشه و اگه بتونه چنگيزخان رو شكست بده، شكستش ميده. اما از بدشانسي چنگيزخان هم يكي از بروبچ المپياد كامپيوتري اون زمان رو كه دوروبره الموت الاف بوده گرفته و در نتيجه چگيزخان هم بهترين بازيش رو ميكنه. و خوب چون ميدونيم الموت تصرف شده، حالا سوال اينه كه شرط اگر و فقط اگر براي اينكه چنگيزخان برده چيه؟(مسلما بر اساس ai ها)

البته توجه كنيد كه وقتي اون بنده خداي الاف رو ميگيرن به هيچوجه حاضر به همكاري نميشه(عرق ملي) اما چنگيزخان نامرد با وعده‌ي يه لبتاپ اونو فريب ميده و تازه بعد از فتح الموت بهش لبتاپ كه نميده هيچ، اونو ميكشه و بعدها وقتي كه ميخوان چنگيزخان رو بكشن، با لباس اون بيچاره خودش رو ميزنه جاي رئيس كميته‌ي كامپيوتر و فرار ميكنه.

بطور مثال اگر توي پله‌ي n-1ام 1 نفر و توي پله‌ي n-2ام 2 نفر ايستاده باشن، اونوقت چنگيزخان افراد پله‌ي n-2ام رو ميكنه يه دسته و اون يكي سرباز رو هم ميكنه يه دسته. حالا شهردار مجبوره اون دسته‌ي نفر توي پله‌ي n-1ام رو حذف كنه و در مرحله‌ي بعدي چنگيزخان 2 نفر در پله‌ي n-1ام خواهد داشت، كه با تقسيم اونها به 2 دسته خواهد برد.

 

خوب اين هم سوالاي من. خداييش قشنگن. راستي چون من از همه كمتر كار گرافيكي بلدم، قرار شده من قالب و اين سوسوليها رو جور كنم، گفتم كه اگه پيشنهادي چيزي بديد ممنون ميشم.

خوب ديگه زياد از وقت همچون طلايم گرفته شد، كسي كاري چيزي نداره؟ پس فعلا

يا حق

+ نوشته شده توسط وحيد(سابق) در سه شنبه 22 فروردین1385 و ساعت 22:51 |
سلام! خوبين؟ خوب الاهی شکر! الّافی خوش ميگزره؟
ما(بهتره بگم من:D) فرضمون اینه که همه اونايی که این وبلاگ رو ميخونن حداقل يکمی رو الّافی ميکنن تو زندگی
خوب حالا که نزديکه مرحله دوّمه (به درک) گفتيم بزار این مدّت رو يه سری مساله بگيم ! بهتره. بد نيست که با چند تا مساله يه نه خيلی اسون شروع کنيم!

۱)يه گروه داريم از ۱+ ۲*n نفر. از بين هر n+1 نفر حتماً يه نفر هست که بقيه رو ميشناسه. ثابت کنين 1 نفر هست که همه رو ميشناسه!

۲)يه جدوله n*n داريم که توش عدد هايه 1 و -1 و 0 رو نوشتيم. به طوری که تويه هر سطری دقيقن يدونه 1 هست و يدونه -1. هر باری ميتونی 2 تا سطر يا 2 تا ستون جدول رو بگيری و جايه اون 2 تا رو با هم عوض کنی .ثابت کنين ميتونيم به جدولی برسيم که جايه 1 ها و -1 ها نسبت به جدوله قبلی توش عوض شده.

۳)يه ترازوی 2 کفه ای داريم که وزنه اجسامه سمته راستش منهايه وزنه اجسامه سمته چپش رو به ما گزارش ميده! 27 تا وزنه به وزنهايه1و 3 و 9 و ... 3 به توانه 26 هم داريم.حداقل بار هايه استفاده از از ترازو برايه اینکه این وزنه ها رو به ترتيبه وزن مرتّب کنيم چند تاست؟

۴)يه جدول 200*200 داريم که خونه هاش با 2 رنگ رنگ شده! سفيدو سياه! اختلاف خونه هايه سفيد با سياه برابر 404 است!ثابت کنيد يه مربع 2*2 هست که تعداده فردی خونه سفيد داره!

۵)يه صفحه يه 100*100 داريم که خونه هاش با 4 رنگ رنگ شده .هر سطری و هر ستونی از هر رنگ دقيقن 25 تا داره. ثابت کنين ميتونيم 2 تا سطر و 2 تا ستون رو انتخاب کنيم به طوری که 4 تا خونه يه محل برخوردشون از 4 رنگه مختلف باشه!

۶)يه گراف ساده داريم که درجه يه هر راسيش حداقل 3 است ثابت کنين که يه دور تويه گراف وجود داره به توری که طوله دور مضربه 3 نباشه

يه مسله يه باحال( مرحله دوّمی نيست ولی من کلّن حال ميکنم با مساله يه با حال چه مرحله دوّمی چه غيره مرحله دوّمی):
ثابت کنين بازه (۱و ۰) با R متناظر است!( به نظره من که اگه حلّشو تا حالا نشنيدين حتماً بشينين حلّش کنين!
خوب ديگه بستونه. دستم درد نکنه!:Dخوش باشين
فعلاً خدا خافظ
+ نوشته شده توسط افشين(سابق) در سه شنبه 22 فروردین1385 و ساعت 13:5 |