المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۳۱

می‌خواهیم به هر کدام از نقطه‌های توپر در شکل مقابل٬ یکی از اعداد ۱ تا $k$ را تخصیص دهیم به طوری که هر مسیری که دو نقطه با شماره‌های یکسان $i$ را به هم وصل می‌کند٬ از حداقل یک نقطه با شماره‌ی بیش‌تر از $i$ عبور کند. کم‌ترین مقدار $k$ چه قدر است؟

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

پاسخ

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

بهترین حالت ممکن به شکل زیر می‌باشد:


ابزار صفحه