شاززز

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

سوال دوم‌:
یک گراف شونزده راسی بسازید. اگه آقای آ‌ آقای ب رو نگاه میکرد از آ‌ به ب یک یال بذارین. حالا درجه ورودی و خروجی هر کس تو این گراف ۷ ه (چرا؟). حالا یازده نفر رو در نظر بگیرید یکی از این یازده نفر هست که به هر ده نفر دیگه یال داره (ورودی یا خروجی). حالا اون ده نفر یک دور دارن . با استفاده از این دور و این که اون یک نفر که کنار گذاشتین به همه یال داره ثابت کنید دور به اندازه یازده هم داریم.
سوال سوم:
این سوال که سوال خیلی خیلی سختی بود ما پیشنهاد نمیکنیم که راه حلشو بخونید. ولی راه حلشو کامل میگیم.
اول این سوال رو برای ده ربات حل میکنیم. بعد از راه حل این برای ۳ کمک میگیریم. (اگه میخواین بیشتر رو این سوال فکر کنید دیگه ازینجاش نخونین)
از استقرا قوی استفاده میکنیم. حکم استقرا میگه اگر ما log n مامور داشته باشیم میتونیم درخت رو بگردیم.
همون طور که میدونید فرض استقرا همون حکمشه برای حالت های کوچیکتر پس ما لازم نیست فرض استقرا رو بنویسیم :)
حال هر ده مامور در یک راس جمع میشوند(اسم این راس را مقر میگذاریم). اگر این راس را از گراف حذف کنیم‌ ، تعدادی درخت به وجود می‌آید که از این تعداد حد اکثر یکی از آن ها تعداد راس هایش بیش از نصف است. طبق فرض استقرا باقی درخت ها با ۹ مامور گشته میشوند. پس ما باقی درخت ها را با ۹ مامور میگردیم. یک مامور هم در مقر نگهبانی میدهد که سوسک از درختی به درخت دیگری نرود. حال اگر ۹ مامور سوسک را پیدا نکنند به مقر برمیگردند. و قسمت بعدی کار آغاز میشود (گشتن در درختی که بیش از نصف راس ها را دارد). هر ده مامور روی یالی که به این درخت میرود حرکت میکنند و داخل راسی جدید میشوند. این راس را مقر جدید میگذارند و یکی در این راس نگهبانی میدهد. قطعن سوسک به بخش هایی از گراف که قبلن گشته شده نمیره.
پس میتونیم فرض کنیم اون درختا وجود ندارن و داریم تو یه درخت کوچیککتر با ده مامور میگردیم. دوباره همین کارو با راس مقر میکنیم تا کل درخت گشته بشه. :)
خب اگه این قسمت رو نفهمیدین از این جا به بعد رو هم نمیفهمین :) پس سعی کنین این قسمت رو بفهمین
اگر توجه کنین مقر های ما تشکیل یک مسیر رو میدن توی درخت که اگه ما اون مسیر رو حذف کنیم تمام درخت های باقی مونده کمتر از نصف تعداد راس های ما رو دارن.
حالا ما اگه بتونیم مسیری پیدا کنیم که با حذف کردنش تمام درخت های باقی مونده کمتر از ۱/۳ راس ها رو داشته باشن. میتونیم این کارو با ۶ رباتم بکنیم.
(یه مامور میذاریم میشه ۳۳۳ راسی. باز تو مقر جدید یه مامور میذاریم نگهبانی بده چند تا ۱۱۱ راسی میمونه. یا مامور جدید میذاریم چند تا ۳۶ راسی میمونه. یکی دیگه میذاریم چند تا ۱۱ راسی میمونه. یکی دیگه بذاریم چند تا سه راسی میمونه. که درخت سه راسی یک مسیره با یک مامورم میشه گشتش)
حالا میخوایم ثابت کنیم چنین مسیری وجود داره. دوباره استقرا میزنیم. اولین نکته اینه که راس درجه ۲ اگه وجود داشته باشه میتونیم حذفش کنیم و به جاش دو تا همسایه شو به هم وصل کنیم و استقرا بزنیم. پس راس درجه دو نداریم.
 اگه راسی وجود نداشته باشه که با حذفش بیشتر از یک درخت با کمتر از یک سوم راس ها به وجود بیاد مانند مثله قبل عمل میکنیم. یعنی ۶ نفر رو میذاریم تو یک راس دلخواه. سپس با ۵ نفر درخت هایی که کمتر از یک سوم دارن رو حل میکنیم بعد همگی میریم به درختی که بیشتر از یک سوم داره.
حالا اگه راسی وجود داشت که با حذفش دو تا درخت با بیش از یک سوم به وجود میومد (قطعن سه تا به وجود نمیاد :) ). خب فقط این راس و دو درختی که بیش از یک سوم راس دارد در نظر میگیریم و باقی درخت ها را حذف میکنیم (حد اقل یک درخت حذف میشه چون درجه همه راسا بیشتر از دو بود). حالا طبق فرض استقرا تو این درخت کوچکتر مسیری وجود داره که با حذفش همه درختای باقی مونده کمتر از یک سوم راس هارو دارن. همین مسیر تو گراف اصلی هم این خاصیت رو داره :)

امسال مثل پیارسال شاززز قصد داره یک آزمون شبه مرحله 1  برگزار کنه. این آزمون قراره در تاریخ ۳ بهمن (اولین پنج شنبه بهمن) و به دو صورت حضوری (داخل مدرسه خودتون یا سمپاد شهرتون) و غیر حضوری (آنلاین)برگزار بشه. ما نهایت تلاشمون رو می کنیم که به مدارس مختلف خبر رسانی کنیم و سطح آزمون رو به سطح امتحان مرحله یک نزدیک تر کنیم.طراحای سوالات هم طلاهای امسال هستند.

روش شرکت حضوری در این آزمون :

به دلیل بسته بودن دست ما در ارتباط با مدارس (مثلپیارسال) خبر رسانی از طریق خود شماست. هر کسی که این پست رو میبینه به مدرسه شون بگه که به این ایمیل اعلام آمادگی کنن ( sh44zzz@gmail.com ).

روش شرکت در آزمون آنلاین :

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

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

ببخشید یک کم دیر شد سرمون شلوغ بود و وقت نداشتیم.

خب بریم سر آزمون:

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

سوال 2: این سوال با استفاده از الگوریتم داینمایک حل می شه. و داینامیکتون رو باید به این شکل تعریف کنید. d_i,j: کمترین هزینه برای رسیدن به مربع i ام به طوری که با پرش به طول j به آن برسیم.

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

سوال 3: می دانیم گوشه n ام این جدول برابر است با n/2+1) * (n/2 + mod 2) +1) و از این طریق می توان A های خواسته شده را به دست آورد.

حال یک گراف وزن دار می سازیم که راس های آن 1 و n و همه ی A و B ها است و به ازای هر AوB یک یال به وزن یک می گذاریم. حال همه ی راس ها را به صورت مرتب شده در یک آرایه نگه می داریم و راس i ام این آرایه را s_iمی گیریم و بین s_iو s_i+1یال به وزن s_{i+1 -} s_i+1 می گذاریم. حال با استفاده از الگوریتمdijkstra طول کوتاهترین مسیر بین راس 1 و n را به دست می آوریم.

صورت سوالات ، تست کیس ها و کد سوالات رو می تونید از اینجادانلودکنید.

این هفته به دلیل برگزاری مسابقه izocup آزمون شاززز نخواهیم داشت.

در کل تعداد شرکت کنندگان در آزمون های عملی خیلی کمه و اگه همینجوری پیش بره آزمون های کمتری برگزار خواهیم کرد (مثلا 1 یا 2 ماه در میان) پس به دوستاتون بگید که شرکت کنن.

جاج این آرمون هم تا این جمعه باز است.

موفق باشید :)

-----------------------------

پ.ن: لینک ها درویکی شاازززیاآپدیت شد و مسائل داینامیک و سوالات المپیاد روسیه به آن اضافه شد.

این هفته قراره آزمون عملی دوم رو  مثل آزمون هفته گذشته برگزار کنیم. زمان آزمون 2 ساعته،در روز جمعه از ساعت 7 تا 9 ولی ممکنه کمی زمان آزمون تغییر کنه پس حتما شاززز رو چند ساعت قبل از شروع آزمون چک کنید.

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

خوش باشید

----------------------------------------

آزمون ساعت 7 شروع میشه.تو این آزمون scoreboard هم داریم.

سوالات رو می تونید ازاینجادریافت کنید.

برای وارد شدن بهاینجامراجعه کنید.

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

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

تو این پست می خوایم سوالات آزمون عملی رو بررسی کنیم:

سوال1: تو این سوال فقط باید به محدودیت های ورودی دقت می کردید.خیلی ها کد bignum زده بودند که اصلاً لازم نبود و تنها وقت خودشون رو هدر دادند.تنها کافی بود متغیر هاتون رو از جنس unsigned long long بگیرید.

سوال2:هدف از این سوال آشنایی شما با قضیه کوچک فرمابود.اینهم یه سوال مشابه برای تمرین بیشتر

سوال3:این سوال هم بیشتر جنبه تئوری داشت و کد خیلی کوتاهی داشت.

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

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

آدرس ایمیل: sh44zzz@gmail.com

موفق باشید

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

نکته اول : گروه شاززز در نظر داره یک آزمون شبیه مرحله اول و مرحله دوم برگزار کنه (داریم تمام تلاشمونو میکنیم که این آزمون به صورت حضوری در مدرسه ها برگزار بشه خبرشو تا اواسط هفته دیگه میدیم)

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

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

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

سلام بچه ها

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

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

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

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

سبک کانتست هم طبقacm/icpc rulesخواهد بود.

برای کسب اطلاعات بیشتر میتونید به سایت مسابقهIZOcup.irمراجعه کنید. 

این هملینکپوستر مسابقات

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

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

شروع آزمون ساعت 4:30 و پایان ساعت 6:30

------------------------------------------------------------------------------------------------

آزمون امروز 3 سوال داره و سوال دو جواب آخر هستش،یعنی لازم نیست کدتون رو ثبت کنید.امتیاز همه سوالات با هم برابر هستش.

در ضمن چند اکانت دیگه هم حذف شد:"ostad","pispis","Alirezan"

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

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

سوالات رو می تونید ازاینجا دریافت کنید.

اولین امتحان غیر output only (: شاززز به اتمام رسید همگی خسته نباشید.تا آخر امشب نتایج میاد.

نتایج رو می تونید ازاینجادریافت کنید. سرور تا فردا بازه و می تونید کد هاتون رو سابمیت کنید و برای هر سوال 20 بار حق ارسال دارید و جواب کل تست کیس ها به جای 30% به شما داده می شه.

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

پیشنهاداتون برای آزمون های بعد در نظرات بنویسید.

قراره که اولین امتحان عملی شاززز جمعه این هفته(8 آذر)برگزار بشه.زمان آزمون دو ساعت و ازساعت 6(بعد از ظهر:) ) تا 8 هستش.این آزمون آزمایشی هستش و برای اینه که شما با محیط آزمون آشنا بشید.آزمون قراره سه سوال در طرح ها و رنگ های مختلف داشته باشه :). تا آخر هفته هم وقت برایثبت نامدارید.اطلاعات بیشتر در مورد سوالات و نحوه امتیازدهی رو آخر هفته بهتون می گیم.

شاد باشید

------------

پ.ن : اون کنار یه لینک اضافه شده (سوالات خوب). یه نگاهی بهش بندازید :) (سوالات شوروی توشه)

پ.ن 2: کسانی که در زمان ثبت نام ارور "آدرس ایمیل شما معتبر نمی باشد" رو دریافت می کردند دوباره تلاش کنند یه مشکلی برا سرور پیش اومده بود که درست شد.

پ.ن 3 : این لینکجواب های هفته پیشه که محمدمهدی جهان آرا و آرش پور دامغانی تهیه کردن.

پ.ن 4:همونطور که گفتیم کسانی که نام و نام خانوادگیشون رو درست وارد نکرده باشند حذف می کنیم.اکانت هایی که حذف شدند:"shadi","kolah","amirrezam".ثبت نام هم تا پنجشنبه شب باز هستش.هر کی مونده سریعتر ثبت نام کنه.