المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۴۰

یک ساختمان قدیمی تعداد زیادی اتاق تودرتو دارد. دو اتاق مجاور تنها از طریق یک در با هم ارتباط دارند و بین آن‌ها راه‌رویی نیست. نقشه‌ی اتاق‌های این ساختمان به صورت روبه‌رو است. در این نقشه در بین دو اتاق با یک خط نشان داده شده است. اتاق $A$ تنها اتاقی است که به بیرون راه دارد. در یکی از اتاق‌های این ساختمان مار کوچک و خطرناکی مخفی شده است و ما می‌خواهیم با استتخدام تعدادی نگهبان آن را قبل از خروج بگیریم. فرض کنید:

  • جست‌و‌جوی هر اتاق وقت زیادی می‌گیرد، بنابراین هر اتاق را فقط یک بار می‌توان جست‌وجو کرد.
  • مار می‌تواند از زیر در اتاق‌ها رد شود و از یک اتاق به هر اتاقی که راه دارد برود و در آن‌جا مخفی شود.
  • اگر در مسیر حرکت مار، اتاقی باشد که نگهبانی در آن ایستاده باشد، آن نگهبان مار را می‌بیند و می‌تواند آن را بگیرد.

حداقل چند نگهبان برای گرفتن مار لازم است؟

  1. ۲
  2. ۳
  3. ۴
  4. ۵
  5. ۶

ابزار صفحه