Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوالات ۱۷ و ۱۸

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

سوال ۱۷

بیژن می‌خواهد در اولین سفر امسالش به کشوری برود که نقشه‌اش به شکل زیر است. اگر او بخواهد با روش مخصوص خودش کل کشور را بگردد، از حداقل چند جاده باید بیش از یک‌بار عبور کند؟

  1. 4
  2. 2
  3. 5
  4. 1
  5. 3

پاسخ

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

سوال ۱۸

بیژن در سفر دومش به کشوری می‌رود که نقشه‌اش به شکل زیر است. اگر او بخواهد این کشور را هم با روش مخصوص خودش بگردد، از حداقل چند جاده باید بیش از یک‌بار عبور کند؟

  1. 10
  2. 7
  3. 5
  4. 3
  5. 4

پاسخ

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


ابزار صفحه