اولین باره که به کاهو میای؟ راهنمای سایت رو حتما بخون!
بازی رنگی - سوال ۱ - مرحله ۲ - ۱۳۹۳
وزنهها و ماشین جادویی - سوال ۲ - مرحله ۲ - ۱۳۹۳
گاوی خسیس - سوال ۳ - مرحله ۲ - ۱۳۹۳
انتقال مهرههای گاوی - سوال ۴ - مرحله ۲ - ۱۳۹۳
یافتن کوچکترین پیچ و مهره با مقایسه آنها
دنباله و جادوگر - دوره ی 24 - مرحله ی 2
مسئله ی مسیر و شبکه - مرحله ی 2 – دوره ی 23
در این قسمت میتونی به یک پرسش پاسخ بدی. اگه میخوای در مورد پرسش بحث و اظهار نظر کنی از قسمت «ثبت نظر» استفاده کن.
پاسخت رو دقیق و کامل بنویس، از عکس استفاده کن و اگه لازمه به منابع (کتاب یا سایت) ارجاع بده.
اگه پرسش یا پاسخها مفید هستند حتما بهشون رای بده تا پرسشها و پاسخهای خوب مشخص بشن.
توی قسمت پیشنمایش میتونی ببینی متنی که نوشتی چجوری روی سایت دیده میشه.
خیلی مهم: برای اینکه به خط بعد بری باید دوتا Enter بزنی.
میتونی از تگهای معمولی و سادهی html هم استفاده کنی.
با دکمههایی که بالای ویرایشگر قرار دارند کلی کار میشه کرد. از عکسگذاشتن بگیر تا لیست شمارهدار. حتما امتحانشون کن.
برای نوشتن علائم ریاضی میتونی از Mathjax استفاده کنی.
راهنمای Mathjax رو از سایت
math.stackexchange
بخون.
برای نوشتن عبارت ریاضی وسط جمله، اون عبارت رو بین دوتا $ قرار بده.
برای نوشتن عبارت ریاضی تو یه خط جدید اون رو بین دوتا $$ قرار بده.
......................................
نکته: جوابم برا قسمت الف و ب یه کم طولانی بود؛ لذا اونا رو به مرور زمان می ذارم. فعلا جواب قسمت ج رو می ذارم که کوتاهه.
اثبات: از اونجایی که ما حداکثر 350 راس واسه پرسش می دیم و در ضمن، درخت ما 351 بخش داره، پس بخشی وجود داره که هیچ کدوم از راس هاش برای پرسش داده نشدن. فرض کنید بخش i چنین ویژگی ای داشته باشه؛ پس منطقا هیچ یک از رئوس $a_i$ و $b_i$ برای پرسش داده نشدن. حالا اگه راس انتخابی البرز، یکی از این دو راس باشند، بیتا به طور یکتا نمی تواند تشخیص بدهد که کدامشان راس انتخابی البرز است.
توجه کنید که به جز خودِ $a_i$ و $b_i$، به ازای هر راس دیگر در درخت، فاصله اش تا این دو راس، یکسان است.
قسمت ب.
فرض کنید دو راس v , u باشه که بینشون مردد باشیم. اولا چون فاصلهشون از ریشه معلومه، هم ارتفاع هستند. حالا lca شون رو در نظر بگیرید. w مینامیمش. این راس قطعا دو شاخه است. و نکته اینه اگه راسی تو زیردرخت w باشه که داخل لیست باشه، فاصله ش از v , u متفاوته. و چون w دوشاخه ست قطعا تو زیردرختش راس دوشاخه ساده وجود داره (ممکنه خودش باشه ولی مهم نیست) پس راسی تو لیست داریم که فاصله ش از v , u متفاوته!
آره منم اومدم فرض کردم که فاصله ی ریشه تا راس البرز برابر k باشه و بعد روی رئوسی که ارتفاعشون k بود حالت بندی کردم...
2024-04-23 12:38:04 -0500 در برزخ