Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۳

جعفر و سلاله در حال بازی روی یک دنباله به طول N هستند که همه‌ی اعضایش در ابتدا 0 می‌باشند. جعفر بازی را شروع می‌کند و بعد از هر نفر، نوبت به شخص دیگر می‌رسد. جعفر در نوبتش یک عضو از دنباله را که 0 است، انتخاب کرده و آن را به 1 تغییر می‌دهد. به طور مشابه، سلاله هم در نوبت خود یک عضو از دنباله را که 0 است، انتخاب می‌کند و آن را به 2 تغییر می‌دهد. بازی زمانی پایان می‌یابد که هیچ 0-ای در دنباله باقی نمانده باشد.

در این زمان، امتیاز جعفر برابر با تعداد جفت‌های 1 مجاور در دنباله، و امتیاز سلاله هم برابر با تعداد جفت‌های 2 مجاور در دنباله است. مثلاً اگر در پایان بازی، دنباله به شکل زیر در آمده باشد، امتیاز هر دو نفر برابر 2 می‌شود. 1,1,1,2,2,1,2,2,1 در صورتی که امتیاز دو نفر برابر باشد، بازی مساوی می‌شود و در غیر این صورت، برنده کسی است که امتیاز بالاتری به‌دست آورده باشد. هدف هر فرد در بازی این است که برنده شود، و اگر برنده‌شدن ممکن نبود، حداقل در صورت امکان، بازی را به‌تساوی بکشاند. اگر هر دو نفر بهینه بازی کنند، نتیجه‌ی بازی برای N=8 و N=9 به ترتیب (از راست به چپ) چه خواهد بود؟

  1. برد سلاله، برد سلاله
  2. برد جعفر، برد سلاله
  3. برد سلاله، برد جعفر
  4. مساوی، برد جعفر
  5. مساوی، برد سلاله

پاسخ

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


ابزار صفحه