سفرنامه‌ی IOI 2010 (المپیاد جهانی کامپیوتر سال ۲۰۱۰)

سلام

قسمت دوم سفرنامه هم آماده شد. برای دیدن این قسمت روی لینک «قسمت دوم» کلیک کنید. برای دیدن همه قسمت ها می تونید به پوشه یhttp://users.allamehelli.ir/~a_babayi/IOI2010/برید.

قرار شد بقیه ی قسمت ها رو هم مهران و بهروز بنویسن.

شب خوش!

جمع‌بندی و اعلام نتایج اولین آزمون هماهنگ شاززز

سلام

بالأخره وارد کردن کردن اطلاعات برگه‌ها تموم شد و ما آماده‌ایم که نتایج رو اعلام کنیم. اما قبلش یه مقدار در مورد امتحان:

به نظر ما سؤال‌های امتحان در رده‌ی «خیلی خوب و آموزنده» بود!
یک سؤال (سؤال ۱۱) به خاطر غلط بودن گزینه‌ها حذف شد که نمره‌ش به همه اضافه شد. قرار نیست بگیم که از قصد این اتفاق افتاده، اما خیلی وقت‌ها این اتفاق برای المپیادهای واقعی هم می‌افته.
در مورد بعضی سؤال‌ها بعضی‌ها می‌گفتن که صورت سؤال نامفهوم بوده، که به این نتیجه رسیدیم که اینطور نبوده. (خیلی ساده به این نتیجه رسیدیم!)
با توجه به تحلیل گزینه‌های انتخاب‌شده، سؤال ۱ سخت‌ترین، سؤال ۹ آسان‌ترین، سؤال ۸ گمراه‌کننده‌ترین سؤال‌های امتحان بودند.

امتحان حضوری به صورت هماهنگ در بیش از ۳۰ مدرسه برگزار شد و در مجموع حدود ۳۹۰ نفر شرکت کردن.

امتحان برخط هم به خوبی برگزار شد، و حدود ۴۰ نفر توش شرکت کردن، که در مجموع حدود ۱۰ تا برگه معتبر بود (چند مورد داشتیم که توی امتحان حضوری هم شرکت کرده بودند، بقیه هم پاسخ‌برگ‌شون رو خالی گذاشته بودن، که همگی حذف شدند)

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

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

موفق باشید

---

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

بایگانی سوالات مراحل اول و دوم

سلام بر همگی!

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

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

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

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

موفق باشید

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

سلام

این هم از آزمون اینترنتی که قولش رو داده بودیم! سه‌شنبه (بیست و سوم آذر) ساعت ۱۶ تا ۱۹ برگزار می‌شه!

برای شرکت در آزمون اینترنتی، به آدرس:

http://sh44zzz.gigfa.com/

مراجعه کنید. اول مشخصات‌تون رو پر کنید و کد برگه و رمز عبورتون رو دریافت کنید. بعد با کد برگه و رمز عبور وارد سیستم بشید. گزینه‌های مورد نظرتون رو انتخاب کنید و بعد پاسخ‌نامه‌تون رو ذخیره کنید. همین!

چند تا نکته:
۱. لطفا فقط یک کد برگه دریافت کنید.
۲. سامانه‌ی ثبت برگه رأس ساعت ۱۹ بسته می‌شه و دیگه نمی‌تونید برگه‌تون رو ذخیره کنید. پس حتما قبل از پایان امتحان این کار رو انجام بدید.
۳. هیچ هشداری برای نزدیک شدن به زمان پایان امتحان وجود نداره. خودتون حواستون رو جمع کنید.
۴. لطفا با اسم واقعی‌تون شرکت کنید.

سؤالات رو از آدرس:

http://s1.picofile.com/file/6210339034/1st_exam.pdf.html

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

موفق باشید!

پ.ن. احتمالا خبر بهتر اینه که بعد از آزمون دوباره بخش نظرات بر می‌گرده!

---

برای دریافت سؤالات از رمز rt7qu11o استفاده کنید.

---

آزمون اینترنتی به خوبی و خوشی برگزار شد. در طول امتحان مشکل خاصی به وجود نیومد. و بامزه‌ترین اتفاق امتحان یه مورد تقلب (!) بود که احتمالا برگه‌ش حذف می‌شه.

می‌تونید پاسخ‌نامه‌ی درست رو ازاینجادریافت کنید.

به زودی یه پست دیگه در مورد جمع‌بندی امتحان (شاید با جواب تشریحی) زده می‌شه.

---

توجه:کسانی که با اسم واقعی‌شون ثبت نام نکردن، اسم واقعی و کد برگه‌شون رو توی نظرات بگن تا اصلاح کنم. وگرنه برگه‌شون حذف می‌شه. (می‌تونید به صورت خصوصی برای نویسنده نظر بفرستید تا بقیه نبینن)

آزمون جمعه

سلام!

قرار بود یه مقدار در مورد امتحان بیشتر توضیح بدیم. امتحان ۲۴ تا سؤال ۵ گزینه‌ای هست و توی ۳ ساعت برگزار می‌شه. پیشنهاد ما اینه که مدارس امتحان رو ساعت ۹ شروع کنند و ساعت ۱۲ تموم کنند. اما اگه یه مقدار دیر بشه احتمالا مشکلی نداره.

سعی کردیم مبحث سؤال‌های امتحان به مرحله یک های واقعی نزدیک باشه. از لحاظ سختی، سؤال‌ها یه کم سخت‌تر از مرحله ۱ پارسال هستش. (چون احتمالش هست که مرحله ۱ امسال از مرحله ۱ پارسال سخت‌تر باشه)

در ضمن، برای کسانی که مدرسه‌شون اعلام آمادگی نکرده، احتمالا ۲-۳ روز دیرتر، امتحان رو به صورت آنلاین برگزار می‌کنیم. برای همین احتمالا بعد از برگزاری امتحان یه مدت نظرات بسته می‌شه تا در مورد سؤال‌ها بحث نشه و کسایی که می‌خوان امتحان آنلاین بدن، بتونن امتحان تازه‌ای رو ببینن.

لیست مدارسی که فعلا برای برگزاری امتحان اعلام آمادگی کردن:
شهید هاشمی‌نژاد مشهد (۱ و ۲)، فرزانگان مشهد (۱، ۲ و ۳)، فرهیختگان، شهید اژه‌ای اصفهان (۱ و ۲)، فرزانگان ۱ و ۲ اصفهان، دبیرستان‌های پسرانه و دخترانه‌ی امام صادق اصفهان، فرزانگان شیراز،  فرزانگان علامه محمد تقی آملی، فرزانگان شهرکرد، شهید صدوقی سمپاد یزد، علامه حلی ۳ تهران،  شهید بهشتی سنندج، شهید دستغیب ۱ شیراز، شهید سلطانی کرج، فرزانگان کرج، علامه حلی اراک، ملاصدرای شیراز، مفید ۱ و ۲، شهید بهشتی شاهرود، سلام یوسف‌آباد، تلاش، شهید بهشتی تنکابن، شهید بهشتی شاهرود، شهید بهشتی شهرری، سلام ایران‌زمین، فرزانگان ۲ ساری، شهید بهشتی مراغه، فرزانگان مراغه، فرزانگان تنکابن، حنان، شهید بهشتی قزوین، فرزانگان قزوین، علامه طباطبایی تهران

امتحان خوبی داشته باشید!

---

نمایندگان تمام مدارسی که قراره توی آزمون شرکت کنند، باید تا حالا کد برگه‌ها و صورت سؤال‌ها رو دریافت کرده باشن. در غیر اینصورت سریعا با ایمیل شاززز تماس بگیرید.

جواب سوالهای آنالیز ترکیبی

سلام

جواب سوالهای پست قبلی رو میتونید ازاینجادانلود کنید.

شاد باشید.

سوالهای آنالیز ترکیبی

سلام

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

موفق باشید.

۱- ۱۵ تیم در یک تورنمنت شرکت کرده‌اند. هر تیم ۷ برد و ۷ باخت دارد. به چند طریق میتوان ۳ تیم از میان آنها انتخاب کرد به طوری که هر کدام در بین خودشان یک برد و یک باخت داشته باشند؟

۲- ثابت کنید تعداد رشته های n تایی از صفر و یک به طوری که هر دو تا حداقل در سه مکان متفاوت باشند حداکثر برابر (۲ⁿ/(n+1 است.

۳- یک کمیسیون ۴۰ بار تشکیل جلسه داده است. در هر جلسه ۱۰ عضو کمیسیون شرکت کرده‌اند. در ضمن هیچ دو عضوی از کمیسیون بیش از یک بار با هم در جلسه ها نبوده‌اند. ثابت کنید تعداد اعضای کمیسیون از ۶۰ بیشتر است.

۴- دنباله ای از اعداد ۱ تا ۹ داده شده است. ابتدا سه جمله ی اول دنباله را به صورت صعودی مرتب می‌کنیم.  سپس جملات ۳ و ۴ و ۵ را به ترتیب صعودی مرتب می‌کنیم. بعد جملات ۵ و ۶ و ۷ و در نهایت جملات ۷ و ۸ و ۹ دنباله را به صورت صعودی مرتب می‌کنیم. به ازای چند دنباله اولیه متشکل از اعداد ۱ تا ۹، دنباله ی به دست آمده

۹ ، ۸ ، ۷ ، ۶ ، ۵ ، ۴ ،‌ ۳ ،‌ ۲ ، ۱ می‌باشد؟

۵- در یک اتاق دو کتابخانه وجود دارد. یکی k قفسه و دیگری k+m قفسه دارد. تعدادی کتاب در کتابخانه ی اول وجود دارد و میدانیم هیچ یک از k قفسه ی این کتابخانه خالی نیست. کلیه کتابهای این کتابخانه را بر می‌داریم و در کتابخانه ی دوم قرار می‌دهیم به طوری که باز هیچ یک از k+m قفسه ی این کتابخانه خالی نباشد. کتابی را «ویژه» می‌نامیم که تعداد کتابهای هم قفسه با این کتاب در حالت اول بیش از حالت دوم باشد. ثابت کنید حداقل m+1 کتاب ویژه وجود دارد.

۶- n تیم فوتیال در یک دوره مسابقه شرکت کرده‌اند. هر دو تیم دقیقاً‌ یک بار با هم مسابقه می‌دهند. در هر بازی به برنده ۲ امتیاز، به بازنده صفر امتیاز و در صورت تساوی به هر یک از دو تیم ۱ امتیاز تعلق می‌گیرد. ثابت کنید در پایان مسابقات اختلاف امتیاز بین هر دو تیم متوالی در جدول امتیازات حداکثر n است.

۷- 12k نفر در یک مهمانی شرکت کرده‌اند. هر نفر دقیقاً با 3k + 6 نفر دیگر از مهمانان دست می‌دهد. همچنین می‌دانیم تعداد افرادی که با هر [هر] دو نفر دست می‌دهند،‌ عددی ثابت است. تعداد افراد شرکت کننده در این مهمانی را تعیین کنید.

۸- تعداد زیرمجموعه های لااقل دو عضوی مجموعه ی {۱، ۲، ۳، ... ، ۲n} که مجموع هر دو عضو متمایز آنها از ۲n بزرگتر است،‌ چند تاست؟

آزمون آزمایشی مرحله ۱

سلام! خوبید؟ خوش میگذره؟ ...؟ خب خدارو شکر! پس میرم سر اصل مطلب: انشاالله میخوایم واستون یه آزمون آزمایشی مرحله ۱ برگزار کنیم!


این آزمون تو مدارس خودتون به صورت حضوری (شبیه‌سازی جلسه امتحان) برگزار می‌شه (به صورت همزمان در تعداد زیادی از مدارس کشور)، بعد هم پاسخنامه‌ها به دست ما می‌رسه و ما صحیحش می‌کنیم و نمره‌هاش رو بهتون اعلام می‌کنیم! تاریخ آزمون صبح جمعه ۱۹ آذر ۸۹ هستش و تمام تلاشمون رو می‌کنیم که دقیقا تو همین تاریخ برگزار بشه (حالا اگه مجبور شدیم تاریخ رو عوض کنیم دیگه مجبور شدیم خب!)
در مورد سبک سوالات و تعداد سؤالات و تعداد گزینه‌ها و مدت امتحان و ... هم فقط میتونم بگم که ما تمام تلاشمون رو می‌کنیم که شبیه مرحله ۱ باشه! :دی

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


یادآوری: ایمیل شاززز این بود: sh44zzz [AT] gmail [DOT] com

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

دومین مسابقات اینترنتی برنامه‌نویسی دانش‌آموزی ایران

سلام

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

مسلماً شرکت توی این مسابقه به همه‌ی علاقه‌مندها توصیه می‌شه (مخصوصاً از نوع المپیاد کامپیوتری)
من سعی می‌کنم اطلاعات بیشتری در مورد مسابقه از برگزارکننده‌ها بگیرم و به همین پست اضافه کنم. (البته توی سایت مسابقه هم توضیحات خوبی در مورد نحوه‌ی برگزاری، مقالات آموزشی، آرشیو سؤالات و ... هست که می‌تونید ازشون استفاده کنید.)

یادتون نره اگه می‌خواید شرکت کنید باید از طریق سایت مسابقاتثبت نامکنید.

به‌روز‌رسانی:اطلاعات بیشتر در مورد ISPC، به نقل از برگزارکنندگان:

«هدف اصلی ispc ایجاد محیطی برای پیشرفت دانش‌آموزان راهنمایی و دبیرستان در زمینه‌ی علوم کامپیوتر است. ispc به محدوده‌ی خاصی از علوم کامپیوتر محدود نمی‌شود و در طول زمان ممکن است مباحث جدیدی به آن اضافه شود. سطح مطالب و مسابقه‌های ispc برای دانش‌آموزان متوسط و بالا در نظر گرفته شده است. دانش‌آموزانی که در یک موضوع خاص سطح خیلی بالایی دارند، شاید مسابقه‌های پیکارجو در آن زمینه نیابند و این طبیعی است.
در زمینه‌هایی که با المپیاد کامپیوتر  اشتراک دارند، تخمین ما این است که مطالب برای بیشتر دانش‌آموزانی که به دوره‌ی المپیاد راه نیافته‌اند می‌تواند مفید باشد. البته در صورتی که افراد بیشتری کمک کنند شاید بتوانیم بخش مخصوص المپیادی‌ها را هم اضافه کنیم، اما به نظر می‌رسد اگر کارهای مخصوص المپیاد توسط باشگاه دانش‌پژوهان جوان انجام شود، منسجم‌تر و بهتر صورت می‌گیرد.
البته ماهیت و فلسفه ispc هنوز در حال شکل گرفتن است و این به خاطر نوپا بودن و تکراری نبودن این جریان است. امیدواریم که با کمک دوستان این جریان به جریان موفقی مبدل بشود.»

نوشته شده توسط سید مهران خلدی(سابق) در پنجشنبه ۲۰ آبان۱۳۸۹ و ساعت 0:1 |

جواب "چند تا سؤال"

خب هفته پیش مهران پست «چندتا سؤال» رو داده بود که توی این پست راه حل اون سؤال‌ها رو می‌گیم:

۱- برای حل این سوال از استقرا استفاده می‌کنیم. پایه استقرا: برای n=۱، عدد مورد نظر ۲ است. هر عدد n+۱ رقمی مورد نظر را بر حسب عدد n رقمی به این صورت می‌سازیم:
اگر عدد n رقمی بر ۲^n+۱بخشپذیر بود آن را بعلاوه ۲×۱۰ⁿمی‌کنیم و در غیر این صورت آن را بعلاوه ۱۰ⁿمی‌کنیم تا عدد به دست آمده بر ۲^n+۱بخش‌پذیرباشد.

۲- چون ۳۹ عدد متوالی داریم می‌توان گفت که حداقل ۲۰تای آنها در یک بازه ۱۰۰تایی (یعنی بین۱۰۰×kو۱۰۰×(k+۱)) هستند. با استفاده از اصل لانه کبوتری می‌توان ثابت کرد که مجموع ارقام یکی از این ۲۰ عدد بر ۱۱ بخشپذیر است (اثبات بر عهده خواننده!)

۳- همانطور که در راهنمایی پست قبل اشاره شد "عدد مورد نظر، برابر میانگین تمام اعداد یادداشت شده به ازای جایگشت‌های مختلف افراد است." برای محاسبه مجموع اعداد یادداشت شده می‌توان در نظر گرفت که هر عدد چند بار در جای درست خود ظاهر شده است. مثلا می‌خواهیم ببینیم عدد ۱ چند بار در جای درست خود در جایگشت آمده است، فرض میکنیم که عدد ۱ در جای اول (جای درست) قرار دارد. در این صورت برای دیگر اعداد(n-۱)!حالت وجود دارد. پس ۱ در(n-۱)!جایگشت در جای خود است. چون n عدد داریم در مجموعn×(n-۱)!بار اعداد در جای درست خود قرار گرفته‌اند. یعنی مجموع اعداد نوشته شده برابرn!و میانگین آنها برابرn! ÷ n! = ۱خواهد بود.


۴- جعبه ها را براساس تعداد سیب‌ها به صورت افزایشی مرتب می‌کنیم. اگر تعداد گلابی‌ها در جعبه‌های فرد بیشتر از نیمی از کل گلابی‌ها بود همان جعبه‌ها را (به همراه جعبه آخر برای حالت n زوج) انتخاب میکنیم. در غیر این صورت جعبه های زوج را (به همراه جعبه آخر برای n فرد و یا هر یک از جعبه های فرد برای n زوج) انتخاب میکنیم. در این صورت حداقل نیمی از سیب‌ها و نیمی از گلابی‌ها را در[n÷۲]+۱تا از جعبه‌ها خواهیم داشت.


۵- سوال از ما گرافی با n راس می‌خواهد که درجه‌ی هیچ ۳ رأسی از آن برابر نباشد. برای ساختن این گراف (برای nهای زوج)n÷۲از رئوس را در بالا وn÷۲را در پایین قرار می‌دهیم. هر رأس از بالا را، به تمامی رئوس پایینی که در سمت چپ آن قرار ندارند وصل می‌کنیم. (به این ترتیب هر رأس پایین هم به تمامی رئوس بالایی که در سمت راست آن قرار ندارند وصل می‌شود). به این ترتیب دنباله‌ی درجات گراف حاصل «۱، ۱، ۲، ۲، ...،n÷۲،n÷۲» خواهد بود.) برای n فرد کافی است یک رأس با درجه‌ی ۰ به گراف اضافه کنیم)