المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۲۲:سوال دو

جاده ها

کشور آتلانتیس دارای $2n$ شهر است که هر دو شهر با یک جاده (خاکی یا آسفالت) مستقیم به یکدیگر متصل هستند. یک روز، وزارت راه این کشور که سابقه‌ی طولانی در اتخاذ تصمیم های عجیب و غریب دارد، تصمیم می‌گیرد که شهرهای کشور را به دو استان ( نه لزوما با تعداد شهرهای برابر) تقسیم کند. این تصمیم باید طوری اجرایی شود که هر جاده میان دو شهر در یک استان، آسفالت باشد. برای انجام این هدف، وزارت راه در نظر دارد هر روز $n$ جاده که هیچ دو جاده‌ای به یک شهر منتهی نیستند را انتخاب کرده و همه ی جاده‌های خاکی انتخاب شده را آسفالت و همه‌ی جاده‌های آسفالت انتخاب شده را خاکی کند. با فرض اینکه نوع جاده‌ها در روز آغازین دلخواه هستند، آیا وزارت راه موفق می‌شود کشور را به دو استان با شرایط گفته شده تقسیم کند؟


ابزار صفحه