المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۱۹:سوال ۳

Tree

درخت دودویی درختی است که هر گره آن حداکثر دو فرزند دارد. مثال زیر یک درخت دودویی با ‎۱۹‎ گره را نشان می‌دهد.

در این مثال ‎$r$‎ ریشه و طبق تعریف، گره‌های ‎$a$‎ و ‎$b$‎ به‌ترتیب سمت‌ چپ‌ترین و سمت‌ راست‌ترین نواده‌ی ‎$r$‎ هستند که آن‌ها را با ‎«سمت‌ چپ‌ترین»‎ و ‎«سمت‌ راست‌ترین»‎ گره در درخت نام می‌بریم.

به گره ‎$i$‎ یک عدد صحیح و مثبت به عنوان وزن آن نسبت می‌دهیم و آن‌را با ‎$w_i$‎ نشان می‌دهیم. هم‌چنین طول مسیر از گره ‎$i$‎ تا ریشه را عمق آن گره می‌گوییم و آن‌را با ‎$d_i$‎ نشان می‌دهیم. در مثال فوق عمق ‎$a$‎ و $b$‎ به‌ترتیب برابر ‎۲‎ و ‎۳‎ است.

وزن یک درخت را نیز برابر ‎$\sum_i w_i d_i$‎ تعریف می‌کنیم.

در این مسئله فرض کنید که وزن سمت‌ چپ‌ترین و سمت‌ راست‌ترین گره داده شده است و وزن بقیه‌ی گره‌ها برابر ‎۱‎ است. می‌خواهیم با دریافت تعداد کل گره‌ها، درختی را بیابیم که کم‌ترین وزن را داشته باشد.

ورودی

  • در سطر اول ورودی به‌ترتیب تعداد گره‌ها، وزن‌های سمت‌ چپ‌ترین و سمت‌ راست‌ترین گره‌ها می‌آید.
  • تعداد گره‌ها حداقل ‎$3$‎ و حداکثر برابر ‎$10^{15}$‎ است.
  • حداکثر وزن سمت‌ چپ‌ترین و سمت‌ راست‌ترین گره ‎$10^{10}$‎ است.
  • سمت‌ چپ‌ترین و سمت‌ راست‌ترین گره نمی‌توانند ریشه درخت باشند.

خروجی

در تنها سطر خروجی مقدار کم‌ترین میانگین عمق گره‌های یک درخت دودویی با ویژگی‌های داده شده را بنویسید.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
11 3 9 35


ابزار صفحه