المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۸:تئوری:سوال ۲۰

سرویس‌دهی

  1. روی بعضی از رئوس گراف ساده‌ی ‎$G$‎ فروشگاه‌هایی قرار دارد. در هر فروشگاه تعدادی بستنی وجود دارد. تعداد بستنی‌ها در فروشگاه‌های مختلف لزوماً یکی نیست. تعدادی کودک نیز روی تعدادی از رئوس (نه لزوماً متمایز) گراف قرار دارند. می‌خواهیم کودکان را روی رئوس گراف طوری حرکت دهیم که به هر کودک یک بستنی برسد (می‌دانیم این‌کار همواره امکان‌پذیر است و لزومی ندارد همه‌ی بستنی‌ها تمام شوند). با دانستن این نکته که هر کودک هر یال را در یک دقیقه طی می‌کند، یک الگوریتم چندجمله‌ای ارائه کنید تا کودکان را طوری حرکت بدهد که آخرین کودکی که به بستنی می‌رسد تا حد ممکن در زمان کوتاه‌تری برسد.
  2. اگر در حالت قبل فروشگاه‌ها هم بتوانند حرکت کنند (مانند چرخ دستی سیّار‎!‎) و سرعت‌شان مانند کودکان باشد، نشان دهید که جواب مسئله کم‌تر از نصف نخواهد شد.

ابزار صفحه