المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲۹

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

نیلوفر و لی‌لی قبل از آن که مقادیر عوارض شهرها را در کتابچه‌ی راهنمای سفر خود ببینند، حرف‌های زیر را زده‌اند. کدام یک از این گفته‌ها به ازای مقادیر مختلفی که ممکن است در دفترچه‌ی راهنما نوشته شده باشد همواره درست است؟

  1. نیلوفر: من کمتر خرج خواهم کرد.
  2. لی‌لی: من کمتر خرج خواهم کرد.
  3. نیلوفر: ممکن است مقادیر دفترچه‌ی راهنما طوری باشد که من مجبور شوم بیشتر خرج کنم.
  4. لی‌لی: مجبور نیستم بیشتر خرج کنم.
  5. نیلوفر:مجبور نیستم بیشتر خرج کنم.

پاسخ

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

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


ابزار صفحه