المپدیا

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

ابزار کاربر

ابزار سایت


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

شکارچیان خرس

سرزمین خرس‌ها ۱۳۸۶ شهر دارد با تعدادی جاده بین آن‌ها. هر جاده٬ دو شهر از این شهرها را به هم متصل می‌کند. لزوماً هر دو شهر مستقیماً با یک جاده به هم متصل نیستند٬ اما می دانیم که با کمک جاده‌ها می‌توان از هر شهر به هر شهر دیگر رفت.

اعضای گروه شکارچیان خرس٬ در تعدادی از شهرهای این منطقه مستقر شده‌اند. قانون اول این گروه می‌گوید هیچ دو عضوی از گروه نمی‌توانند هم‌زمان در یک شهر باشند (بنابراین تعداد شهرهایی که در هر زمان محل استقرار شکارچیان‌اند٬ با تعداد اعضای گروه برابر است.)

گروه ناگهان تصمیم می‌گیرد که اعضایش در مجموعه‌ای جدید از شهرها مستقر شوند. واضح است که طبق قانون اول٬ تعداد شهرهای این مجموعه‌ی جدید نیز با تعداد اعضای گروه برابر است. برای رسیدن به هدف فوق٬ هر روز٬ درست یک نفر از اعضای گروه می‌تواند با طی کردن فقط یک عدد از جاده‌ها٬‌ از شهری که در آن مستقر است به شهری دیگر (بالطّبع خالی) برود و در آن مستقر شود. برای گروه تنها این مهم است که هریک از شهرهای مجموعه‌ی جدید٬ محل استقرار یکی از اعضا شود. این مهم نیست که کدام عضو در پایان کار٬ در کدام شهر از شهرهای مقصد مستقر شده است.

اگر تصمیم گروه در همه‌ی حالات (یعنی برای هر مجموعه‌ی فعلی٬ هر مجموعه‌ی مقصد و نیز هر ترکیب قابل قبول از جاده‌ها) قابل اجرا باشد٬ حداقل تعداد روزهای لازم برای استقرار همه‌ی افراد در شهرهای انتخابی در بدترین حالت ممکن چه‌قدر است؟ اگر حالتی وجود دارد که چنین تصمیمی در آن عملی نیست٬ آن حالت کدام است؟ و چرا در این حالت٬ تصمیم گروه قابل اجرا نیست؟


ابزار صفحه