المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۹

در بازی خرگوش‌کشی که در سوال قبل گفته شد، هر بار که مرد خرگوشی را بکُشد که نه در سطرِ آن و نه در ستونِ آن، خرگوش زنده‌ی دیگری نباشد، یک امتیاز می‌گیرد(دقّت کنید که پس از کشتن خرگوش آخر نیز امتیاز می‌گیرد). او حدّاکثر چند امتیاز می‌تواند بگیرد؟

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

پاسخ

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

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


ابزار صفحه