فهرست مندرجات
Numbers
فرض کنید $f(x)$ برابر باشد با کوچک‌ترین $k$ به طوری که $\lfloor\frac{x}{2^k}\rfloor = 0$. به شما $n$ عدد $a_1$ تا $a_n$ داده شده است. شما باید $n$ عدد صحیح بزرگ‌تر از صفر $b_1$ تا $b_n$ را بیابید به طوری که :
- به ازای هر $i$ و $j$ ($i \neq j$) هیچ $k \geq 0$ای وجود نداشته باشد بهطوری‌که $\lfloor\frac{b_i}{2^k}\rfloor = b_j$.
- $\sum_{i=1}^{n}a_i \times f({b_i})$ کمینه باشد.
ورودی
- در سطر اول ورودی، عدد $1 \leq m \leq 10^5$ آمده است.
- در $m$ سطر بعد، در سطر $i$ام دو عدد $1 \leq x_i \leq 10^5$ و $1 \leq y_i \leq 10^5$ آمده است که نشان می‌دهد تمامی اعداد $a_{\sum_{j=1}^{i-1}x_j + 1}$ تا $a_{\sum_{j=1}^{i-1}x_j + x_i}$ برابر با $y_i$اند.
- $n$ برابر است با .$\sum_{i=1}^{m} x_i$
خروجی
در تنها سطر خروجی مقدار$\sum_{i=1}^{n}a_i \times f({b_i})$ را بنویسید.
محدودیت‌ها
- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
ورودی و خروجی نمونه
| ورودی نمونه | خروجی نمونه |
|---|---|
| 1 3 1 1 1 2 1 3 | 15 |
پاسخ
می‌خواهیم اعداد $b_1$ تا $b_n$ را طوری به‌دست بیاوریم که شرایط سوال را برقرار کند. فرض کنید $c_1$ تا $c_n$ به ترتیب رشته‌های از صفر و یک باشند و $c_i$ برابر باشد با نمایش $b_i$ در مبنای دو که یک اول آن حذف شده است. در این صورت مسئله به سوال معروف زیر تبدیل می شود:
می خواهیم $n$ رشته $c_1$ تا $c_n$ را طوری پیدا کنیم که هیچ رشته‌ای رشته دیگر نباشد و مجموع ضرب $a_i$ در طول $c_i$ کمینه شود.
این مسئله با استفاده از الگوریتم huffman coding در زمان ${\cal O} (n log(n))$ قابل حل است و روش آن به صورت زیر است:
- یک Multiset از $a_i$ ها درست کن.
- مقدار $x$ را برابر با صفر قرار بده.
- تا زمانی که تعداد اعداد multiset ای یک بیش‌تر است کار زیر را انجام بده:
- $a$ را برابر کم‌ترین عدد multiset قرار بده و آن را از multiset حذف کن.
- $b$ را برابر کم‌ترین عدد multiset قرار بده و آن را از multiset حذف کن.
- مقدار $x$ را با $a+b$ جمع کن و $a+b$ را در multiset قرار بده.
مقدار $x$ که از الگوریتم بالا به‌دست می‌آید، همان جوابیست که باید در خروجی چاپ شود. مقدار $n$ زیاد است و انجام تمامی عملیات بالا در زمان مناسب امکان‌پذیر نیست. فرض کنید در یک مرحله از کار کم‌ترین عدد multiset $a$ باشد و تعداد $a$های multiset برابر با $c$ باشد، در این صورت ما یک کار ثابت را $\frac{c}{2}$ بار انجام می‌دهیم، که با پیاده‌سازی درست می‌توان هر کدام از این کارها را یک بار انجام داد. در این صورت پیچیدگی زمانی برنامه‌ما برابر خواهد بود با ${\cal O}(m \times log(m))$ که در زمان مناسب پاسخ سوال را به‌دست می‌آورد.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
