کپل: ﺩﻡﺑﺎﺭﯾﯿﯿﮏ! ﺩﻡﺑﺎﺭﯾﮏ ﺟﻮﻧﻢ! ﺑﯿﺎ . . . ﺑﯿﺎﺍﺍﺍﺍ . . .
ﺩﻡﺑﺎﺭﯾﮏ: ﻫﺎﻥ. ﭼــــﯿﻪ؟
ﮐﭙﻞ: ﺑﺒﯿﯿﯿﻦ. ﺍﻭﻥ n تا انبار ﮔﺮﺩﻭ ﺑﻮﺩ ﮐﻪ ﭘﯿﺪﺍ ﮐﺮﺩﯾﻢ.
ﺩﻡﺑﺎﺭﯾﮏ: ﺧﻮﺏ؟
ﮐﭙﻞ: ﻣﻦ ﺑﯿﻨﺸﻮﻥ ﯾﻪ ﺳﺮﯼ ﺗﻮﻧﻞ ﮐﺸﯿﺪﻡ. ﺍﻻﻥ ﻣﯽﺷﻪ ﺑﺎ ﺍﯾﻦ ﺗﻮﻧﻞﻫﺎ ﺍﺯ ﻫﺮ ﺍﻧﺒﺎﺭ ﺑﻪ ﻫﺮ ﺍﻧﺒﺎﺭ ﺩﯾﮕﻪﺍﯼ ﺭﻓﺖ.
ﺩﻡﺑﺎﺭﯾﮏ: ﺭﺍﺳﺖ ﻣﯽﮔﯽ ﮐﭙﻞ ﺟﻮﻧﻢ؟ ﺗﻮ ﮐﻪ ﺧﯿﻠﯽ ﺍﻫﻞ ﺗﻮﻧﻞ ﮐﺸﯿﺪﻥ ﻭ ﺍﯾﻦ ﺟﻮﺭ ﺯﺣﻤﺖﻫﺎ ﻧﺒﻮﺩﯼ.
ﮐﭙﻞ: ﺧﻮﺏ، ﻣﻦ ﺗﻮﻧﺴﺘﻢ ﻓﻘﻂ ﺑﺎ n−1 ﺗﻮﻧﻞ ﺍﯾﻦ ﮐﺎﺭ ﺭﻭ ﺍﻧﺠﺎﻡ ﺑﺪﻡ.
ﺩﻡﺑﺎﺭﯾﮏ: ﮐﭙﻞﺟﻮﻧﻢ، ﻣﯽﺷﻪ ﺑﮕﯽ ﭼﻪ ﺍﻧﺒﺎﺭﻫﺎﯾﯽ ﺭﻭ ﻣﺴﺘﻘﯿﻤﺎً ﺑﺎ ﺗﻮﻧﻞ ﺑﻪ ﻫﻢ ﻭﺻﻞ ﮐﺮﺩﯼ؟
ﺁﻗﺎ ﻣﻌﻠﻢ: ﮐﭙﻞ! ﭼﻪ ﻗﺪﺭ ﺣﺮﻑ ﻣﯽﺯﻧﯽ؟!
ﮐﭙﻞ: ﻫﯿﺴﺲ. ﻣﻦ ﻧﻤﯽﺗﻮﻧﻢ ﺧﯿﻠﯽ ﺣﺮﻑ ﺑﺰﻧﻢ. ﻭﻟﯽ ﺍﮔﺮ ﺑﻪ ﺍﯾﻦ ﺷﮑﻞ سوال ﮐﻨﯽ، ﻣﯽﺗﻮﻧﻢ ﺟﻮﺍﺑﺖ ﺭﻭ ﺑﺪﻡ: «ﺗﻮ ﭼﻨﺪﺗﺎ ﺍﻧﺒﺎﺭ ﺭﺍ ﺑﮕﻮ، ﻣﻦ ﺗﻌﺪﺍﺩ ﺗﻮﻧﻞﻫﺎﯾﯽ ﺭﻭ ﻣﯽﻧﻮﯾﺴﻢ ﮐﻪ ﻫﺮ ﺩﻭ ﺳﺮﺷﻮﻥ ﺑﻪ ﺍﻧﺒﺎﺭﻫﺎﯾﯽ ﺧﺘﻢ ﻣﯽﺷﻪ ﮐﻪ ﺗﻮ ﮔﻔﺘﯽ.»
ﻣﯽﺩﺍﻧﯿﻢ ﺩﻭ سر ﻫﺮ ﺗﻮﻧﻞ ﺑﻪ ﯾﮏ ﺍﻧﺒﺎﺭ ﺧﺘﻢ ﻣﯽﺷﻮﺩ ﻭ ﺗﻮﻧﻞﻫﺎ ﺑﺎ ﻫﻢ ﺗﻘﺎﻃﻊ ﻧﺪﺍﺭﻧﺪ ﻣﮕﺮ ﺩﺭ ﺳﺮﻫﺎﯾﺸﺎﻥ. ﺑﻪ ﺩﻡﺑﺎﺭﯾﮏ ﮐﻤﮏ ﮐﻨﯿﺪ ﺗﺎ ﺑﺎ ﺗﻌﺪﺍﺩ ﮐﻤﯽ سوال بفهمد n−1 تونل کپل چه انبارهایی را مستقیما به هم وصل کردهاند. ﻫﻤﭽﻨﯿﻦ ﻣﯽﺩﺍﻧﯿﻢ ﮐﭙﻞ ﺣﻮﺻﻠﻪﯼ ﭘﺎﺳﺦ ﺩﺍﺩﻥ ﺑﻪ ﺑﯿﺶ ﺍﺯ ۲۰۰۰۰ سوال را ندارد.
ﺑﺮﻧﺎﻣﻪﺍﯼ ﺑﻨﻮﯾﺴﯿﺪ ﮐﻪ:
تعداد انبارها (n) را از کتابخانه بخواند. به کمک کتابخانه سوالات مورد نظر را از کپل بپرسد. به کتابخانه گزارش دهد چه انبارهایی با تونل مستقیما به هم راه دارند.
ورودی نمونه | خروجی نمونه |
---|---|