المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۱

خیکوله یک دستمال کاغذی $۴ \times ۴$ پیدا کرده است و ۱۶ پوست‌پسته جمع کرده است که $i$امین آن‌ها در $i$ ثانیه می‌سوزد. او می‌خواهد پوست‌پسته‌ها را روی خانه‌های دستمال کاغذی بگذارد و خانه‌ی بالا سمت راست آن را آتش بزند تا کل دستمال کاغذی بسوزد. نحوه‌ی سوختن دستمال کاغذی به این نحو است:

  • هر وقت یک خانه‌ی دستمال کاغذی آتش گرفت٬ اگر روی آن خانه یک پوست‌پسته باشد که در $t$ ثانیه می‌سوزد٬ بعد از $t$ ثانیه آن خانه می‌سوزد و خانه‌های مجاور‌ضلعی‌اش (در صورتی که قبلا آتش نگرفته باشند) آتش می‌گیرند.

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

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

پاسخ

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

برای سوختن خانه‌ی پایین سمت چپ حداقل به اندازه‌ی جمع اعداد ۱ تا ۷ (یعنی ۲۸ ثانیه) زمان لازم است. می‌توان بقیه را طوری چید که این زمان حاصل شود. جدول زیر نمونه‌ای از این چینش‌ها را نشان می‌دهد.


ابزار صفحه