شاززز

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

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

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

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

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

۴-

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

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

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

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

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