ایده های کلی مرحله 2 ها

[hoco.hc]

پاسخ : ایده های کلی مرحله 2 ها

دوره 19:
1- 5 تا ، پیدا کردنش راحته ( و یه کم خر کاری )، اثبات این که بهینه هست رو هم می تونید با باینر سرچ برید. ( هر خونه که انتخاب کنید به دو دسته انتخاب می شند که یکیشون حتما از 9 بیشتره )
2-

ببرید تو مبنای دو. هر دسته 1 و 0 باید یه پرش بکنه.
3- اگه از کوچیک به بزرگ برسه ، از بزرگ هم به کوچیک می رسه.
4- ریشه دار کنید درخت رو.
5- از یک طرف صفحه را شطرنجی کنید و از طرف دیگه توی هر مربع 2*2 حداکثر 10 تا حالت هست.
6- در مرحله اوّل باید 10 تا سطل باشند که توشون حداقل 10 و 9 و .... و 1 توپ باشه. ولی مجموع توپ ها بیشتر از 50 میشه که تناقضه.
7- استقرا
8- در هر مرحله 2 تا کارت را انتخاب کنید و حداکثر 2d-1 تا از اختلاف هاشون رو بپرسید. ثابت می شه در کل حداکثر nd-1 تا رو پرسیدیم.

 

[emadceh]

پاسخ : ایده های کلی مرحله 2 ها

hoco عزیز به خاطر اون دوتا سوال دوره 17 خیلی ازت ممنونم و خیلی دوست دارم بدونم چی جوری سوال یک دوره بیست رو با ناوردایی حل کردی ؟من با برهان خلف حل کردم .البته اولش به نظرم اومد که ناوردایی باشه ولی اونجوری حل نشد.

 

[hoco.hc]

پاسخ : ایده های کلی مرحله 2 ها

hoco عزیز به خاطر اون دوتا سوال دوره 17 خیلی ازت ممنونم و خیلی دوست دارم بدونم چی جوری سوال یک دوره بیست رو با ناوردایی حل کردی ؟من با برهان خلف حل کردم .البته اولش به نظرم اومد که ناوردایی باشه ولی اونجوری حل نشد.

خواهش می کنم، خب یه سوال راه حل های متفاوتی داره، حتی ممکنه با استقرا هم حل بشه !!!!.
ولی راه ناوردایی من: اوّل همه رو توی یه شرکت می زاریم، اگه راضی بودند که هیچ، اگه راضی نبودند یکیشون رو میبریم توی یه شرکت دیگه، و هیچ وقت هم توی دور نمیفته ( چرا؟ ) پس بعد از حداکثر n حرکت ( بردن یه کارمند از شرکت اوّلی به دومی ) مطمئنا کارمندا راضی می شند.

 

[mimilad]

پاسخ : ایده های کلی مرحله 2 ها

سوال 5 دوره 18 :
ثابت کنید برای k مرکز حداقل kd/2 +1 شهر نیاز است (که d زوجه و برای فرد هم به طور مشابه ) برای این کار مسیر بین مرکز 1 و 2 رو در نظر بگیرید حالا مسیر بین مرکز 1و3 رو در نظر بگیرید و در مسیر بین 1 و3 شهر های که بعد از اولین اشتراک این مسیر با مسیر 1و 2 قرار دارند رو حذف کنید حالا بین شهر های که مانده اند حداقل 3d/2 +1 است و میدانیم یکی از مسیر های از 1 تا شهر اشتراکی یا از 2 تا شهر اشتراکی برای با حداقل d/2 است (مثلا 1مرکز ) حالا مسیر بین 1مرکز و شهر اشتراکی رو یک مجموعه و مسیر بین شهر 2 و3 را یک مجموعه در نظر میگریم (که حداقل شامل d+1 شهره) حالا مسیر بین مرکز 1 و مراکز 2 سپس 3 و........... رو به ترتیب در نظر گرفته و کار مشابهی رو انجام میدهیم و هرگاه مجموعه ای شامل بیش از 3 مرکز به وجود امد اونو به دو مجموعه تقسیم میکنیم .

سوال 7 رو سر ازمون به چیزای خیلی خاصی نرسیدم اگه کسی حل کرده بزاره

 

[b_delshad]

پاسخ : ایده های کلی مرحله 2 ها

دوره 20:
1- ناوردایی
2- الف: در هر مرحله نصف اعداد سر جایشان قرار می گیرند، ب : استقرا
3: الف : استقرا ( زیبا بود استقراش ) ، ب: یک مسیر به طول 5 به طوری که هر کدوم از جاده هاش دو عدد 1 و 0 رو داشته باشند.
4: استقرا !!!!!
5: الف: اوّل دو تا دو تا ، بعدش 4 تا چهار تا و .... . ب : نمی دونم . // ( این منو یاد disjoint set میندازه. )

2 ب رو باید یه ارایه ساختار داد بعد برای اثباتش استقرا زد. ارایه ساختارشاگه درست درست یادم مونده باشه)
1 2 4 3 8 7 6 5 16 15 14 ... 9 32 ... 17 ...
5 ب هم مسئله رو می شه به این مسئله تناظر داد:
n تا دسته داریم تو هر کدوم 1 مهره هست. در هر نوبت می تونیم دو دسته را ادغام کنیم (یعنی مهره هاشو بریزیم تو یه دسته) و هزینه ی انجام این کار به تعداد مهره های دسته کمتره(دسته ای که تعداد مهره هاش کمتر بود) می شه. هدف اینه که به 1 دسته با n مهره برسیم. باید ثابت کنیم در هر صورت پولی که می پردازیم از

بیشتر نمیشه.
برای اثبات این هم می گیم هر مهره حداکثر k بار تو هزینه حساب میشه.(چون بعد هر یه باری که حساب میشه چون تو دسته کوچیکتر مساویه به یه دسته حداقل دو برابر می رسه پس حد اکثر k بار حساب میشه.) از اون جایی که 2 به توان k تا مهره داریم هزینه از

بیشتر نمیشه.

 

[b_delshad]

پاسخ : ایده های کلی مرحله 2 ها

خیلی خوشحالم که این تاپیک کلا نخوابید.
مرحله 17:
روز اوّل همه سوالات بدیهی ( ولی می نویسم )
1: همه n ها برنده می شه. هر خطی که نفر اوّل بکشه یه ناحیه به وجود میاد، نفر دوم اون ناحیه رو رنگ می کنه.
2: سه مسیر مجزا یال از a به b
3: استقرا
4: یه ناوردا پیدا کنید. a<= 1 می شه گراف کامل ، a>1 می شه ستاره.
روز دوم:
5: اون پی رو در نظر بگیرید که کمترین فاصله رو از A داره و داخل A هست.
6:m+n+k . یه مثالی بزنید که اینقدر بشه. با استقرا ثابت کنید کمتر نمی شه.
7:فکر می کنم بشه (lg n ) - 1 . هر مرحله یکی بی حساب بشه. یه مثالی هم بزنید که کمتر نمی شه. ( کسی که بیشتر از همه پول داره در هر مرحله نصف می شه )
8: سوالو درک نکردم. یکی بیشتر توضیح بده.

سوال 6 میشه m+n+k-2 مثالشم: 1 تا m و 1 تا n و 1 تا k که اعداد 3 تا m+n+k تولید میشه. من اثبات با استقراشو نمیدونم ولی بدون استقرا هم میشه الگوریتمی داد که m+n+k-2 عدد مختلف تولید کرد.
7 هم میشه 2n - 1 همون مرحله اول شما n مرحله است.
8 هم به ازای n شهر و k شکارچی میشه l (n - k)*k
اثباتشم با استقراست.
1 هم اگه دقت کنین سوری گیم هستش یعنی بازی به هر طریقی انجام شه قابیل می بره و ربطی به حرکتشون نداره. برای اثبات هم به زوجیت ناحیه های رنگ نشده در پایان هر حرکت توجه کنید.
سوال 3 هم یه مشکلی داشت صورتش. بعد از هر دستوری که توش بررسی کن وجود داره می تونید از این دستور ها استفاده کنیدمعلومه که بدون شرط نمیشه این کد رو زد.)
اگر نتیجه ی بررسی .... شد (آنگاه یکی یا چند تا از دستورهای موجود در صورت سوال)
در ضمن من ربطشو به استقرا نفهمیدم؟ جواب یه کده با دستور های فارسی به این صورت:
1. وضعیت کلید مقابل را بررسی کن.
2. اگر رو به بالا بود
1.2آنگاه آن را رو به پایین کن
2.2 وجود برق را در آن بررسی کن.
3.2 اگر برق نداشت دوباره آن را رو به بالا کن.
3.به کلید بعدی برو.
(این کد را n بار زیر هم می نوسیم در آخر
3n + 1. توقف کن.
حال هر کلیدی که رو به پایین است دارای برق است.
(در ضمن این تغییرات در صورت سوال و جواب به تایید دبیرم رسیده . شک نکنید.)
--------------------------------------------------------------------------------------------------------
در آخر ممنون از جناب hoco با این پست می تونم ایرادات هم و مشکلاتمون رو حل کنیم.

 

[hbsciw]

پاسخ : ایده های کلی مرحله 2 ها

دوره 19:
1- 5 تا ، پیدا کردنش راحته ( و یه کم خر کاری )، اثبات این که بهینه هست رو هم می تونید با باینر سرچ برید. ( هر خونه که انتخاب کنید به دو دسته انتخاب می شند که یکیشون حتما از 9 بیشتره )
2-

ببرید تو مبنای دو. هر دسته 1 و 0 باید یه پرش بکنه.
3- اگه از کوچیک به بزرگ برسه ، از بزرگ هم به کوچیک می رسه.
4- ریشه دار کنید درخت رو.
5- از یک طرف صفحه را شطرنجی کنید و از طرف دیگه توی هر مربع 2*2 حداکثر 10 تا حالت هست.
6- در مرحله اوّل باید 10 تا سطل باشند که توشون حداقل 10 و 9 و .... و 1 توپ باشه. ولی مجموع توپ ها بیشتر از 50 میشه که تناقضه.
7- استقرا
8- در هر مرحله 2 تا کارت را انتخاب کنید و حداکثر 2d-1 تا از اختلاف هاشون رو بپرسید. ثابت می شه در کل حداکثر nd-1 تا رو پرسیدیم.

سوال 4 رو بیشتر توضیح بدید.

 

[mohsen2010]

پاسخ : ایده های کلی مرحله 2 ها

فردا ایشالله اونایی که حل کردم از دوره 18 رو میزارم + حل کامل سوال 5 دوره 17. سوال 4 هم اینطوری هست که اگر q حداقل هزینه باشه، و b تعداد جاده ها باشه ، باید

. این عبارت هم تبدیل میشه به

که از اون جا که

، مقدار b باید حداقل بشه. و چون باید گراف همبند باشه، حداقل مقدار b ، n-1 هست، یعنی باید درخت باشه. و در درخت، فاصله هر دو راس غیر مجاور، حداقل 2 هست، و در ستاره این فاصله دقیقا 2 می باشد. ==> جواب ستاره می شه.

البته برای aههای کوچکتر از ۱ گراف کامل میشه.

 

[mafia3]

پاسخ : ایده های کلی مرحله 2 ها

ایده ها دوره 21م هم بزارین .

 

[hoco.hc]

پاسخ : ایده های کلی مرحله 2 ها

ایده ها دوره 21م هم بزارین .

سوال یک: استقرا
سوال دو: الف: اگر ارتفاع کمتر از 14 بود درست میشه، وگر نه بلند ترین مسیر رو حذف کنید و ... . اگر بلند ترین مسیر رو هم در هر مرحله حذف کنیم می شه 15+14+13+...+2 که از 100 بیشتره. ب: استقرا ( توجه کنید : k^2 = 1 + 3+5+..+ 2n+1 )
سوال سه: الف: مبنای دو ببرید. ب: نمی دونم.
سوال چهار: اوّل روابط نسبی شون رو پیدا کنید، بعد همه رو سر جاشون قرار بدید. ( اوّلی را با آخری چک کنید، بعدش ... )
سوال پنج: الف: گراف جایگشت، ب: نمی دونم.

 

[hoco.hc]

پاسخ : ایده های کلی مرحله 2 ها

ببخشید، اگه یه چند وقت نبودم، این جواب هایی هست که تقریبا مطمئنم. اگه اشتباهی بود ببخشید دیگه. تلاشمو کردم.D:

البته برای aههای کوچکتر از ۱ گراف کامل میشه.

گفته بودم، به صفحات قبل دقت کنید.

سوال 4 رو بیشتر توضیح بدید.​

درخت رو ریشه دار کنید، اوّل ریشه رو رنگ کنید، بعد هر راسی رو که رنگ کرد، اگه پدرش رنگ شده نبود، رنگش کنید، و اگر رنگ شده بود، یه راسی رو پیدا کنید و رنگ کنید که پدرش رنگ شده باشه. اگه همچین راسی وجود نداشته باشه، مسئله تموم شده ( چرا؟ )

سوال 6 میشه m+n+k-2 مثالشم: 1 تا m و 1 تا n و 1 تا k که اعداد 3 تا m+n+k تولید میشه. من اثبات با استقراشو نمیدونم ولی بدون استقرا هم میشه الگوریتمی داد که m+n+k-2 عدد مختلف تولید کرد.
7 هم میشه 2n - 1 همون مرحله اول شما n مرحله است.
8 هم به ازای n شهر و k شکارچی میشه l (n - k)*k​

سوال 6 که سریع نوشتم، ولی با چند تا مثال بدیهی هست که بیشتر از m+n+k-2 تا نمی شه. علاوه بر این با استقرا ثابت می شه که بیشتر نمی شه. لازم که نیست الگوریتم بدید. همه اعداد از 1 تا k و n و m رو می دید.
سوال بعدی هم درسته، چون من مفهوم مرحله رو اشتباه متوجه شده بودم، در این صورت در هر مرحله یه نفر تسویه حساب می کنه و راحت می شه مثالی زد که با کمتر نشه.
سوال هشت هم برای کمک به استقرا ، درخت رو ریشه دار کنید. ( اگه درست یادم باشه کدوم سواله )

2 ب رو باید یه ارایه ساختار داد بعد برای اثباتش استقرا زد. ارایه ساختارش​

اگه درست درست یادم مونده باشه)
1 2 4 3 8 7 6 5 16 15 14 ... 9 32 ... 17 ...​

استقرا در حقیقت نوعی ارائه الگوریتم هستش. تقریبا همه الگوریتم های فصل 7 کریتیو حالت استقرایی دارند. و برای نوشتن شبه کدش هم راحت می شه از استقرا استفاده کرد.

 

[b_delshad]

پاسخ : ایده های کلی مرحله 2 ها

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

 

[Olympiad]

پاسخ : ایده های کلی مرحله 2 ها

اگه میشه یکی حل این سوالا رو کامل بگه !!!

سوال 8 دوره ی 19
سوال 7 دوره ی 18

 

[rezashiri]

پاسخ : ایده های کلی مرحله 2 ها

برای سوال 7 دوره 18

 

[b_delshad]

پاسخ : ایده های کلی مرحله 2 ها

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

عدد رنگ شده باقی مانده اند.
در ابتدای کار، چون مجموعه ها مجزا نیستند(معلومه دیگه چرا)، با بی رنگ کردن عددی که در بیشترین تعداد مجموعه ظاهر شده، حداقل دو مجموعه حذف می شوند.این روند ادامه دارد ، تا هنگامی که مجموعه های باقی مانده دو به دو مجزا شوند. از این به بعد، در هر مرحله دقیقن یک مجموعه حذف می شود.
اولین جایی را در نظر می گیریم که مجموعه ها مجزا شده اند. فرض کنیم تا الان، a عدد بی رنگ و b مجموعه حذف شده اند.داریم:

. چون کلا n عضو داریم و مجموعه ها 3 عضوی هستند، برای این که مجموعه ها مجزا باشند، تعدادشان نمیتواند از

بیشتر باشد. یعنی

، پس

.
برای حذف n - b مجموعه ی باقی مانده، باید دقیقن n-b عدد بی رنگ شوند(از هر مجموعه یکی). پس در نهایت، تعداد اعداد رنگی برابر

است. کافی است نشان دهیم

.
اگر

چون

، پس

. و اگر

، چون

پس

.
حل سوال به اتمام رسید.