المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۳

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

  1. ۳۶
  2. ۲۸
  3. ۲۶
  4. ۲۱
  5. ۱۷

پاسخ

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

با انتخاب جاده‌های نشان‌داده‌شده در شکل زیر می‌توان با مجموع هزینه‌ی ۱۷ تمام شهرها را با مسیر آسفالت به هم متصل کرد.


ابزار صفحه