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

المپدیا

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

ابزار کاربر

ابزار سایت


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

گریه‌ی هپید

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

احمد ‎di‎ را برابر فاصله ‎li‎ از ‎li+1‎ در درخت تعریف کرد (‎تعداد یال‌های بینشون}. به این ترتیب ‎n1‎ عدد ‎d1dn1‎ به وجود آمدند.

احمد به هپید، عدد ‎n‎، و سپس ‎n1‎ عدد ‎d1dn1‎، و بعد از آن دو عدد ‎i‎ و ‎j‎ را می‌دهد و به او می‌گوید: ‎»‎اگر فاصله‌ی برگ‌های ‎li‎ و ‎lj‎ از درخت را به من بگویی، برایت بستنی می‌خرم‎.«‎

الکی بود‎!‎ برنامه‌ای بنویسید که عدد ‎n‎ ‎ و ‎n1 عدد ‎d1dn1‎ و دو عدد ‎i‎ و ‎j‎ را بگیرد و فاصله‌ی ‎li‎ و ‎lj‎ را در خروجی چاپ کند.

ورودی

  • در سطر اول ورودی عدد ‎n‎ آمده است.
  • در ‎n1‎ سطر بعدی، ‎n1‎ عدد ‎d1dn1‎ آمده است
  • در سطر آخر دو عدد ‎i‎ و ‎j‎ داده شده است.
  • 2n10000‎. در ‎60‎ درصد تست‌ها ‎n1000‎ است.

خروجی

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

محدودیت‌ها

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

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

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

ابزار صفحه