سوال ۹
جزیره‌ی فلون که اکنون مسکونی شده است، ۱۰۰ شهر دارد که به شکل یک جدول $10 \times 10$ ساخته شده‌اند. در ابتدا شهر گوشه بالا راست جزیره به کرونا آلوده شده است. ابتدای هر روز، تنها یکی از شهرهای سالم که در مجاورت ضلعی حداقل یک شهر آلوده قرار گرفته است، به کرونا آلوده می‌شود. سپس دکتر ارنست یکی از شهرهای سالم را قرنطینه می‌کند و دیگر امکان ندارد آن شهر آلوده شود.
می‌دانیم شهرهای آلوده هیچ وقت به وضعیت سالم بر نمی‌گردند. دکتر ارنست با استفاده از دستگاه تشخیص کرونا از راه دور همواره می‌داند کدام شهرها آلوده هستند. هدف او کمینه کردن تعداد شهرهای آلوده است. اگر دکتر ارنست بهینه عمل کند، بیشینه‌ی تعداد شهرهای آلوده پس از گذشت ۱۰۰ روز از آغاز شیوع چه‌قدر است؟
- 5
- 4
- 6
- 11
- 16
پاسخ
گزینه (۱) درست است.
استراتژی دکتر ارنست: بدون کم شدن از کلیت می‌توان فرض کرد که خانه‌ای که در آن شماره ۱ قرار دارد اولین حرکت کرونا باشد. اگر دکتر ارنست خانه ۲ را قرنطینه کند می‌تواند با ماکسیمم ۵ خانه آلوده شهر را قرنطینه کند. هر بار که کرونا به یکی از خانه‌های $x, y, z$ رفت، دکتر ارنست خانه متناظر میان $x', y', z'$ را قرنطینه می‌کند.
با حالت‌بندی می‌توان ثابت کرد کرونا می‌تواند طوری گسترش پیدا کند که حداقل ۵ شهر آلوده شود(؟).
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
