صفحه ۳۱
آمادگی برای مرحله دوم المپیاد کامپیوتر
ما هم خوبیم ، شکر!
از عنوان این پست پیداست که در چه مورد می خوام باهاتون صحبت کنم. آفرین ، مرحله 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 ( معروف به "اس جی یو"! )
سایت های دیگه هم هست که توی پیوند ها می تونید پیدا کنید.
فعلا همینا کافیه! اگه چیزی از قلم افتاده بود تو نظرات بگین تا پست رو به روز رسانی! کنم.
۱۳۸۸/۱۱/۲۳ · ۱۱:۴۹
کلید مرحله ۱
کد یک:
سوال ۱: گزینه د
سوال ۲: جواب ۴۴ هستش که تو گزینه‌ها موجود نیست
سوال ۳: گزینه ه .. برای هر مربع حساب کنید که تو چندتا مستطیل هست
سوال ۴: گزینه ب .. با استفاده از قضیه‌ی باقیمانده‌ی چینی
سوال ۵: گزینه ج
سوال ۶: گزینه د .. حداکثر فاصله رو باید از نقطه‌های سیاه بدست بیاورید
سوال ۷: گزینه ب .. a در نهایت برابر با تعداد صفرهای x در مبنای ۲ می‌شود
سوال ۸: گزینه ج
سوال ۹: گزینه ب
سوال ۱۰: گزینه ب
سوال ۱۱: گزینه ه
سوال ۱۲: گزینه د
سوال ۱۳: گزینه ه .. از این استفاده کنید که جمع هر ستون یا سطر باید ۱۵ باشد
سوال ۱۴: گزینه ه .. مجموع قدرت شهرها صفر می‌شود
سوال ۱۵: گزینه ه
سوال ۱۶: گزینه الف
سوال ۱۷: گزینه الف
سوال ۱۸: گزینه ج
سوال ۱۹: گزینه ب .. از این که می‌دانیم حتما یا ۰-غالب است یا ۱-غالب استفاده کنید
سوال ۲۰: گزینه ج .. با استفاده از تقسیم رئوس غیر از رأس وسط به سه دسته
سوال ۲۱: گزینه الف
سوال ۲۲: گزینه ج
سوال ۲۳: گزینه ب .. فقط جایگشت چهارم را می‌توان ساخت
سوال ۲۴: گزینه الف .. با استفاده از گراف جایگشت
سوال ۲۵: گزینه د .. حالت‌هایی مطلوبند که صفر، یک، شش یا هفت تا به چپ حرکت کند
**************************************
کد دو:
سوال ۱: گزینه ه .. برای هر مربع حساب کنید که تو چندتا مستطیل هست
سوال ۲: جواب ۴۴ هستش که تو گزینه‌ها موجود نیست
سوال ۳: گزینه ب .. با استفاده از قضیه‌ی باقیمانده‌ی چینی
سوال ۴: گزینه د
سوال ۵: گزینه ب .. a در نهایت برابر با تعداد صفرهای x در مبنای ۲ می‌شود
سوال ۶: گزینه د .. حداکثر فاصله رو باید از نقطه‌های سیاه بدست بیاورید
سوال ۷: گزینه ج
سوال ۸: گزینه ه
سوال ۹: گزینه ج
سوال ۱۰: گزینه ب
سوال ۱۱: گزینه ب
سوال ۱۲: گزینه ه .. مجموع قدرت شهرها صفر می‌شود
سوال ۱۳: گزینه ه
سوال ۱۴: گزینه ه .. از این استفاده کنید که جمع هر ستون یا سطر باید ۱۵ باشد
سوال ۱۵: گزینه د
سوال ۱۶: گزینه الف
سوال ۱۷: گزینه ج
سوال ۱۸: گزینه الف
سوال ۱۹: گزینه الف
سوال ۲۰: گزینه ب .. از این که می‌دانیم حتما یا ۰-غالب است یا ۱-غالب استفاده کنید
سوال ۲۱: گزینه ج
سوال ۲۲: گزینه ج .. با استفاده از تقسیم رئوس غیر از رأس وسط به سه دسته
سوال ۲۳: گزینه الف .. با استفاده از گراف جایگشت
سوال ۲۴: گزینه د .. حالت‌هایی مطلوبند که صفر، یک، شش یا هفت تا به چپ حرکت کند
سوال ۲۵: گزینه ب .. فقط جایگشت چهارم را می‌توان ساخت
**************************************
۱۳۸۸/۱۱/۰۱ · ۰۷:۴۳
قبول شدگان دوره ی ۱۰ روزه
سال سومی‌ها:
| ردیف | نام | نام خانوادگی | شهر | آموزشگاه |
| 1 | کیانا | احسانی | تهران | فرزانگان |
| 2 | آریاز | اقبالی | تهران | علامه حلی |
| 3 | محمد | پدرام فر | رشت | میرزاکوچک‌خان |
| 4 | سیدمحمد | چاوشیان | تهران | علامه حلی |
| 5 | امیدعلی | رئوفچی | تهران | سلام۱ |
| 6 | سهند | رجبی | تهران | علامه طباطبایی۱ |
| 7 | علی | رزم‌آرا | شیراز | شهید دستغیب |
| 8 | پریا | رشیدی‌نژاد | کرمان | فرزانگان |
| 9 | آزاد | زرشاد | ارومیه | شهید بهشتی |
| 10 | مهرداد | زمردیان | دزفول | شیخ مرتضی انصاری |
| 11 | پارسا | سعادت پناه | تهران | علامه حلی |
| 12 | امیرحسین | شاپوری | تهران | علامه حلی |
| 13 | علی | صادقی | شیراز | شهید دستغیب |
| 14 | علیرضا | عموزاد مهدیرجی | تهران | علامه حلی |
| 15 | زهرا | معدنی فاروج | تهران | فرزانگان۲ |
| 16 | پردیس | ملک‌زاده | اصفهان | فرزانگان |
| 17 | محمد جواد | نادری بنی | شهرکرد | شهید بهشتی |
| 18 | پیمان | نعمت اللهی | تهران | سلام۱ |
سال دومی‌ها:
| ردیف | نام | نام خانوادگی | شهر | آموزشگاه |
| 1 | اقبال | سرجمعی | تهران | علامه حلی |
| 2 | محمدامین | شعبانی | کرج | شهید سلطانی |
| 3 | محمدامین | صباغیان | کاشان | شهید بهشتی |
| 4 | حامد | صالح محمدآباد | تهران | علامه حلی |
| 5 | صدرا | علیمی عقدائی | یزد | شهید صدوقی |
| 6 | علیرضا | فرهادی | قزوین | شهید بابایی |
| 7 | محمدحسن | گل محمدیان | تهران | مفید۱ |
| 8 | هادی | مؤذن | بناب | علامه طباطبایی |
| 9 | امیرعلی | معین‌فر | تهران | علامه حلی |
| 10 | محمدرضا | ملکی | تهران | علامه حلی |
| 11 | محمدرضا | منتظری | تهران | علامه حلی |
| 12 | محمدرضا | ناطقی | یزد | شهید صدوقی |
۱۳۸۸/۱۰/۲۷ · ۱۱:۲۹
امتحان آزمایشی مرحله ۱
باشگاه امسال یک امتحان آنلاین سراسری برگزار می کنه. شما می تونید توی سایتhttp://www.yscazmoon.irثبت نام کنید. البته سایت از فردا ( شنبه 19 دی ) راه اندازی می شه. برای واقعی تر! شدن نتایج ، به دوستانتون اطلاع بدین و به مسئولین مدرسه تون بگین که به همه ی بچه ها اطلاع رسانی کنن . پس اطلاع رسانی یادتون نره!
پی نوشت: بیاین، اینم امتحان آنلاین ، دیگه چی می خواین؟!
۱۳۸۸/۱۰/۱۸ · ۰۷:۳۶
مرحله ۱
همون طور که می دونید مرحله ۱ نزدیکه. بهترین کار توی این ایام امتحان گرفتن مرحله ۱ ها از خودتونه. چون مرحله ۱ ، تقریبا بلافاصله بعد از امتحانات ترم اوله ، بهتره از همین الان شروع کنین تا قبل از مرحله ۱ ، حداقل ۵ تا مرحله ۱ رو داده باشین. اگه سال اولی هستین، این چند سال اخیر رو سوالاش رو نبینید و امتحان ندین تا سال دیگه که براتون مهمتره سوال داشته باشین که امتحان بدین. پس جو گیر نشین همه مرحله ۱ ها رو بدین که سال دیگه ندونین چه کار کنین!
مثل امتحان وقت بذارین و توی اون وقت سوالات رو حل کنید. تفریحی و پراکنده سوال حل نکنید. بعد از امتحان حتما جواب های صحیح رو چک کنید و اگه از کتاب استفاده می کنید ، جواب های صحیح سوالات رو بخونید. ( حتی سوالاتی که حل کردین، چون ممکنه یه ایده جدید یاد بگیرین. )
انتشارات خوشخوان برای مرحله ۱ ها کتاب داره، ولی نمی دونم آخرین نسخه اش الان تا چه سالی رو داره. اما می تونید سوالات رو از اینترنت بگیرین ، کلیدش رو هم توی سایت باشگاه ، همین وبلاگ یا وبلاگهای دیگه پیدا کنید.
همین دیگه ، موفق باشین! امتحان هم ساده خواهد بود ، اصلا نگران نباشید! ( برنامه نویسی هم نمی خواد!!! )
پ.ن. : الان از توی کتابخونه باشگاه پست می زنم و سرعت اینترنتش کمه!! اگه کسی سایتی پیدا کرد که سوالات مرحله اول رو داشته باشه ، تو قسمت نظرات لینکش رو بده.
۱۳۸۸/۰۹/۲۶ · ۱۱:۳۳
جواب ها
-تو جواب ها بیشتر ایده های کلی رو نوشتم تا خودتون رو بقیه اش فکر کنید. البته نکات جزیی خیلی مهمه و بخش مهمی از راه حله. بیشتر جوب زدن ها هم تو همین نکات جزیی رخ می ده که معمولا وقتی جواب رو می نویسید معلوم میشه.
-اینا جواب هاییه که به ذهن من رسیده و ممکنه جواب های بهتر و قشنگ تری هم وجود داشته باشه. اگه کسی خواست می تونه جواب های خودش رو تو نظرات بنویسه.
اینم جواب ها:
۱- افراز متوازن:
اول یه لم مهم رو ثابت کنید: صورت لم همان صورت مساله است با این تفاوت که از شما خواسته اند وزنه ها را به دو دسته تقسیم کنید به طوریکه اختلاف آنها ۲ به توان k باشد. k را به شما می‌دهند و می دانید ۲ به توان k از همه وزنه ها مقدارش اکیدا بیشتر است. باید ثابت کنید تعداد راه های افراز وزنه ها با این شرایط صفر یا توانی از دو است.
این لم را می توانید با استقرا روی k و حالت بندی روی تعداد وزنه هایی که وزنشان ۲ به توان k-1 است(در گام استقرا) ثابت کنید.
مساله اصلی را نیز می توان با استقرا روی وزن بزرگترین وزنه و حالت بندی روی تعداد این وزنه ها و استفاده از لم بالا اثبات کرد.
۲- سپید و سیاه:
یک راه‌حل منطقی این است که ثابت کنید تا وقتی حداقل دو خانه سیاه داریم می توان تعداد خانه های سیاه را کم کرد. برای این کار دو خانه سیاه را در نظر بگیرید که فاصله شان از همه کمتر است. با این فرض می توان نتیجه گرفت که در زیر مستطیلی که این دوخانه در گوشه های قطری‌اش هسند هیچ خانه سیاه دیگری نیست. حالا با حالت بندی روی طول اضلاع این مستطیل سعی کنید تعداد خانه های سیاه را کاهش دهید. به این نکته هم دقت کنید که m و n (طول اضلاع جدول اصلی) هر دو حداقل ۳ هستند.
۳- گراف یابی:
ثابت کنید تعداد پرسش ها حداقل (C(2, n است. یعنی حالتی وجود دارد که مملی مجبور است به ازای هر جفت از راس ها از ففلی یک سوال بپرسد. (اگر ففلی به ازای هر سوال که مملی می پرسد بگوید فاصله آن دو راس بی نهایت است، یعنی آن دو به هم هیچ مسیری ندارند، مملی مجبور است همه جفت ها را از ففلی بپرسد).
۴- ماتریس کم تنوع:
کافی است که از روی یک ماتریس a*a با تنوع p و یک ماتریس b*b با تنوع q، یک ماتریس (ab)*(ab) با تنوع p.q بسازید.
موفق باشید.
خداحافظ!
۱۳۸۸/۰۹/۱۸ · ۰۷:۵۶
سوال.
به نام خدا
سلام به همه رفقا. عید قربان با کمی تاخیر مبارک! عید غدیر هم پیشاپیش مبارک!
آقا با اینکه تو بخش نظرات پست قبلی کلی بحث شد و من خودم شخصا اعمال نفوذ کردم ولی بازم طرفداران سوال های مرحله دو (طی یک نقشه حساب شده)، نظرسنجی رو به نفع خودشون تموم کردند! به هرحال چون اینجا دموکراسی کامله! ما هم به رای اکثریت احترام می ذاریم و تو این پست جندتا سوال می ذارم. (البته قرار بود حسام سوال بذاره اما به خاطر مشکلاتی نشد).
اما قبل از اینکه سوال ها رو بذارم چندتا نکته می گم:
- من خودم به نظرم الان سوال تئوری نمی‌ذاشتیم بهتر بود. چندتا دلیل هم دارم. اول اینکه به خاطر تغییرات المپیاد کامپیوتر سبک سوالات معلوم نیست چی جوری باشه. دوم اینکه سوال هایی که ما می ذاریم اکثرا از همون منابعیه که در دسترس همه هست (مثل کتاب های شوروی و وست و استراتژی و ..)، به جز اونایی که تو دوره دیدیم و ممکنه برای شما جدید باشه(این سوال هایی هم که در ادامه می‌نویسم ماله دوره تابستونیه خودمونه). سوم اینکه من تو آرشیو وبلاگ یه نگاه کردم دیدم کلی سوال تئوری وجود داره که می تونید از اون ها هم استفاده کنید. خب همین چندتا دلیل بسه دیگه!(D:).
- با این اوصاف چون ملت خواستند سوال بذاریم من ۴تا سوال می ذارم. این سوال هایی که خواهم نوشت مال امتحان های تئوری تابستون پارسال هستند که طراحاشون آقای زادی مقدم و آقای مهینی بودن.
- من پیشنهاد می کنم تا چند روز کسی در مورد جواب سوال ها تو بخش نظرات چیزی ننویسه، بعدش رو جواب ها بحث می کنیم. البته در مورد خود سوال ها یا چیزای دیگه اگه خواستید می تونید نظر بدید.
اینم سوال ها:
۱-افراز متوازن:
تعدادی عدد طبیعی که هر یک توانی از دو هستند به ما داده اند. می دانیم که از هر توان دو حداکثر دوتا به ما داده شده است. مثلا ممکن است به ما اعداد ۱و۱و۲و۴و۸و۳۲و۳۲ را بدهند. ثابت کنید تعداد روش‌های افراز این اعداد به دو دسته برابر یا صفر یا توانی از دو است. مثلا اعداد بالا را تنها به شکل (۸و۳۲) و (۱و۱و۲و۴و۳۲) می‌توان به دو دسته برابر افراز کرد.
۲-سپید و سیاه:
خانه های یک جدول m*n را با رنگهای سفید و سیاه رنگ کرده‌اند. ما در هر مرحله می‌توانیم یک زیر مستطیل این جدول را به شرطی که (این زیر مستطیل) شامل لااقل دو خانه سیاه باشد، انتخاب کرده و رنگ کل خانه های این زیرمستطیل را عوض کنیم. ثابت کنید که اگر m و n هر دو از ۲ بیشتر باشند، با تعدادی از این حرکات می توان به جدولی برسیم که حداکثر یک خانه سیاه دارد.
۳-گراف یابی:
ففلی یک گراف ساده n-راسی روی کاغذ کشیده است و به مملی نشانش نمی دهد. مملی در هر لحظه دو راس را انتخاب می کند و ففلی فاصله آن ها را به مملی می گوید. کمترین تعداد سوال که مملی باید بپرسد تا از شکل گراف آگاه شود بر حسب n چند است؟
۴- ماتریس کم تنوع:
یک ماتریس n*n که با اعداد ۱ تا n*n پرشده است داریم. رتبه یک درایه در این ماتریس برابر تعداد اعداد بزرگتر از درایه در کل سطر و ستونش می باشد. بنابراین رتبه هر درایه عددی بین ۰ تا 2-2n است. تعداد رتبه های مختلف که در این ماتریس مشاهده می شود برابر تنوع آن است. کترین تنوع در بین همه‌ی ماتریس‌های n*n با درایه های متفاوت را (T(N بنامید. ثابت کنید:
T(ab)
موفق باشید.
خداحافظ!
۱۳۸۸/۰۹/۰۹ · ۱۹:۵۹
آموزش الگوریتم
سلام.
آقا راستش تصمیم گرفتم چندتا از الگوریتم هایی رو که معمولا تو دوره نقره-طلا گفته میشه رو اینجا به صورت آموزشی بنویسم. این مطالب هم می تونه به درد بچه هایی که الان تو دوره هستند بخوره، هم به درد اونایی که الان تو دوره نیستند و می خوان از بچه های دوره عقب نمونند. تصمیم داشتم اولین الگوریتمی که میگم 2sat باشه، ولی فکر کردم قبلش از شما یه نظر سنجی بکنم تا اگه کسی نمی‌خواد بی خودی پست نزنم.
موفق باشید.
علی
۱۳۸۸/۰۸/۲۷ · ۲۰:۳۰