المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی تابستان:دوره‌ی ۱۷:عملی:سوال ۶

گریه‌ی هپید

هپیدِ ما باز شروع کرده به گریه کردن‎!‎ احمد هم دلش برای او سوخت و یک مساله طرح کرد تا برای مدتی هپید را سرگرم کند. او یک درخت دودویی‎ (یعنی هر راسی یا دو تا بچه دارد، یا هیچی) ‎$2n-1$‎ راسیِ ریشه‌دار در نظر گرفت. سپس از ریشه درخت یک ‎DFS‎ زد و هرگاه که وارد یک برگ می‌شد، شماره‌ی آن برگ را یادداشت می‌کرد. به این ترتیب پس از پایان یافتن DFS‎، او ‎$n$‎ عدد متفاوتِ ‎$l_1 \ldots l_n$‎ را (به تعداد برگ‌ها) یادداشت کرده بود.

احمد ‎$d_i$‎ را برابر فاصله ‎$l_i$‎ از ‎$l_{i+1}$‎ در درخت تعریف کرد (‎تعداد یال‌های بینشون}. به این ترتیب ‎$n-1$‎ عدد ‎$d_1 \ldots d_{n-1}$‎ به وجود آمدند.

احمد به هپید، عدد ‎$n$‎، و سپس ‎$n-1$‎ عدد ‎$d_1 \ldots d_{n-1}$‎، و بعد از آن دو عدد ‎$i$‎ و ‎$j$‎ را می‌دهد و به او می‌گوید: ‎»‎اگر فاصله‌ی برگ‌های ‎$l_i$‎ و ‎$l_j$‎ از درخت را به من بگویی، برایت بستنی می‌خرم‎.«‎

الکی بود‎!‎ برنامه‌ای بنویسید که عدد ‎$n$‎ ‎ و ‎$n-1$ عدد ‎$d_1 \ldots d_{n-1}$‎ و دو عدد ‎$i$‎ و ‎$j$‎ را بگیرد و فاصله‌ی ‎$l_i$‎ و ‎$l_j$‎ را در خروجی چاپ کند.

ورودی

  • در سطر اول ورودی عدد ‎$n$‎ آمده است.
  • در ‎$n-1$‎ سطر بعدی، ‎$n-1$‎ عدد ‎$d_1 \ldots d_{n-1}$‎ آمده است
  • در سطر آخر دو عدد ‎$i$‎ و ‎$j$‎ داده شده است.
  • $2 \leq n \leq 10 000$‎. در ‎$60$‎ درصد تست‌ها ‎$n \leq 1000$‎ است.

خروجی

در تنها سطر خروجی، فاصله‌ی ‎$l_i$‎ و ‎$l_j$‎ را چاپ کنید.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
3
3
2
1 3
3
3

ابزار صفحه