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

[emadceh]

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

دوست من فکر می کنم که اشتباه می کنی حرکت اول که مهم نیست ۲ راس مجاور رو در نظر بگیره یا غیر مجاور رو در حرکت دوم مخالف کار حرکت اول رو انجام میده و تا اینجا وضعیت ۳ لیوان رو فهمیده از این به بعد داور رو باهوش در نظر می گیریم به طوری که حرکت ما رو می تونه حدس بزنه(آخه ما هم که باهوش هستیم ) در نتیجه می تونه کاری کنه که فقط وضعیت همون ۳ راس(لیوان) رو بفهمیم و مسئله به جواب نمیرسه

انقدر سر این سوال مسخره بحث نکنید .یکیتون بقیه سوالا رو ادامه بده .نوبت روز دوم دوره چهاردهمه.اگه فقط یه سوالم حل کردید بگید چون دوره 14 و 15 سوالاش خیلی سخت بودن .مخصوصا 15 .البته شاید فقط برای من سخت بوده. نظر شما چیه؟

 

[hoco.hc]

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

انقدر سر این سوال مسخره بحث نکنید .یکیتون بقیه سوالا رو ادامه بده .نوبت روز دوم دوره چهاردهمه.اگه فقط یه سوالم حل کردید بگید چون دوره 14 و 15 سوالاش خیلی سخت بودن .مخصوصا 15 .البته شاید فقط برای من سخت بوده. نظر شما چیه؟

دوره 15 روز اوّل:
مسئله 1: همه جایگشت ها رو در نظر بگیرید.
مسئله 2: توجه کنید اگه یه مسیر همیلتونی باشه که یه طرفش پایتخت باشه این نقشه قابل ساخته
مسئله 3: ثابت کنید هر عضو a در c هست و هر عضو c در a هست
مسئله 4: به ازای همه جایگشت ها می شه. اوّل 2k+1 رو میاریم آخر، 2k رو میاریم پشتش، 2k-1 رو میبریم آخر و در موقع مناسب می بریم پشت 2k و ... ( --> به ازای همه جایگشت ها می شه. ) ( فکر کنم )

----
پ.ن.: دوره 14 روز 1 بدترین امتحان عمر من بود.

 

[emadceh]

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

دوره 15 روز اوّل:
مسئله 1: همه جایگشت ها رو در نظر بگیرید.
مسئله 2: توجه کنید اگه یه مسیر همیلتونی باشه که یه طرفش پایتخت باشه این نقشه قابل ساخته
مسئله 3: ثابت کنید هر عضو a در c هست و هر عضو c در a هست
مسئله 4: به ازای همه جایگشت ها می شه ( فکر کنم )

----
پ.ن.: دوره 14 روز 1 بدترین امتحان عمر من بود.

سوال 4 یعنی چی که گفتی فکر کنم مگه اثباتش نکردی ؟.بعدشم قرار شد ایده کلی حل سوال رو بنویسی نه اینکه بگی جواب این میشه تو پرانتزم بگی فکر کنم:33:

 

[hoco.hc]

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

سوال 4 یعنی چی که گفتی فکر کنم مگه اثباتش نکردی ؟.بعدشم قرار شد ایده کلی حل سوال رو بنویسی نه اینکه بگی جواب این میشه تو پرانتزم بگی فکر کنم:33:

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

 

[mohsen2010]

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

فرض کنید که k تا مهره شماره n داریم.یکی رو نگه می داریم k-1 تا باشماره 2n و k-1 تا با شماره n+1 می کنیم.از این k-1 تا k-2 تا 2n+2 تولید میکنیم.و از k-1 تا 2n که داشتیم k-2 تا 2n+1 و از این ها k-3 تا 2n+2 ای تولید می کنیم.حال در مجموع 2k-5 تا مهره 2n+2 داریم که واضح است به ازای k>5 این مقدار از k بیشتر است.

شما با یه الگوریتم خاص پیش رفتی و ثابت کردی که نمیشه که این درست نیست بلکه باید ثابت کنی برای هر جور الگوریتمی نمیشه به جایی رسید که همه ی اعداد مختلف باشند.

سوال ۳ هم ایدش اینه که ثابت کنید اگه با a*bتا کشور بشه خواسته ی مسئله رو انجام داد برای(a*(b+2 و (b*(a+2 و (a*(2b و(b*(2a هم میشه اینکار رو انجام داد.

 

[mohsen2010]

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

سوال ۴ دوره ۱۴ روز اول هم ایدش اینه که ابتدا همه ی رشته ها ی متناظر به حروف رو از کوچیک به بزرگ مرتب می کنیم و تو یه درخت دو دویی ادشون می کنیم به این صورت که sرو ۱وoرو ۰ در نظر می گیریم و ابتدا از یه راس تنها شروع می کنیم اگه ابتدا ی رشته اول ۰ بود که یه ریشه متناظر۰ به این راس اضافه می کنیم اگه هم یه بود یه ریشه متناظر ۱ اضافه می کنیم و این کا را تا آخر رشته ادامه می دیم و سپس به آخرین ریشه که اضافه کنیم به یک متغیرمتناظر به آن یکی اضافه می کنیم(در ابتدا همه متغییر ها ۰ هستند) بعد رشته ی بعدی رو تو این درخت اد می کنیم اگر هم در اد کردن به یک متغییر رسیدیم که مقدارش بیشتر از ۰ بود و هنوز به آخر رشته نرسیده بودیم آن متغییر رو هم یکی اضافه می کنیم. این کار رو تا آخر ادامه می دهیم. به سراغ متغییر هایی که مقدارشون بیشتر از ۱ هست می رویم
اگه توی بچه های این رشته یه متغییر وجود داشت که بیشتر از ۰ بود پس دیگه متغیر متناظر به مسیر این پدر تا فرزندش در درخت نباید بیشتر از ۰ باشدپس در نتیجه به غیر از این مسیر مسیر دیگه ای که متناظر با این مسیر باشد نباید باشد.
اگه این درخت رو تحلیل کنید به همون رابطه خواسته شده می رسید.(عمق هر راس رو طول رشته در نظر بگیرید)

پ.ن:کل سعیم رو کردم که درست توضیح بدم امیدوارم راه حلم واضح باشه .
پ.ن:مثل اینکه سوال ۲ دوره ۱۴ روز اول هم جواب نداره (کلا OPENهست) تو متن اشتباه تایپی داره اصلش اینه کی عددn رو بر می داریم به جاش دو عدد 2nو2n+1قرار میدیم.

 

[emadceh]

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

دوره 16 :
روز اول
مسئله 1:الف)واضحه ب)الگوریتم بدید.
مسئله 2:با استقرا میشه .میشه یه الگوریتم هم داد.
مسئله 3:لامپ ها رو تصادفی وصل می کنیم .دوحالت پیش میاد.یا هیچی روشن نمیشه یا یکی روشن میشه.بعد هر دو حالت رو بررسی کرده و به نتیجه میرسیم.
مسئله 4: به ازای k=1 بدیهیه که با کم تر از k+1 نمیشه.حالا کوچکترین k ای رو در نظر بگیرید که با کم تر از k+1 میشه .بعد، از این نتیجه بگیرید که برای k-1 با کم تر از k میشه .پس به تناقض رسیدیم .
روز دوم:
مسئله 5:استقرا
مسئله 6: نمی دونم
مسئله 7:دو تا دوتا دسته بندی کنید.
مسئله 8:نمی دونم

حالا نوبت شماست دوره 17 یا 18

 

[hoco.hc]

پاسخ : ایده های کلی مرحله 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: سوالو درک نکردم. یکی بیشتر توضیح بده.

 

[emadceh]

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

7:فکر می کنم بشه (lg n ) - 1 . هر مرحله یکی بی حساب بشه. یه مثالی هم بزنید که کمتر نمی شه. ( کسی که بیشتر از همه پول داره در هر مرحله نصف می شه )

من 2n-1 به دست آوردم .البته مطمئن نیستم که با این مقدار بشه ولی مطمئنم از این کمتر نمیشه.فکر کنم با استقرا بشه ثابت کرد که با این مقدار میشه.

 

[hoco.hc]

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

من 2n-1 به دست آوردم .البته مطمئن نیستم که با این مقدار بشه ولی مطمئنم از این کمتر نمیشه.فکر کنم با استقرا بشه ثابت کرد که با این مقدار میشه.

lgn کمتر از 2n هست. lg n هم اینطوری که در هر مرحله کاری می کنیم که نصف بشند تعداد افراد. دو به دو می شینند. ( هر کسی با یه بدهکار ) یکیشون که پول کمتری بدهی یا طلب داره ، حسابش صاف می شه. ( یا سوال رو اشتباه متوجه شدم؟ )

 

[Olympiad]

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

lgn کمتر از 2n هست. lg n هم اینطوری که در هر مرحله کاری می کنیم که نصف بشند تعداد افراد. دو به دو می شینند. ( هر کسی با یه بدهکار ) یکیشون که پول کمتری بدهی یا طلب داره ، حسابش صاف می شه. ( یا سوال رو اشتباه متوجه شدم؟ )

تبادل پول فقط بین دو نفر صورت میگیره !!! شما تو هر مرحله دارید n تبادل پول انجام میدید ... 2n-1 هم درسته ، چون باید گرافمون همبند باشه و با استقرا هم میشه ثابت کرد که با این تعداد میشه ....... سوال 6 دوره ی 17 منظورتون m+n+k-2 بود دیگه ؟!؟!

راستی این سوال 2 یکم مشکوک میزنه ... آخه نمیشه که اینقد بدیهی بشه !!!!!!

اگه میشه سوال 5 رو کامل توضیح بدید

پ.ن : منم سوال 8 رو نفهمیدم !!!!

 

[hbsciw]

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

دوره 16
مسئله 6:یکی ، می توان ثابت کرد همه جدول ها در نهایت به جدول تمام صفر می رسند.
مسئله 8:الف)نمی توان در هر مرحله در جهت افقی یا عمودی از خانه دور می شود.
ب)نمی توان تغیر جهت ها یکی در میان ساعتگرد و پادساعتگرد هستند ، پس نمی توان یک دور را پیمود.

 

[hoco.hc]

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

تبادل پول فقط بین دو نفر صورت میگیره !!! شما تو هر مرحله دارید n تبادل پول انجام میدید ... 2n-1 هم درسته ، چون باید گرافمون همبند باشه و با استقرا هم میشه ثابت کرد که با این تعداد میشه ....... سوال 6 دوره ی 17 منظورتون m+n+k-2 بود دیگه ؟!؟! راستی این سوال 2 یکم مشکوک میزنه ... آخه نمیشه که اینقد بدیهی بشه !!!!!! اگه میشه سوال 5 رو کامل توضیح بدید پ.ن : منم سوال 8 رو نفهمیدم !!!!

سوال دو رو خودم هم اول شک داشتم. ولی شنیده بودم که دوره هفده راحته و از یکی هم پرسیدم گفت درسته.سوال پنج: اون pi رو در نظر گیرید که کمترین فاصله را با c دارد. C جایگشتی هست که کمترین فاصله رو با a داره. حالا اون pi با هر کدوم دیگه از جایگشت ها حداکثر دو برابر c از اون جایگشت فاصله داره.

 

[hoco.hc]

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

دوره 18 روز یک:
سوال 1: اوّل به طور رندوم انتخاب می کنیم. بعد اونایی که بیشتر از 3 تا هستند رو درست می کنیم.
سوال 2: الف: سطری ستونی
سوال 3: استقرا می شه 2n-1
سوال 4: اون قدر می ریم توی یه سالن تا دوباره همون شبکه نمایش داده بشه. ( یه دور ایجاد می شه ) بعد به یه سالنی می ریم که جایگشتش رو تا حالا ندونستیم، برای هر عدد حداکثر دو روز وقت هدر دادیم و یک روز هم در اوّل که در کل حداکثر می شه 2n-1 ( آخرین جایگشت رو لازم نیست بلد باشیم )

 

[mohsen2010]

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

بچه دوره ۱۴ روز دوم رو هیچکس حل نکرده؟ ویا ایده ای روش نداره؟

 

[graph]

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

بچه دوره ۱۴ روز دوم رو هیچکس حل نکرده؟ ویا ایده ای روش نداره؟

جواب ها رو میگم :5 الف میشه به هر a صفر و هر b یک نسبت بدید و ارزش رقم i ام از چپ رو دو به توان i بگیرید5 ب نمیشه مثال نقض ان abb است که با استقرا ثابت میشه توقف نا پذیره6 98 شطرنجی رنگ کنید ادامه بدید7 یه تناوب بسازید از بیشترین طول کلمات نحس استفاده کنید8 الف یه مثال بزنید دیگه8 ب نمیدونم کمک

 

[emadceh]

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

لطفا یه نفر جوابای روز دوم دوره 18 را بزاره و آقای hoco اون سوال 5 دوره 17 رو اگه میشه لطفا بهتر توضیح بدین من متوجه نشدم و سوال 4 دوره 17 قسمت دومش که a>1 گراف ستاره میشه اثبات اینکه این کمینه ست چه جوریه؟

 

[hoco.hc]

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

لطفا یه نفر جوابای روز دوم دوره 18 را بزاره و آقای hoco اون سوال 5 دوره 17 رو اگه میشه لطفا بهتر توضیح بدین من متوجه نشدم و سوال 4 دوره 17 قسمت دومش که a>1 گراف ستاره میشه اثبات اینکه این کمینه ست چه جوریه؟

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

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

که از اون جا که

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

 

[hoco.hc]

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

لطفا یه نفر جوابای روز دوم دوره 18 را بزاره و آقای hoco اون سوال 5 دوره 17 رو اگه میشه لطفا بهتر توضیح بدین من متوجه نشدم و سوال 4 دوره 17 قسمت دومش که a>1 گراف ستاره میشه اثبات اینکه این کمینه ست چه جوریه؟

دوره 18 روز دوم به نظرم سوالای 5و 7 سخت بودند. ( نتوستم حل کنم ) اگه کسی بلده بگه.
سوال 6: برعکس هر عدد رو پشتش می نویسیم.
سوال 8: الف : بدیهی ( با رسم شکل ) ، ب: اوّل ثابت کنید یه نفر هست که با همه مولفه همبندی هاش دوست هست، بعدش استقرا بزنید.

اینم سوال 5 دوره 17. امیدوارم بتونید دستخطم رو بخونید. سوال 5 دوره 17

 

[hoco.hc]

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

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