المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۳۰:سوال دو

فاصله‌گذاری اجتماعی (۲۰ نمره)

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

پاسخ


ابزار صفحه