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

1. $4$
2. $5$
3. $6$
4. $7$
5. $3$

• سوال بعد