Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


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

تونل

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

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

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

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

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

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

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

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

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

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

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

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

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

ورودی

خروجی

محدودیت‌ها

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

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

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

ابزار صفحه