سوال ۶
مورچه‌ای به کندوی زنبورها راه پیدا کرده است. او تنها می‌تواند روی مرز لانه‌ها حرکت کند. زنبورها از لانه‌هایی چرخان استفاده می‌کنند تا عسل آن‌ها شکرک نزند! این لانه‌ها در هر ثانیه یک واحد در جهت مشخص‌شده می‌چرخند.
مورچه یک ضلع را می‌تواند در یک ثانیه طی کند و همواره در ابتدای هر ثانیه تصمیم می‌گیرد که یا سر جای خود بایستد، یا به سمت یکی از تقاطع‌های مجاور خودش حرکت کند و تا رسیدن به تقاطع تصمیم خود را تغییر نمی‌دهد (حتی اگر به علت چرخش جهت حرکتش تغییر کند).
اگر مورچه در تقاطع $A$ باشد، کم‌ترین زمان لازم برای آن که به تقاطع $B$ برسد چقدر است؟
- ۶
- ۷
- ۸
- ۱۰
- ۱۱
راهنمایی
به صورت داینامیک مساله را حل کنیم. از پایین سمت چپ شروع کرده و کم‌ترین زمانی که می‌توانیم به هر کدام از تقاطع‌ها برسیم را محاسبه می‌کنیم.
پاسخ
گزینه‌ی ۲ درست است.
کافی است به صورت داینامیک مساله را حل کنیم.
از پایین سمت چپ شروع کرده و کم‌ترین زمانی که می‌توانیم به هر کدام از
تقاطع‌ها برسیم را محاسبه می‌کنیم. واضح است که اگر مورچه در یک تقاطع روی یک لانه‌‌ی چرخان باشد،
پس از یک ثانیه در یکی از سه تقاطع زیر قرار دارد:
- همان تقاطع (اگر خود مورچه در خلاف جهت چرخش بتواند حرکت کند و حرکت بکند.)
- یک تقاطع جلوتر در جهت چرخش (اگر حرکت نکند.)
- دو تقاطع جلوتر در جهت چرخش (اگر در جهت چرخش بتواند حرکت کند و حرکت بکند.)
در شکل بالا کوتاه‌ترین مسیر تا مقصد مشخص شده است.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
