اندر احوالات مرحله ۲

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

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

۱- دو خانه و به ۴ حالت. هر دو تا خونه ی کنجی رو که رو به روی هم نباشند اگه در نظر بگیرید خوبه. (البته به شرطی که ترتیب انتخاب خانه ها مهم نباشه. مگر نه می شه ۸ حالت. من بودم سر امتحان هر دو حالت رو می نوشتم.)

۲- نوشتنش خیلی سخته. نمی نویسم‌ :). فقط بدونید برای قسمت ت جوابی ندارم هنوز.

۳- nb - n2 + n. (هر نوع توپ باید تو حداقل b - n + 1 خونه باشه. n تا خونه یه توپه هر کدوم از یه نوع در نظر بگیرید و بقیه خونه ها با همه n نوع توپ. الان همین جملات رو با توضیح بنویسید باید ۳۵ بگیرید)

۴-

     الف:‌ فکر کنم میشه کف log ماکسیمم (a + 1) ها.

     ب  ‌: r تا میشه. (قشنگ از اون شهر مینیمه بگیرید هر جا دستگاه میگه برید میشه r بار. اگه توی یه درخت متوازن دو دویی هم باشید که k + 1 ای عمق داشته باشه، دقیقا مجبورید همین r تا رو برید.)

     ج ‌  : نمی دونم چی جوریه دقیقا. باید یه همچین چیزی ثابت کنید : توی هر گراف همبند n راسی ای، یه راسی وجود داره که اگه اون راس رو بپرسید، هر جوابی که بده، شهر های مظنون باقیمونده یه گراف همبند کمتر مساوی کف n/2 راسی رو ایجاد می کنن. (نوشتن این حدس هیچ نمره ای نداره ها! باید اثباتش کنید. منم فعلا بلد نیستم اثباتش رو)

فعلا حرف دیگه ای ندارم! :) کف هم نمی دم فعلا. تا ببینیم چه پیش خواهد آمد :)

شاد و سرزنده باشید! :)