المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۳۳:تئوری نهایی اول:سوال ۱

سعی کنید سوالات را با کمترین راهنمایی از بالا به پایین حل کنید.

راهنمایی

بر روی رنگ راس ریشه حالت‌بندی کنید

راهنمایی

اگر ریشه قرمز باشد و قصد داشته باشیم زیرمجموعه‌ی پیدا شده‌ی مطلوب مسئله قرمز باشد، در هر یک از دو زیر درخت حاصل از حذف ریشه، می‌بایست به دنبال چه زیرمجموعه‌ای از رئوس باشیم؟ در صورتی که بخواهیم زیردرخت انتخابی آبی باشد چطور؟

راهنمایی

با استفاده از دو راهنمایی بالا، از استقرا استفاده کنید.

راهنمایی

بر روی $p+q$ استقرا بزنید.

راهنمایی

اگر ریشه قرمز باشد، در زیر درخت‌های چپ و راست به دنبال یافتن زیر مجموعه‌ای مطلوب از راس‌ها خواهیم بود که درختی با ارتفاع $p-1$ قرمز باشد، یا زیر درختی با ارتفاع $q$ به رنگ آبی. اگر ریشه آبی باشد چطور؟


ابزار صفحه