المپدیا

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

ابزار کاربر

ابزار سایت


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

جاده ها

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


ابزار صفحه