المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۱۶:سوال ۲۰

تونل

کپل: ﺩﻡﺑﺎﺭﯾﯿﯿﮏ! ﺩﻡﺑﺎﺭﯾﮏ ﺟﻮﻧﻢ! ﺑﯿﺎ . . . ﺑﯿﺎﺍﺍﺍﺍ . . .

ﺩﻡﺑﺎﺭﯾﮏ: ﻫﺎﻥ. ﭼــــﯿﻪ؟

ﮐﭙﻞ: ﺑﺒﯿﯿﯿﻦ. ﺍﻭﻥ $n$ تا انبار ﮔﺮﺩﻭ ﺑﻮﺩ ﮐﻪ ﭘﯿﺪﺍ ﮐﺮﺩﯾﻢ.

ﺩﻡﺑﺎﺭﯾﮏ: ﺧﻮﺏ؟

ﮐﭙﻞ: ﻣﻦ ﺑﯿﻨﺸﻮﻥ ﯾﻪ ﺳﺮﯼ ﺗﻮﻧﻞ ﮐﺸﯿﺪﻡ. ﺍﻻﻥ ﻣﯽﺷﻪ ﺑﺎ ﺍﯾﻦ ﺗﻮﻧﻞﻫﺎ ﺍﺯ ﻫﺮ ﺍﻧﺒﺎﺭ ﺑﻪ ﻫﺮ ﺍﻧﺒﺎﺭ ﺩﯾﮕﻪﺍﯼ ﺭﻓﺖ.

ﺩﻡﺑﺎﺭﯾﮏ: ﺭﺍﺳﺖ ﻣﯽﮔﯽ ﮐﭙﻞ ﺟﻮﻧﻢ؟ ﺗﻮ ﮐﻪ ﺧﯿﻠﯽ ﺍﻫﻞ ﺗﻮﻧﻞ ﮐﺸﯿﺪﻥ ﻭ ﺍﯾﻦ ﺟﻮﺭ ﺯﺣﻤﺖﻫﺎ ﻧﺒﻮﺩﯼ.

ﮐﭙﻞ: ﺧﻮﺏ، ﻣﻦ ﺗﻮﻧﺴﺘﻢ ﻓﻘﻂ ﺑﺎ $n-1$ ﺗﻮﻧﻞ ﺍﯾﻦ ﮐﺎﺭ ﺭﻭ ﺍﻧﺠﺎﻡ ﺑﺪﻡ.

ﺩﻡﺑﺎﺭﯾﮏ: ﮐﭙﻞﺟﻮﻧﻢ، ﻣﯽﺷﻪ ﺑﮕﯽ ﭼﻪ ﺍﻧﺒﺎﺭﻫﺎﯾﯽ ﺭﻭ ﻣﺴﺘﻘﯿﻤﺎً ﺑﺎ ﺗﻮﻧﻞ ﺑﻪ ﻫﻢ ﻭﺻﻞ ﮐﺮﺩﯼ؟

ﺁﻗﺎ ﻣﻌﻠﻢ: ﮐﭙﻞ! ﭼﻪ ﻗﺪﺭ ﺣﺮﻑ ﻣﯽﺯﻧﯽ؟!

ﮐﭙﻞ: ﻫﯿﺴﺲ. ﻣﻦ ﻧﻤﯽﺗﻮﻧﻢ ﺧﯿﻠﯽ ﺣﺮﻑ ﺑﺰﻧﻢ. ﻭﻟﯽ ﺍﮔﺮ ﺑﻪ ﺍﯾﻦ ﺷﮑﻞ سوال ﮐﻨﯽ، ﻣﯽﺗﻮﻧﻢ ﺟﻮﺍﺑﺖ ﺭﻭ ﺑﺪﻡ: «ﺗﻮ ﭼﻨﺪﺗﺎ ﺍﻧﺒﺎﺭ ﺭﺍ ﺑﮕﻮ، ﻣﻦ ﺗﻌﺪﺍﺩ ﺗﻮﻧﻞﻫﺎﯾﯽ ﺭﻭ ﻣﯽﻧﻮﯾﺴﻢ ﮐﻪ ﻫﺮ ﺩﻭ ﺳﺮﺷﻮﻥ ﺑﻪ ﺍﻧﺒﺎﺭﻫﺎﯾﯽ ﺧﺘﻢ ﻣﯽﺷﻪ ﮐﻪ ﺗﻮ ﮔﻔﺘﯽ.»

ﻣ‰ﯽﺩﺍﻧ‰ﯿ‰ﻢ ﺩﻭ سر ﻫ‰ﺮ ﺗ‰ﻮﻧ‰ﻞ ﺑ‰ﻪ ﯾ‰ﮏ ﺍﻧ‰ﺒ‰ﺎﺭ ﺧ‰ﺘ‰ﻢ ﻣ‰ﯽﺷ‰ﻮﺩ ﻭ ﺗ‰ﻮﻧ‰ﻞﻫ‰ﺎ ﺑ‰ﺎ ﻫ‰ﻢ ﺗ‰ﻘ‰ﺎﻃ‰ﻊ ﻧ‰ﺪﺍﺭﻧ‰ﺪ ﻣ‰ﮕ‰ﺮ ﺩﺭ ﺳﺮﻫﺎﯾﺸﺎﻥ. ﺑﻪ ﺩﻡﺑﺎﺭﯾﮏ ﮐﻤﮏ ﮐﻨﯿﺪ ﺗﺎ ﺑﺎ ﺗﻌﺪﺍﺩ ﮐﻤﯽ سوال بفهمد $n-1$ تونل کپل چه انبارهایی را مستقیما به هم وصل کرده‌اند. ﻫﻤﭽﻨﯿﻦ ﻣﯽﺩﺍﻧﯿﻢ ﮐﭙﻞ ﺣﻮﺻﻠﻪﯼ ﭘﺎﺳﺦ ﺩﺍﺩﻥ ﺑﻪ ﺑﯿﺶ ﺍﺯ ۲۰۰۰۰ سوال را ندارد.

ﺑﺮﻧﺎﻣﻪﺍﯼ ﺑﻨﻮﯾﺴﯿﺪ ﮐﻪ:

تعداد انبارها ($n$) را از کتاب‌خانه بخواند. به کمک کتاب‌خانه سوالات مورد نظر را از کپل بپرسد. به کتاب‌خانه گزارش دهد چه انبارهایی با تونل مستقیما به هم راه دارند.

ورودی

خروجی

محدودیت‌ها

  • محدودیت زمان: ۵ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه

ابزار صفحه