المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱۵:سوال ۲۳

سؤال ۲۳

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

• از هر خانه به هرکدام خانه‌های مجاور (حداکثر ۴ خانه )، ۱ تومان.

• از هر خانه‌ی سیاه به هر خانه‌ی سیاه دیگر، رایگان است.

حرکت به‌غیراز دو صورت گفته‌شده در بالا ممکن نیست. حداقل هزینه‌ای که این شخص باید بپردازد چه قدر است؟

  1. ۹٫۹۹۹
  2. ۵٫۰۰۰
  3. ۴٫۹۹۹
  4. ۵٫۰۰۱
  5. ۹٫۹۹۸

پاسخ

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

اولا باید توجه داشت که برای ورود و خروج هر مربع سفیدی مجموعا ۲تومان هزینه می‌شود و ثانیا به غیر از خانه‌های اول و آخر٬ ورود و خروج لازم دارند. واضع است که خانه اول ورود ندارد و نیز می‌توان حرکات آخر را چنان چید(مطابق شکل)که آخرین خانه سفید باشد و خروجی لازم نداشته باشد که در این صورت هزینه انجام شده برابر $(5000\times2)-2$ یعنی ۹۹۹۸ خواهد شد.


ابزار صفحه