صفحه ۹

نگاهی گذرا به المپیاد کامپیوتر

سلام بچه های خوبی که شاز را دنبال می کنید. :)

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

اول از همه یه سوال مهم. چرا المپیاد؟

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

حالا بحث مدالشم که بذاریم کنار ‍, کلی خوبی های دیگه داره که ارزششون خیلی از مدال اوردن بیشتره. مثلا اینکه شما وقتی به مسائل فکر می کنید و ایده های مختلف می زنید ذهنتون پرورش پیدا می کنه و این تو اینده خیلی به دردتون میخوره.همین طور تو المپیاد یاد می گیرید به مسائل از دید دیگه ای نگاه کنید و اون موقع می فهمید که مسائل چه قدر راحت تر می تونن حل بشن.

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

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

حالا که فهمیدیم المپیاد خوبه می خواهیم بدونیم چی کار باید بکنیم تا المپیادی موفقی بشیم. برای همین اول مراحل المپیاد رو توضیح میدم براتون.

مراحل المپیاد کامپیوتر:

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

مرحله‌ دوم: شامل یک آزمون تستی و یک آزمون تشریحی که در دو روز برگزار شده و برای انتخاب در سطح کشوری برگزار می‌شود. شرکت‌ کنندگان این مرحله قبول‌ شدگان مرحله‌ اول هستند و تعداد قبول‌ شدگان برای مرحله‌ بعد حدود دو برابر ظرفیت دوره‌ تابستانی (تقریبا ۸۰ نفر) می‌باشد. ضمنا برای تصحیح شدن آزمون تشریحی شما باید ابتدا در ازمون تستی حدنصاب لازم رو کسب کنید. این مرحله چالشی مهم و تاثیرگذار برای محک زدن دانش اموزان در زمینه های ترکیبیات و گراف و الگوریتم خواهد بود و رقابت در ان بسیار جدی می باشد.
آزمون مقدماتی برنامه‌نویسی (مرحله سوم): شامل یک آزمون تمرینی و دو آزمون انتخابی که در آن هر نفر یک کامپیوتر برای کمک گرفتن در حل مسائل خواهد داشت. در این مرحله پاسخ نهایی هر سوال یک عدد خواهد بود که روی برگه نوشته شده و تصحیح می‌شود. قبول‌شدگان این مرحله حدود ۴۰ نفر برای شرکت در دوره‌ تابستانی انتخاب می‌شوند.
دوره‌ تابستانی: در این دوره در کنار تدریس مطالبی از علوم کامپیوتر که در دروس دبیرستان مطرح نمی‌شوند و هم چنین کلاس‌های تمرین برنامه نویسی و حل مسئله، به طور منظم آزمون‌ های تشریحی و برنامه نویسی برگزار می‌شود. شرکت‌کنندگان در این دوره منتخبین آزمون مقدماتی برنامه‌ نویسی و همچنین دارندگان مدال نقره‌ المپیاد کامپیوتر از سال‌های گذشته هستند که مجاز به شرکت در المپیاد باشند. در انتهای این دوره بر اساس عملکرد شرکت‌ کنندگان در آزمون‌ها به 8 نفر مدال طلا و به ۱۶ نفر بعد مدال نقره و به بقیه برنز داده می‌شود. برحسب عملکرد دانش آموزان ممکن است به فرد یا افرادی هیچ مدالی داده نشده و تنها دیپلم افتخار دریافت کنند. دانش‌آموزانی که مدال طلا کسب کرده‌ اند برای انتخاب تیم ملی از شرکت در کنکور سراسری معاف بوده و در این رقابت‌ها باید شرکت کنند.
دوره‌ انتخاب تیم ملی: دانش آموزانی که مدال طلای کشوری المپیاد کامپیوتر را کسب می‌کنند تا زمانی که مجاز به شرکت در المپیاد کامپیوتر باشند برای عضویت در تیم ملی اعزامی به المپیاد بین‌ المللی کامپیوتر رقابت خواهند کرد. در این دوره تمرکز بر تمرین و کسب تسلط بیشتر می‌باشد و در کنار آن مطالب تکمیلی نیز آموزش داده می‌ شود. پس از این دوره تیم ملی متشکل از ۴ نفر انتخاب خواهند شد.

دوره‌ آمادگی تیم ملی: پس از انتخاب تیم ملی، در طول چند ماه باقی مانده به اعزام، دوره‌ ای دیگر برای آمادگی بیشتر مخصوص اعضای تیم برگزار می‌شود.

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

چگونه برای المپیاد آماده شویم؟

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

به صورت کلی شما باید به طور همزمان به مطالعه ترکیبیات و گراف و افزایش مهارت حل مسئله توی این دروس بپردازید. در عین حال باید در برنامه نویسی الگوریتمی هم مهارتتون را افزایش بدید به این شکل که به یادگیری الگوریتم های جدید و یادگیری زبان C++ و همچنین حل کردن مسائل مربوط به برنامه نویسی الگوریتمی در سایت های برنامه نویسی بپردازید.

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

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

شااززز منگولیا ۱۳۹۷/۱۰/۱۸ · ۱۹:۰۹

---

سوال شب ۱

خب خب خب :))

سلام بچه ها :8

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

خب سوال اول از این قراره :

یه زمین دایره ای شکل داریم که محیطش 1 متره. روی محیط زمین n تا پمپ بنزین هستن که با اعداد 1 تا n شماره گذاریشون کردیم. توی آی امین پمپ بنزین Xi لیتر بنزین وجود داره. Xi>=0 هستن و جمع Xi ها هم 1 میشه. حالا ما یه ماشین داریم که باکش اول کار خالیه و برای L متر جابجا شدن به L لیتر بنزین نیاز داره. ثابت کنید پمپ بنزینی وجود داره که بتونیم از اونجا در یک جهت خاص شروع به حرکت کنیم و کل محیط دایره رو دور بزنیم و به سر جای اولمون برگردیم.

نویسنده : امید آزادی

شااززز منگولیا ۱۳۹۷/۱۰/۱۸ · ۱۲:۵۴

---

Tutorial آزمون عمل اول

سلام!

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

اِسپویلِر آلِرت ( فارسیش خطر لوث شدن ) : به کسانی که سوالای آزمون رو ندیدن توصیه می شه که سوالا رو نسوزونن و به صورت مجازی ( تا جمعه ) تو کانتست شرکت کنن!

سوال A :

لم 1 : تعداد پنج ها در تجزیه این عدد از تعداد دو ها کمتر است. پس کافیست تعداد پنج ها را بیابیم.

حال کافیست به ازای هر i از 1 تا n  ، تعداد پنج های !i را بیابیم. این مقدار نیز برابرست با :

i / 5 + i / 25 + i / 125 + ...

در تمامی تقسیم ها کف گرفته می شود. پیچیدگی زمانی : O(nlogn) a

این سوال یه راه با پیچیدگی زمانی O(logn) a هم دارد که برای گرفتن نمره 100 لازم نبود.

Source Code

سوال B :

لم 1 : x ^ x = 0

لم 2 : a ^ (b ^ c) = (a ^ b) ^ c

با استفاده از این دو لم می توان دید که هر عددی که زوج بار آمده تاثیری بر ایکس اور ندارد و ایکس اور تمام اعداد آرایه برابر با عددی است که فرد بار آمده. پیچیدگی زمانی : O(n) a

Source Code

سوال C :

ابتدا فرض کنید گشتمان باید بسته باشد. در اینصورت برای دیدن m راس ، 2m-2 حرکت لازم است.

حال که مجبور نیستیم گشت بسته ای طی کنیم ، زمانی که m راس را می بینیم کارمان تمام می شود ؛ بدین معنا که تعداد حرکات 2m-2-d است که d فاصله ی بین راس شروع و پایانی است. حال ما میخواهیم d را بیشینه کنیم ، پس دو سر قطر را به عنوان شروع و پایان گشت انتخاب میکنیم.

برای پیدا کردن قطر هم کافیست دورترین راس نسبت به دورترین راس نسبت به یه راس رو پیدا کنیم! پیچیدگی زمانی : O(n) a

Source Code

سوال D :

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

آن مسیر را حذف کرده و این مسیر را اضافه میکنیم. در نتیجه جوابمان همچنان بهینه می  ماند. پس کافیست از پایین به بالا هر گاه که میتوانستیم مسیر k تایی انتخاب کنیم. پیچیدگی زمانی : O(n) a

Source Code

سوال E :

ابتدا فرض کنید جایگشت ورودی n n-1 n-2 ... 1 است. dp_i را جواب برای n = i میگداریم. حال جایگشت هایی را در نظر بگیرید که عدد j در اول آنهاست. در بین این جایگشت ها j ثابت است و سایر i-1 عدد دیگر جا به جا می شوند. پس عملا dp_i-1 حرکت لازم است. به راحتی نیز می توان دید تعداد حرکت لازم برای تیز کردن جایگشت j, i, i -1, i-2, ... 1 برابر با سقف i/2 است. پس : dp_i = dp_i-1 * i + (i - 1) * i/2.

حال برای حل حالت کلی : فیکس میکنیم که چه پیشوندی از جایگشت ورودی با جایگشت فعلی مان برابر است ( ابتدا جایگشتمان همانی است ). این مقدار را i می نامیم. حال برای اینکه i +1 امین عدد جایگشت ها هم برابر شود c * (dp_n-i-1 + (n-i)/2) a  حرکت لازم است (در تقسیم سقف گرفته می شود) که c برابر با تعداد اعداد کمتر از P_{i + 1} در میان n-i آعدد آخر جایگشت است. پیچیدگی زمانی : O(nlogn) a

Source Code

نویسنده : کسری مظاهری

طلاهای دوره ۲۸ ۱۳۹۷/۰۹/۱۹ · ۱۳:۱۲

---

کانتست اول شاززز (آپدیت شده)

سلام

الوعده وفا.

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

سیستم داوری مسابقه cms (جاج دوره تابستون) عه و مدتش هم ۵ ساعته (بازم مثل دوره تابستون)

این که چه جوری می تونین ثبت نام کنین رو متعاقبا اعلام می کنیم :)

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

شرکت کننده ها زیاد بشه => ما انگیزمون زیاد می شه => کانتست بیشتر میذاریم.

اگه حرفی حدیثی دارین یا با هر چیزی (مثل تایمش) مشکل دارین می تونین تو نظرا بگین (بررسیشون میکنیم)

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

بلاگ رو واسه اطلاعات بعدی چک کنید.

خدافظ

******

آپدیت 1:

یکم بررسی کردیم و تصمیم گرفتیم کانتست به صورت رسمی 9 صبح جمعه شروع شه اماااا میتونید تا شبِ دوشنبه هر 5 ساعتی که خواستید شرکت کنید توش به صورت غیر رسمی.

جایزه طبعن به نفر دوم مسابقه رسمی داده میشه!

از طریق ایییییین لینک میتونید ثبت نام کنید توی کانتست. (برای هر دو کانتست رسمی و غیررسمی).

پ.ن1: با تشکر از امیرحسین رجبی بابت سایت کیوبیت.

آپدیت ۲:

حتماااااااا تا ساعت ۸ صبح ثبت نام کنین تو کانتست چون بعدش دیگه زمان ثبت نام تموم خواهد شد!!

ساعت ۸ و نیم صبح یه ایمیل با رمز ورود بهتون فرستاده میشه که بتونین لاگین کنین و کانتست بدین!

آپدیت ۳:

ایمیلا فرستاده  شد!!

احتمالا هم تو پوشه اسپم ایمیلتون رفته. چک کنین ایمیلتون رو!

موفق باشین:))))

آپدیت ۴

رتبه بندی رو هم تو اینجا میتونین ببینین:))

آپدیت ۵:

میتونین تا دوشنبه از اینجا هم برای شرکت در کانتست غیر رسمی اقدام کنین

نویسنده: حمیدرضا کلباسی فیت مهدی جعفری

طلاهای دوره ۲۸ ۱۳۹۷/۰۹/۱۲ · ۲۲:۰۸

---

سلام اول

سلااااااااااااااااام

شاززز دوباره برگشت:)))

البته یه عذر خواهی باید بکنیم به خاطر دیر شدن این ماجرا. تقریبا هیچ سالی اینطوری نشده بود:(

اما خب مشکلات پیش میان دیگه.

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

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

خب دیگه خوش باشین

نویسنده: میکائیل

طلاهای دوره ۲۸ ۱۳۹۷/۰۹/۰۴ · ۱۳:۵۳

---

سلام آخر!

سلاام!‌‌ :)

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

 کلا میخوام بگم خیلی جالبه این روند دوری زندگی و المپیاد و این بحثا! :))

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

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

این موضوع یککم متاسفانه کمرنگ شده تو دوره های اخیر نسبت به قبل! :( (و البته قطعا ما هم مقصریم!)

ما که رفتنی شدیم! :'( کم و کسری های ما رو ببخشید! :))‌ امیدوارم بچه های جدیدی که میان با انرژی مضاعف اون شور و شوق قدیم شاززز و برگردونن و واقعا اون ارتباطه و اون خودمونی بودن جو شاززز رو برگردونن!  همین که بچه ها بتونن حرفاشونو راحت بزنن تو این محیط یه چیزیه که کم تر و کمتر شده و این بده! از نظر من علاوه بر اینکه مسابقات آمادگی مرحله ۱ و مرحله ۲ و مرحله ۳ و این جور چیزای گوگولی مگولی (!)‌برگزار میشه باید به این موضوع هم خیلی توجه بشه امسال! که ایشالا میشه!‌‌ :دی

ما رفتیم، اوناییکه اومدن ببینیم چه میکنن! درساتونو بخونید و خوش باشید و ازین حرفا! :دی

یه عذر خواهیم باید بکنیم بخاطر اینه این پست اینقد دیر شد! کلا هم مارو حلال کنید دیگه :))‌

موفق باشید و زندگی رو بترکونید!‌‌ 🤘

حمیدرضا کامکاری ۱۳۹۷/۰۹/۰۱ · ۲۳:۱۹

---

آزمون مرحله ۳ ای!!!

سلام.

این جمعه که داره میاد(یعنی 1 تیر) ساعت 9 صبح قراره یه ازمون مرحله 3 ای برگزار کنیم!

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

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

مثل مرحله 3 پاسخ سوال‎ها به صورت تک جوابی است.

پیشنهاد هم می کنم که ازمون رو جدی بدید یعنی تا حد امکان در شرایط آزمون بدید!

عیدتونم مبارک:)

بروزرسانی : در سایت کدشارک "زمان تا شروع ازمون" اشتباه نوشته شده ولی آزمون همان ساعت ۹ صبح جمعه شروع می‌شود!

بروزرسانی :حالا در سایت کدشارک "زمان شروع ازمون" اشتباه نوشته شده ولی آزمون همان ساعت ۹ صبح جمعه شروع می‌شود! کلا شروع شد دیگه برید بدید.

رتبه بندی

سید مهدی صادق شبیری ۱۳۹۷/۰۳/۲۶ · ۱۷:۴۶

---

مسابقه المپیادی با همکاری Quera

سلام

یه آزمونی رو ما آماده کردیم که قراره جمعه 11 خرداد تو سایت Quera برگزار بشه.

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

همین دیگه.

شااززز منگولیا ۱۳۹۷/۰۳/۱۰ · ۱۵:۱۳

---

۱ ۸ ۹ ۱۰ ۳۸