المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲۷

یک گراف کامل $11$ رأسی با رأس‌های ۱، ۲، $\ldots$ و ۱۰ داریم. روی یال بین رأس‌های $i$ و $j$ مقدار باقی‌مانده‌ی $i+j$ در تقسیم بر $11$ را نوشته‌ایم. می‌خواهیم یک زیردرخت فراگیر از این گراف انتخاب کنیم، طوری که مجموع اعداد یال‌های آن کمینه باشد. این مقدار کمینه چیست؟

  1. ۱۶
  2. ۱۰
  3. ۱۱
  4. ۶
  5. ۵

پاسخ

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

تعداد یال‌های درخت برابر ۱۰ است. گراف پنج یال با عدد ۰ دارد. پس پاسخ نمی‌تواند از $5 \times 0 + (10-5) \times 1 = 5$ کم‌تر باشد.

حال اگر یال‌های زیر را به عنوان یال‌های درخت در نظر بگیریم، مجموع اعداد یال‌های درخت برابر ۵ خواهد شد: $$1 \leftrightarrow 10 \qquad 2 \leftrightarrow 9 \qquad 3 \leftrightarrow 8 \qquad 4 \leftrightarrow 7 \qquad 5 \leftrightarrow 6 \qquad $$ $$0 \leftrightarrow 1 \qquad 2 \leftrightarrow 10 \qquad 3 \leftrightarrow 9 \qquad 4 \leftrightarrow 8 \qquad 5 \leftrightarrow 7 \qquad$$ پس پاسخ برابر ۵ است.


ابزار صفحه