المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲۸

پینوکیو برای یافتن پدر ژِپِتو وارد شکم نهنگ شد. شکم نهنگ به شکل مجموعه‌ای از سه‌راهی‌هاست که هر کدام به سه سه‌راهی دیگر متصل است. فاصله‌ی دو سه‌راهیِ متصل ۱ متر است. پدر ژپتو در یکی از سه‌راهی‌هاست. در هر سه‌راهی تابلویی وجود دارد که رویش فاصله‌ی آن سه‌راهی تا پدر ژپتو نوشته شده است. پینوکیو در یکی از این سه‌راهی‌هاست که تابلوی آن ۱۳۸۵ را نشان می‌دهد. با این فرض که پینوکیو به اندازه‌ی کافی باهوش است، در بدترین حالت چند متر باید راه برود تا به پدر ژپتو برسد؟

  1. ۱۳۸۵
  2. ۲۷۷۱
  3. ۴۱۵۵
  4. ۴۱۵۷
  5. ۶۹۲۵

پاسخ

گزینه‌ی (۴) درست است.

پینوکیو به جز مرحله‌ی اول همواره از یک مسیر وارد سه‌راهی شده و در نتیجه تنها دو مسیر پیش‌رو دارد. پس هر بار در بدترین حالت مجبور است یکی از سه‌راهی‌ها را برود و برگردد و سپس وارد مسیر درست شود. در نتیجه هربار 3متر را طی می‌کند و در ازای آن یک متر از فاصله او با پدر ژپتو کاسته خواهد شد. البته در مرحله‌ی اول باید 5 متر طی کند. پس در کل 1385×3+2= 4157 متر باید بپیماید.


ابزار صفحه