صفحه ۸

آمادگی برای مرحله یک

سلام به همه شازیای دوست داشتنیمون :)

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

نکاتی پیرامون آزمون فردا:

1. آزمون روز جمعه مورخ ۲۱ / ۱۰ / ۱۳۹۷ به صورت انلاین برگزار می شود و شامل ۲۵ سوال است که شما عزیزان ۳:۳۰ ساعت برای پاسخ دادن به آن ها زمان خواهید داشت. برای راحتی شما عزیزان ساعت شروع آزمون بر عهده خود شما خواهد بود و شما می توانید در هر بازه ۲۱۰ دقیقه ای از جمعه که خواستید توی این آزمون شرکت کنید.
2. برای شرکت در آزمون به لینک /http://judge.cf:1234 مراجعه کنید و پس از ثبت نام وارد آزمون شوید. دقت کنید که صورت سوالات از ساعت ۱۲ بامداد جمعه بر روی سایت قرار خواهد گرفت.
3. نام کاربری و رمز خود رو فراموش نکنید. چرا که پاسخ عملکرد شما در روز شنبه (فردای آزمون) در همان جایی که آزمون را شرکت کردید به شما ابلاغ می شود.
4.  برای تشویق نفرات برتر رتبه و نمره ۲۰ نفر اول آزمون روز شنبه در اختیار عموم قرار خواهد گرفت.
5. این آزمون صرفا برای مهارت سنجی شما عزیزان توسط خودتان آماده شده و جایزه ای هم برای آن در نظر گرفته نشده است. لذا تقلب در آن بی مورد است و به غیر از ضرر هیچ چیزی برای شما نخواهد داشت. 
6. صورت سوالات کاملا واضح نوشته شده است و گزینه ها و پاسخ های آزمون بارها بررسی شده است. لذا از پاسخ به سوالات و ابهامات شما عزیزان در حین آزمون اجتناب خواهد شد. اگر اعتراضی به سوالات دارید پس از آزمون خود, آن را به اطلاع ما برسانید. اعتراضات وارده بررسی و نتیجه آن ها شنبه صبح اعلام خواهد شد.

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

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

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

• بدون توجه به آزمون های گذشته آزمون خود را بدهید. بدانید اگر سوالات برای شما راحت است برای دیگران نیز راحت است و اگر برای شما سخت است برای دیگران نیز سخت است. پس دلیلی برای استرس و یا غرور وجود ندارد. مهم این است که شما از فکر کردن به مسائل متفرقه اجتناب کنید و با تمام تمرکز به ادامه آزمون خود بپردازید.
• وقت خود را مدیریت کنید. اول از همه زمان خود را تقسیم بر تعداد سوالات کنید تا ببینید برای هر سوال به طور میانگین چه قدر زمان دارید. سپس طوری ازمون را پیش ببرید که مطمئن باشید برای هر سوال حل نشده خود می توانید حداقل به اندازه نصف زمان آن سوال بر روی آن وقت بگذارید. متاسفانه خیلی از بچه ها گاهی اوقات بر روی تعدادی مسئله زمان زیادی می گذارند و این باعث می شود که نتوانند بر روی همه مسائل به اندازه لازم وقت بگذارند و این گونه ممکن است تعداد زیادی سوال راحت را از دست بدهند. پس مراقب زمان خود باشید.
• بی دقتی هم یکی دیگر از عواملی است که که گریبان گیر بچه ها در حین آزمون می شود و حسرت های زیادی برای آن ها در پی خواهد داشت. رمز بی دقتی نکردن در حفظ آرامش و منظم فکر کردن است. اگر برای حل هر سوال مسیر درستی را در نظر بگیریم و با آرامش به ترتیب مسیر را طی کنیم هیچ بی دقتی در این بین نخواهد شد. اغلب بی دقتی ها در اثر استرس و یا گیج شدن بچه ها در مسائل است.
• وقت خود را بر روی راه حل های اشتباه تلف نکنیم. خیلی اوقات المپیادی ها نه تنها در آزمون تستی بلکه در آزمون تشریحی نیز راه حل اشتباهی را برای حل سوال در نظر گرفته و زمان زیادی را بر روی آن تلف می کنند و حتی در آزمون های تستی نمره منفی نیز دریافت می کنند. حال چه کنیم که از این اشتباهات نداشته باشیم؟! باید یاد بگیریم که چراهای درستی برای خود طرح کنیم و پاسخ درستی هم به آن ها بدهیم. خیلی اوقات ما یک سری حالات مسئله را در نظر نگرفته و یا از اثبات یک گزاره به سادگی عبور می کنیم و تو ذهن خود می گوییم اینکه بدیهی است در صورتی که واقعا ممکن است آن گزاره اشتباه باشد. باید به ذهن خود آموزش دهیم که از زوایای مختلف به مسئله نگاه کند و خیلی راحت از کنار گزاره های کوچک که در کنار هم قرار گرفتن آن ها مسئله را حل می کند نگذرد و برای تک تک آن ها اثباتی ارائه دهد. این کار با حل مسئله میسر می شود البته به شرط اینکه در حین حل مسائل تمامی این نکات را در نظر بگیریم. هر چه مسئله ای که حل می کنم سخت تر باشد قطعا میزان پیشرفت ما نیز بیشتر خواهد بود.
• در آزمون تستی سرعت عمل بسیار تاثیرگذار است و حفظ آرامش که در نکات قبلی به آن اشاره کردیم دلیلی بر فدا کردن سرعت عمل نخواهد بود. باید یاد بگیریم که وقت خود را بیهوده تلف نکنیم و در عین آرامش مسیر حل مسئله را سریع تر بپیماییم. این کار با حل مسئله زیاد میسر خواهد شد. پس توصیه می شود مرحله یک دوره های قبل را که بهترین نمونه برای مرحله یک واقعی هستند به صورت آزمون از خود بگیرید و پس از آزمون به حل سوالات حل نشده آن بپردازید.
• اگر برای حل سوالی هیچ ایده ای نداشتید سعی کنید با مثال های کوچک و یا بررسی تعدادی از حالات مسئله برای خود شهود ایجاد کنید تا بتوانید بهتر به مسئله فکر کنید.

اگر دقت کرده باشید مطالب گفته شده در جهت بهبود مرحله یک اصلی شما می باشد. لذا از همین فردا اجرای این نکات را آغاز کنید تا عملکردتان روز به روز بهبود یابد.

امیدوارم هر جا که هستید موفق باشید. خداحافظ :)

امیرمحمد ایمانی

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

---

سوال شب ۳

سلام ! دونقطه دی

مثل دیروز اول راه شب گذشته رو می گیم ( اگر به سوال به مقدار کافی فکر نکردین، نخونین که براتون لوث نشه !=) ) :

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

حالا در کل 2^M زیرمجموعه داریم. هر کدوم از زیرمجموعه ها مثل S رو متناظر با یک n+1 تایی مرتب (a₀, a₁ , ... , a_n) می کنیم, که a_i برابر sigma (S_j) ⁱ هست.

a_i حداقل 0 و حداکثر M * M ⁱ = M ^{i + 1} هست, پس حداکثر M ^{i + 1} + 1 <= M ^{n + 2} حالت دارد ( M > 1 ). در نتیجه تعداد n + 1 تایی های معتبر از M ^{n*n + 3*n + 2} بیستر نیست.

پس کافیه 2^M > M ^{n*n + 3*n + 2} تا طبق اصل لانه کبوتری 2 تا زیرمجموعه درست پیدا بشن. تابع 2^M نمایی هست ولی تابع M ^{n*n + 3*n + 2} چندجمله ای, پس پیدا می شه M که نا مساوی گفته شده برقرار بشه !

 

خب , بالاخره می رسیم به سوال امشب دونقطه دی :

 

خانه های یک جدول مربعی n _x n رو با اعداد صحیح پر کرده ایم , به طوری که اختلاف عدد هر دو خانه ی مجاور ضلعی , از 1 بیشتر نشود.

الف ) اثبات کنین عددی وحود داره که حداقل کف n/2 بار در جدول ظاهر شده.

ب ) اثبات کنین عددی وحود داره که حداقل n بار در جدول ظاهر شده.

 

نویسنده: مهرشاد =) (راه سوال دیشب هم از میکائیل )

 

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

---

آزمون شبیه ساز مرحله یک

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

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

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

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

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

امیدوارم آزمون مفیدی براتون باشه. 

یادتون نره که ما بعد از جمعه منتظر انتقادات و پیشنهادات محترمانه شما خواهیم بود :)

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

---

شب ۲

سلاااااااام

 

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

 

اول از همه راه سوال دیروزو میگم، کسایی که فکر نکردن بهش نخونن که براشون لوث نشه!

 

میخوایم ثابت کنیم یه پمپ بنزینی هست که بشه با شروع ازش، ساعتگرد کل دایره رو طی کرد. میخوایم با استقرا روی n، تعداد پمپ بنزین ها، مسئله رو ثابت کنیم. به ازای n=1، حکم بدیهیه خدایی. به ازای n>1 ها، اول نشون میدیم پمپ بنزینی مثل X وجود داره که با شروع از اون و با باک خالی، بتونیم خودمونو به پمپ بنزین بعدی X در جهت ساعتگرد برسونیم. فرض خلف میکنیم همچین پمپ بنزینی نباشه، اونوقت مقدار بنزین هر پمپ بنزین اکیدن از مقدار فاصلش تا پمپ بنزین بعدیش در جهت ساعتگرد کمتره، اونشکلی جمع بنزین ها از محیط دایره کمتر میشه که تناقضه. پس پمپ بنزین X طبق خواسته ما وجود داره. حالا پمپ بنزین بعدی X در جهت ساعتگرد رو Y بگیرید. میگیم بیا بنزین Y رو بگیر و تو X بریز، بعدش Y رو حذف کن. شرایط مسئله هنوز برقراره و تعداد پمپ بنزینا یکی کم شده؛ پس طبق فرض استقرا، یه پمپ بنزینی هست که با شروع از اون در جهت ساعتگرد بشه دایره رو طی کرد. اگه اسم اون پمپ بنزین Z باشه، ما اینجا هم با شروع از Z کل دایره رو طی میکنیم. چرا؟ چون تا وقتی به X نرسیده که همه چی مثل شرایط n-1 پمپ بنزینمونه. وقتی هم به X رسید، چون باکش بیشتر مساوی 0 بنزین داره، با بنزینی که از X میگیره میتونه به Y برسه (طبق شرایط X) و از اونجا هم به پمپ بنزین بعدی میره. بعدش دوباره طبق شرایط n-1 پیش میره. اینشکلی گام استقرا ثابت میشه و حکم ثابت میشه.

 

راه های دیگه ای هم مثل اکسترمال داره این سوال اگه خواستید فک کنید بهش %__%

 

 

 

و حالا سوال جدید:))

 

ثابت کنین عدد طبیعی M وجود دارد به طوری که از مجموعه ی اعداد طبیعی 1 تا M

بتوان دو زیر مجموعه مجزا مثل A و B انتخاب کرد به طوری که:

Sigma ai^k=sigma bi^k

برقرار باشه به ازای هر 0=<n>=k

(یعنی تعداد اعضاشون برابر باشه, مجموع اعضاشون برابر باشه, مجموع توان دو اعضاشون برابر باشه و ... مجموع توان n اعضاشون هم برابر باشن)

 

نویسنده: میکائیل (راه حل سوال دیروز از امید)

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

---

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

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

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

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

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

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

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

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

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

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

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

مرحله‌ دوم: شامل یک آزمون تستی و یک آزمون تشریحی که در دو روز برگزار شده و برای انتخاب در سطح کشوری برگزار می‌شود. شرکت‌ کنندگان این مرحله قبول‌ شدگان مرحله‌ اول هستند و تعداد قبول‌ شدگان برای مرحله‌ بعد حدود دو برابر ظرفیت دوره‌ تابستانی (تقریبا ۸۰ نفر) می‌باشد. ضمنا برای تصحیح شدن آزمون تشریحی شما باید ابتدا در ازمون تستی حدنصاب لازم رو کسب کنید. این مرحله چالشی مهم و تاثیرگذار برای محک زدن دانش اموزان در زمینه های ترکیبیات و گراف و الگوریتم خواهد بود و رقابت در ان بسیار جدی می باشد.
آزمون مقدماتی برنامه‌نویسی (مرحله سوم): شامل یک آزمون تمرینی و دو آزمون انتخابی که در آن هر نفر یک کامپیوتر برای کمک گرفتن در حل مسائل خواهد داشت. در این مرحله پاسخ نهایی هر سوال یک عدد خواهد بود که روی برگه نوشته شده و تصحیح می‌شود. قبول‌شدگان این مرحله حدود ۴۰ نفر برای شرکت در دوره‌ تابستانی انتخاب می‌شوند.
دوره‌ تابستانی: در این دوره در کنار تدریس مطالبی از علوم کامپیوتر که در دروس دبیرستان مطرح نمی‌شوند و هم چنین کلاس‌های تمرین برنامه نویسی و حل مسئله، به طور منظم آزمون‌ های تشریحی و برنامه نویسی برگزار می‌شود. شرکت‌کنندگان در این دوره منتخبین آزمون مقدماتی برنامه‌ نویسی و همچنین دارندگان مدال نقره‌ المپیاد کامپیوتر از سال‌های گذشته هستند که مجاز به شرکت در المپیاد باشند. در انتهای این دوره بر اساس عملکرد شرکت‌ کنندگان در آزمون‌ها به 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: با تشکر از امیرحسین رجبی بابت سایت کیوبیت.

آپدیت ۲:

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

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

آپدیت ۳:

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

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

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

آپدیت ۴

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

آپدیت ۵:

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

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

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

---

۱ ۷ ۸ ۹ ۳۸