المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۳۹

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

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

پاسخ

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

با فرض این که چاه در روستای ۱ باشد با انتقال چاه از روستای ۱ به ۲ راه ۵ روستا هر کدام یک واحد اضافه شده ولی در عوض راه ۱۶ روستا هر کدام یک واحد کم خواهد شد٬ بنابراین روستای ۲ بهتر از روستای ۱ است.با انتقال چاه از روستای ۲ به روستای ۳ راه ۴ روستا هر کدام یک واحد کم شده ولی در عوض راه ۱۷ روستا هر کدام یک واحد اضافه می‌شود٬ بنابراین روستای ۲ بهتر از روستای ۳ می‌باشد. با انتقال چاه از روستای ۲ به روستای ۴ راه ۱۱ روستا ه رکدام یک واحد اضافه شده ولی در عوض راه ۱۰ روستا هر کدام یک واحد کم خواهد شد٬ بنابراین روستای ۲ بهتر از روستای ۴ است. به همین ترتیب ثابت می‌شود که روستای ۲ از روستای ۵ نیز بهتر است.


ابزار صفحه