ایده های کلی مرحله 2 ها
پاسخ : ایده های کلی مرحله 2 ها
دوره 12 روز یک:
سوال 1: ( سوالش مشکل داره ، یه مثال نقض برای پایه اش وجود داره ) استقرا+ اکسترمال+لانه . در هر مرحله ستونی که بیشترین تعداد یک علامت نخورده را دارد انتخاب و همه یک های همسطر را علامت بزنید.
سوال 2: الف: مثال نقص، ب: اثبات منطقی ( هر کدام از دایره ها با شعاع r حداکثر یکی از اعضای s را می پوشانند )
سوال 3: بلد نیستم. بلدی بگو
سوال 4: الف: همه به جز بیت اختلاف دار را یک کنید و بعد بیت اختلاف دار رو. ب: از قسمت الف استفاده کنید.
-------------------
پ.ن.: سوال 2-ب اصلاح شد. // اینو قبلا حل کرده بودم دقیقا یادم نبود .
دوره 12 روز یک:
سوال 1: ( سوالش مشکل داره ، یه مثال نقض برای پایه اش وجود داره ) استقرا+ اکسترمال+لانه . در هر مرحله ستونی که بیشترین تعداد یک علامت نخورده را دارد انتخاب و همه یک های همسطر را علامت بزنید.
سوال 2: الف: مثال نقص، ب: اثبات منطقی ( هر کدام از دایره ها با شعاع r حداکثر یکی از اعضای s را می پوشانند )
سوال 3: بلد نیستم. بلدی بگو
سوال 4: الف: همه به جز بیت اختلاف دار را یک کنید و بعد بیت اختلاف دار رو. ب: از قسمت الف استفاده کنید.
-------------------
پ.ن.: سوال 2-ب اصلاح شد. // اینو قبلا حل کرده بودم دقیقا یادم نبود .
آخرین ویرایش توسط مدیر
پاسخ : ایده های کلی مرحله 2 ها
سوال 2 دوره دوازده قسمت ب مثال نقض نیست، اثبات میشه.فقط الفش مثال نقضه.
دوره 14 ، روز اول:
مساله 1 دوره 14:نوشتن حلش اینجا غیر ممکنه ولی جواب آخرش فکر کنم 5 میشه که برای اثباتش فقط باید شکل بکشید و حالتها رو بررسی کنید و ...و در کل سوال جالبی نیست(به نظر من)
مساله 2دوره 14:امکان نداره.میشه ثابت کرد اگه ابتدا k تا از یه مهر با شماره n ،داسته باشیم در پایان حدقل k تا از یه مهره دیگه داریمو در کل سوال خیلی خیلی قشنگیه.
مساله 3 دوره 14: حل نکردم.اگه ایده ای دارید یگید.
مساله4 دوره 14: حل نکردم.اگه ایده ای دارید یگید .من شنیدم که این سوال سخت ترین سوال تاریخ المپیاد کامپیوتر ایران بوده.
سوال 2 دوره دوازده قسمت ب مثال نقض نیست، اثبات میشه.فقط الفش مثال نقضه.
دوره 14 ، روز اول:
مساله 1 دوره 14:نوشتن حلش اینجا غیر ممکنه ولی جواب آخرش فکر کنم 5 میشه که برای اثباتش فقط باید شکل بکشید و حالتها رو بررسی کنید و ...و در کل سوال جالبی نیست(به نظر من)
مساله 2دوره 14:امکان نداره.میشه ثابت کرد اگه ابتدا k تا از یه مهر با شماره n ،داسته باشیم در پایان حدقل k تا از یه مهره دیگه داریمو در کل سوال خیلی خیلی قشنگیه.
مساله 3 دوره 14: حل نکردم.اگه ایده ای دارید یگید.
مساله4 دوره 14: حل نکردم.اگه ایده ای دارید یگید .من شنیدم که این سوال سخت ترین سوال تاریخ المپیاد کامپیوتر ایران بوده.
آخرین ویرایش توسط مدیر
پاسخ : ایده های کلی مرحله 2 ها
دوره 10، روز دوم:
مسئله اوّل : هر کدام از اعداد روی تقاطع ها، دقیقا 4 بار استفاده میشود. و مجموع همه اعداد زوج میشه برای n=4k
مسئله دوم: الگوریتمی ارائه دهید که همه زیر مجموعه ها را چک کنه.
مسئله سوم: ابتدا حرف اوّلشان را بر اساس حروف الفبا مرتب می کنیم. حل دو حرف پشت سر هم داریم. توجه کنید که همه جایگشت های دوری را در اختیار داریم.
مسئله چهارم: به توان های دو توجه کنید.
دوره 10، روز دوم:
مسئله اوّل : هر کدام از اعداد روی تقاطع ها، دقیقا 4 بار استفاده میشود. و مجموع همه اعداد زوج میشه برای n=4k
مسئله دوم: الگوریتمی ارائه دهید که همه زیر مجموعه ها را چک کنه.
مسئله سوم: ابتدا حرف اوّلشان را بر اساس حروف الفبا مرتب می کنیم. حل دو حرف پشت سر هم داریم. توجه کنید که همه جایگشت های دوری را در اختیار داریم.
مسئله چهارم: به توان های دو توجه کنید.
پاسخ : ایده های کلی مرحله 2 ها
مساله چهار يه سوال دابل كانتينگهقبول داري كه اگر يكي از كلمه هاي بارون پيشوند يكي ديگه باشه آنوقت يك كلمه ممكنه دوجور معني بده پس بايد ما كلمه هايي و بگيريم كه هيچ يك پيشوند اون يكي نباشه آنوقت يك جدول مي كشيم كه يك طرفكل كلمه هايي بو طول بيشترين طول كلمه هاي بارون و يك طرف ديگه همه ي كلمات كه بارون ساخته.حال اگر تو خونه ي اين جدول ١ مي ذاريم كه كلمه ي بارون پيشوند باشه بعد از اون طرف هم ماكيسممو بدست بيار بعد دو طرف ساده ميشن و حكم اثبات ميشه
مساله چهار يه سوال دابل كانتينگهقبول داري كه اگر يكي از كلمه هاي بارون پيشوند يكي ديگه باشه آنوقت يك كلمه ممكنه دوجور معني بده پس بايد ما كلمه هايي و بگيريم كه هيچ يك پيشوند اون يكي نباشه آنوقت يك جدول مي كشيم كه يك طرفكل كلمه هايي بو طول بيشترين طول كلمه هاي بارون و يك طرف ديگه همه ي كلمات كه بارون ساخته.حال اگر تو خونه ي اين جدول ١ مي ذاريم كه كلمه ي بارون پيشوند باشه بعد از اون طرف هم ماكيسممو بدست بيار بعد دو طرف ساده ميشن و حكم اثبات ميشه
پاسخ : ایده های کلی مرحله 2 ها
مساله چهار يه سوال دابل كانتينگهقبول داري كه اگر يكي از كلمه هاي بارون پيشوند يكي ديگه باشه آنوقت يك كلمه ممكنه دوجور معني بده پس بايد ما كلمه هايي و بگيريم كه هيچ يك پيشوند اون يكي نباشه آنوقت يك جدول مي كشيم كه يك طرفكل كلمه هايي بو طول بيشترين طول كلمه هاي بارون و يك طرف ديگه همه ي كلمات كه بارون ساخته.حال اگر تو خونه ي اين جدول ١ مي ذاريم كه كلمه ي بارون پيشوند باشه بعد از اون طرف هم ماكيسممو بدست بيار بعد دو طرف ساده ميشن و حكم اثبات ميشهسوال چهار دوره چهاردهم
مساله چهار يه سوال دابل كانتينگهقبول داري كه اگر يكي از كلمه هاي بارون پيشوند يكي ديگه باشه آنوقت يك كلمه ممكنه دوجور معني بده پس بايد ما كلمه هايي و بگيريم كه هيچ يك پيشوند اون يكي نباشه آنوقت يك جدول مي كشيم كه يك طرفكل كلمه هايي بو طول بيشترين طول كلمه هاي بارون و يك طرف ديگه همه ي كلمات كه بارون ساخته.حال اگر تو خونه ي اين جدول ١ مي ذاريم كه كلمه ي بارون پيشوند باشه بعد از اون طرف هم ماكيسممو بدست بيار بعد دو طرف ساده ميشن و حكم اثبات ميشهسوال چهار دوره چهاردهم
پاسخ : ایده های کلی مرحله 2 ها
دوره 14
سوال 1 : نمیشه چون داور میز رو به دلخواه میچرخونه پس امکان داره مهره های تکراری رو هر دفعه برداریم
سوال 2 : میشه : با استقرا رو تعداد مهره ها اول تعداد مهره های کمترین شماره رو 1 میکنیم بقیه طبق فرض استقرا
سوال 3 : من یه الگوریتم ارایه دادمکه میشه با استفاده از مثال سوال
سوال 4 : فعلا نمیدونم
دوره 14
سوال 1 : نمیشه چون داور میز رو به دلخواه میچرخونه پس امکان داره مهره های تکراری رو هر دفعه برداریم
سوال 2 : میشه : با استقرا رو تعداد مهره ها اول تعداد مهره های کمترین شماره رو 1 میکنیم بقیه طبق فرض استقرا
سوال 3 : من یه الگوریتم ارایه دادمکه میشه با استفاده از مثال سوال
سوال 4 : فعلا نمیدونم
پاسخ : ایده های کلی مرحله 2 ها
مساله 1 دوره 14: خیلی برام جالبه بدونم الگوریتمتون با 5 تا یا 7 تا چجوریه؟ من خودم فکر کنم که نمی تونه. چون اگه لیوان ها رو شماره گزاری کنیم، ممکنه مثلا لیوان با شماره 1 ( که در ابتدا پایین بوده ) هیچ وقت توی دست علی نیاد. ( تایید حرف graph )
مساله 2 دوره 14: مثال نقض برای حرف شما آقا عماد: 2و 2 -> 2و 3 و4 . و فکر کنم جواب بله باشه. با استقرا می شه ثابت کرد. در هر مرحله اون عددی که بیشتر از یکی ازش داریم رو انتخاب می کنیم، و بزرگش می کنیم و همه اعداد به دست اومده از اون رو از بزرگترین عدد موجود بزرگ تر می کنیم ( این کار همیشه ممکن است )
مساله 3 دوره 14: برای |m-n| = 2k یه الگوریتم پیدا کردم. برای بقیه ( تفاضلشون فرد باشه ) سر جلسه راهی به ذهنم نرسید.
مساله 4 دوره 14: بدون شرح
مساله 1 دوره 14: خیلی برام جالبه بدونم الگوریتمتون با 5 تا یا 7 تا چجوریه؟ من خودم فکر کنم که نمی تونه. چون اگه لیوان ها رو شماره گزاری کنیم، ممکنه مثلا لیوان با شماره 1 ( که در ابتدا پایین بوده ) هیچ وقت توی دست علی نیاد. ( تایید حرف graph )
مساله 2 دوره 14: مثال نقض برای حرف شما آقا عماد: 2و 2 -> 2و 3 و4 . و فکر کنم جواب بله باشه. با استقرا می شه ثابت کرد. در هر مرحله اون عددی که بیشتر از یکی ازش داریم رو انتخاب می کنیم، و بزرگش می کنیم و همه اعداد به دست اومده از اون رو از بزرگترین عدد موجود بزرگ تر می کنیم ( این کار همیشه ممکن است )
مساله 3 دوره 14: برای |m-n| = 2k یه الگوریتم پیدا کردم. برای بقیه ( تفاضلشون فرد باشه ) سر جلسه راهی به ذهنم نرسید.
مساله 4 دوره 14: بدون شرح
پاسخ : ایده های کلی مرحله 2 ها
به hoco.hc :
در مورد سوال دوم دوره ی 14 دارید اشتباه میکنید !!!!! اون مثالی که شما گفتید مثال نقض نیست که !!! شما فقط یه مثال دادید که میشه این کار رو کرد در حالی که جواب مسئله "خیر" هست و emadceh درست گفتن ضمن اینکه جوب شما اینه که لزوما(حتما) تعداد جرکاتی که انجام میدید متناهی نیست! ...
به hoco.hc :
در مورد سوال دوم دوره ی 14 دارید اشتباه میکنید !!!!! اون مثالی که شما گفتید مثال نقض نیست که !!! شما فقط یه مثال دادید که میشه این کار رو کرد در حالی که جواب مسئله "خیر" هست و emadceh درست گفتن ضمن اینکه جوب شما اینه که لزوما(حتما) تعداد جرکاتی که انجام میدید متناهی نیست! ...
- ارسال ها
- 56
- لایک ها
- 26
- امتیاز
- 0
پاسخ : ایده های کلی مرحله 2 ها
جواب مسئله 1 دوره چهارده (پاسخ خودم )
ابتدا دو گوشه مجاور رو انتخاب می کنیم ( اگر اول بار می تونن همه شون یالا یا همشون پایین باشن یکبار بدون تغییر لیوان ها منتظر شنیدن صدای داور میشیم :4: ) یک مرحله اضافه میشه اگر امکان این باشه که همون اول بار لیوان ها همه یا بالا باشن یا پایین
1. دو لیوان مثل هم باشن : فرض کنیم هر دو لیوان بالا (پایین) باشند حالا هر دو لیوان را برعکس می کنیم یا همه پایین ( بالا ) می شوند که مسئله حل است یا 3تا پایین 1 بالا (3 تا بالا 1 پایین ) حال دو گوشه مجاور را انتخاب می کنیم اگر یک بالا داشت یک پایین لیوانی را که بالا ( پایین ) است برعکس می کنیم و مسئله حل است اگر هر دو پایین باشند یکی را برعکس می کنیم پس الان دو لیوان بالا و دو لیوان پایین داریم حال دو گوشه رو به رو انتخاب می کنیم اگر هر دو مثل هم باشند هر دو را برعکس می کنیم و مسئله حل است اگر یکی بالا باشد و یک پایین باز هم هر دو را برعکس می کنیم حال دو گوشه مجاور را درنظر میگیریم اگر هر دو مثل هم بودن که هر دو را برعکس می کنیم و مسئله حل است و اگر یکی بالا بود و دیگری پایین باز هم هر دو را برعکس می کنیم برای بار بعد کافی است دو گوشه روبه رو درنظر بگیریم که صد در صد مثل هم هستند یعنی یا هر دو بالا و یا هر دو پایین هستند پس با برعکس کردن آن دو مسئله حل می شود
2 دو لیوان مثل هم نباشند : هر دو لیوان را به دلخواه یا بالا یا پایین می گذاریم فرض می کنیم بالا گذاشتیم
اگر 2 لیوان مجهول یا هر دو بالا هستند که مسئله حل است در غیر این صورت دو گوشه رو به رو در نظر می گیرم یا یکی بالا یکی پایین یا هر دو بالا هستند اگر هر دو بالا بودند که می رسیم به حالت 3 به 1 که بالا توضیح دادم
اما اگر یکی بالا و یکی پایین بود اونی که پایین است رو رو به بالا می کنیم یا خانه مجهول بالا است که در این صورت مسئله حل است یا پایین است (که وقتی داور نگفت موفق شدی می فهمیم :4: ) که دوباره به حالت 3 به 1 رسیدیم
دهنم سرویس شد تا اینو نوشتم :4:
جواب مسئله 1 دوره چهارده (پاسخ خودم )
ابتدا دو گوشه مجاور رو انتخاب می کنیم ( اگر اول بار می تونن همه شون یالا یا همشون پایین باشن یکبار بدون تغییر لیوان ها منتظر شنیدن صدای داور میشیم :4: ) یک مرحله اضافه میشه اگر امکان این باشه که همون اول بار لیوان ها همه یا بالا باشن یا پایین
1. دو لیوان مثل هم باشن : فرض کنیم هر دو لیوان بالا (پایین) باشند حالا هر دو لیوان را برعکس می کنیم یا همه پایین ( بالا ) می شوند که مسئله حل است یا 3تا پایین 1 بالا (3 تا بالا 1 پایین ) حال دو گوشه مجاور را انتخاب می کنیم اگر یک بالا داشت یک پایین لیوانی را که بالا ( پایین ) است برعکس می کنیم و مسئله حل است اگر هر دو پایین باشند یکی را برعکس می کنیم پس الان دو لیوان بالا و دو لیوان پایین داریم حال دو گوشه رو به رو انتخاب می کنیم اگر هر دو مثل هم باشند هر دو را برعکس می کنیم و مسئله حل است اگر یکی بالا باشد و یک پایین باز هم هر دو را برعکس می کنیم حال دو گوشه مجاور را درنظر میگیریم اگر هر دو مثل هم بودن که هر دو را برعکس می کنیم و مسئله حل است و اگر یکی بالا بود و دیگری پایین باز هم هر دو را برعکس می کنیم برای بار بعد کافی است دو گوشه روبه رو درنظر بگیریم که صد در صد مثل هم هستند یعنی یا هر دو بالا و یا هر دو پایین هستند پس با برعکس کردن آن دو مسئله حل می شود
2 دو لیوان مثل هم نباشند : هر دو لیوان را به دلخواه یا بالا یا پایین می گذاریم فرض می کنیم بالا گذاشتیم
اگر 2 لیوان مجهول یا هر دو بالا هستند که مسئله حل است در غیر این صورت دو گوشه رو به رو در نظر می گیرم یا یکی بالا یکی پایین یا هر دو بالا هستند اگر هر دو بالا بودند که می رسیم به حالت 3 به 1 که بالا توضیح دادم
اما اگر یکی بالا و یکی پایین بود اونی که پایین است رو رو به بالا می کنیم یا خانه مجهول بالا است که در این صورت مسئله حل است یا پایین است (که وقتی داور نگفت موفق شدی می فهمیم :4: ) که دوباره به حالت 3 به 1 رسیدیم
دهنم سرویس شد تا اینو نوشتم :4:
آخرین ویرایش توسط مدیر
پاسخ : ایده های کلی مرحله 2 ها
اولا که من گفتم که در پایان حداقل k تا ... و دوما دقت کنید که من اثباتم رو کامل نگفتم . در پایان اثبات من ثابت میشه که باید k >5 باشه ولی برای k <5 مثال شما درسته.
نوشتن اثبات دقیقم اینجا مشکله چون باید نمودار درختی بکشی ولی اگه می خوای تا بنویسم.
اولا که من گفتم که در پایان حداقل k تا ... و دوما دقت کنید که من اثباتم رو کامل نگفتم . در پایان اثبات من ثابت میشه که باید k >5 باشه ولی برای k <5 مثال شما درسته.
نوشتن اثبات دقیقم اینجا مشکله چون باید نمودار درختی بکشی ولی اگه می خوای تا بنویسم.
آخرین ویرایش توسط مدیر
پاسخ : ایده های کلی مرحله 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 بیشتر است.
فرض کنید که 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 بیشتر است.
- ارسال ها
- 103
- لایک ها
- 35
- امتیاز
- 0
پاسخ : ایده های کلی مرحله 2 ها
دوست من فکر می کنم که اشتباه می کنی حرکت اول که مهم نیست ۲ راس مجاور رو در نظر بگیره یا غیر مجاور رو در حرکت دوم مخالف کار حرکت اول رو انجام میده و تا اینجا وضعیت ۳ لیوان رو فهمیده از این به بعد داور رو باهوش در نظر می گیریم به طوری که حرکت ما رو می تونه حدس بزنه(آخه ما هم که باهوش هستیم
) در نتیجه می تونه کاری کنه که فقط وضعیت همون ۳ راس(لیوان) رو بفهمیم و مسئله به جواب نمیرسه
پ.ن:مثل اینکه من اشتباه می کنم و راه حل شما درسته.
دوست من فکر می کنم که اشتباه می کنی حرکت اول که مهم نیست ۲ راس مجاور رو در نظر بگیره یا غیر مجاور رو در حرکت دوم مخالف کار حرکت اول رو انجام میده و تا اینجا وضعیت ۳ لیوان رو فهمیده از این به بعد داور رو باهوش در نظر می گیریم به طوری که حرکت ما رو می تونه حدس بزنه(آخه ما هم که باهوش هستیم
) در نتیجه می تونه کاری کنه که فقط وضعیت همون ۳ راس(لیوان) رو بفهمیم و مسئله به جواب نمیرسهپ.ن:مثل اینکه من اشتباه می کنم و راه حل شما درسته.
آخرین ویرایش توسط مدیر