المپیاد کامپیوتر مرحله 2 (بخش تشریحی)
- ارسال ها
- 2,239
- لایک ها
- 166
- امتیاز
- 0
- ارسال ها
- 2,239
- لایک ها
- 166
- امتیاز
- 0
shoki گفت
سلام امیر،تبریک می گم
!!! کسی نتونست 5 تا رو از اینجا (بین پسرا که این طوری بود) حل کنه ... راه حل قسمت ب سوال 5 رو هم لطف کن بگو تا تمام راه حل ها گفته شده باشه ، ممنونم !!
راستی ، سوال 3 رو چیجوری حل کردی ؟؟
راستی ، سوال 3 رو چیجوری حل کردی ؟؟
قسمت ب هم نوشتم تا در اومد
قسمت ب سوال 3 رو امروز می ذارم
به عماد قول دادم
سوال 5 - قسمت ب)
مقدار B برابر تعداد تغییرهاست. (اینو باید از روی الگوریتم تشخیص بدیم و اثبات کنیم.)
اگر این مقدار بیش از k×2[SUP]k[/SUP] شود ، طبق اصل لانه کبوتری یکی از درایه ها حداقل k+1 بار تغییر کرده است.
مقدار اولیه ی این درایه را با a[SUB]0[/SUB] نشان می دهم.مقدار بعد از تغییر اول را با a[SUB]1[/SUB] و ...
پس به ازای هر i ، می دانیم که تکرار ai از جمع همه ی a[SUB]j[/SUB] ها که j از i کوچکتر است ، بزرگتر است.(به راحتی می توان بررسی کرد که تساوی ممکن نیست)
چون مقدار تکرار a[SUB]0[/SUB] حداقل 1 است ، پس تکرار a[SUB]k+1[/SUB] بیش تر از 2[SUP]k[/SUP] می شود. ××تناقض××
- ارسال ها
- 2,239
- لایک ها
- 166
- امتیاز
- 0
shoki گفت
شرمنده امیر ولی چه جوری به حالت فرض استقرا می رسی ؟؟ با حذف برگ یا حذف یال ؟؟ ثانیا منظورت از این که
'فاصله ی k هم نداشته باشند.' چیه ؟
شرمنده که این قدر گیراییم پایینه
'فاصله ی k هم نداشته باشند.' چیه ؟
شرمنده که این قدر گیراییم پایینه
هر درخت رو میشه به چند مرتبه (پله) تقسیم کرد.
می تونیم طوری تعیین کنیم که در هر پله با پله ی بالایی تفاوت داشته باشندچ
اینجوری ساده تر هم هست
به هر حال ، این آخرین پست منه
خدانگهدار
- ارسال ها
- 335
- لایک ها
- 8
- امتیاز
- 0
سلام من هم اومدم.
دمت گرم گوهرشادی ترکوندی.
من هم 3.5 تا حل کردم. سوالات 1و2و4 پنج هم قسمت اول.
راه حل سوال یک من : ابتدا دلخواه این افراد را پخش میکنیم و سپس از شرکتی که افرادش ناراضی هستند هی یک نفر به اون شرکت میفرستیم.
سوال دو : دقیقا شبیه shoki.
سوال 4 : استقرا زدم و فرض استقرام رو قوی کردم و فرض این بود : توریست از هر شهر میگذرد و هر شهر بعد از مدت نامحدود نا متناهی بار میگذرد.
سوال 5 الف : دقیقا مثل shoki\
خیلی بده الان نه میدونم قبول میشم و نه میدونم رد میشم. به قولی در برزخم.
دمت گرم گوهرشادی ترکوندی.
من هم 3.5 تا حل کردم. سوالات 1و2و4 پنج هم قسمت اول.
راه حل سوال یک من : ابتدا دلخواه این افراد را پخش میکنیم و سپس از شرکتی که افرادش ناراضی هستند هی یک نفر به اون شرکت میفرستیم.
سوال دو : دقیقا شبیه shoki.
سوال 4 : استقرا زدم و فرض استقرام رو قوی کردم و فرض این بود : توریست از هر شهر میگذرد و هر شهر بعد از مدت نامحدود نا متناهی بار میگذرد.
سوال 5 الف : دقیقا مثل shoki\
خیلی بده الان نه میدونم قبول میشم و نه میدونم رد میشم. به قولی در برزخم.
