+ محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- آرایه $a$، شامل اعداد $a_1, a_2, ..., a_n\ $ روی تخته نوشته شده است. در هر گام می‌توانیم یکی از دو عملیات زیر را انجام دهیم. + یک عدد $x$ از روی تخته در نظر بگیریم و **تمام** اعداد $x$ روی تخته را با $\left \lfloor{ \frac {x}{2}}\right \rfloor$ جایگزین کنیم. (یعنی به جای هر $x$ روی تخته، $\left \lfloor{ \frac {x}{2}}\right \rfloor$ قرار می‌دهیم.‌) + یک عدد $x$ از روی تخته در نظر بگیریم و **تمام** اعداد $x$ روی تخته را پاک کنیم. از عملیات نوع دوم **حداکثر $k$ بار** می‌توانیم استفاده کنیم. کم‌ترین تعداد مرحله برای این که در انتها کلا عددی روی تخته باقی نماند، یا تمامی اعداد باقی مانده برابر با $0$ باشد، چه‌قدر است؟ # ورودی ورودی شامل دو خط است که خط اول آن شامل دو عدد $n, k$ است. در خط دوم $n$ عدد $a_1, a_2, .., a_n\ $ می‌آید که اعداد اولیه روی تخته را مشخص می‌کند. $$1 \le n \le 100\ 000$$ $$0 \le k \le 10$$ $$1 \le a_i \le 10^9$$ # خروجی در تنها خط خروجی کمترین مراحل مورد نیاز برای رسیدن به شرایط مطلوب را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 5 2 1 2 3 4 5 ``` ## خروجی نمونه ۱ ``` 5 ``` یکی از روش‌ها این است که ابتدا اعداد $5$ و $4$ را با عملیات نوع اول به $2$ تبدیل کنیم. سپس عدد $3$ را به $1$ تبدیل کنیم، اعداد روی تخته $<1, 2, 1, 2, 2>$ خواهند بود. در نهایت عدد $1, 2$ را پاک کنیم و دنباله تهی می‌شود. در مجموع $5$ عملیات انجام شده است. ## ورودی نمونه ۲ ``` 4 1 1 1 2 3 ``` ## خروجی نمونه ۲ ``` 3 ``` در یکی از روش‌های بهینه ابتدا عدد $3$ را حذف می‌کنیم،‌ سپس $2$ را با عملیات اول به $1$ تبدیل می‌کنیم و نهایتا همه اعداد $1$ را با عملیات اول به صفر تبدیل می‌کنیم. ## ورودی نمونه ۳ ``` 10 3 10 20 30 40 50 60 70 80 90 100 ``` ## خروجی نمونه ۳ ``` 16 ``` ------------- <details class="blue"> <summary> راهنمایی ۱ </summary> در این بخش فرض کنید $k=0$ است. نمایش باینری اعداد را در نظر بگیرید، با عملیات اول آخرین رقم نمایش دودویی حذف می‌شود. اکنون [درخت ترای](https://fa.wikipedia.org/wiki/%D8%AF%D8%B1%D8%AE%D8%AA_%D9%BE%DB%8C%D8%B4%D9%88%D9%86%D8%AF%DB%8C) اعداد آرایه را در نظر بگیرید، هدف این است که با حذف آخرین رقم همه اعداد را به صفر تبدیل کنیم که یعنی درخت ترای اعدادمان را تک راسی کنیم، پس می‌توان دریافت که به حداقل به اندازه تعداد راس‌های ترای منهای یک، عملیات نیاز داریم، چون در هر عملیات حداکثر یک راس حذف می‌شود. همین‌طور می‌توان روشی ارائه داد تا با دقیقا همین تعداد عملیات، همه اعداد را به صفر تبدیل کنیم. پس مساله در حالت $k=0$، حل شد. سعی کنید با همین ایده مساله را برای $k>0$ حل کنید. </details> <details class="blue"> <summary> راهنمایی ۲ </summary> در این بخش به بیان ایده حالت کلی مساله می‌پردازیم. با استفاده از برنامه‌نویسی پویا روی درخت ترای مساله را حل می‌کنیم. فرض کنید بخواهیم برای هر راس در درخت ترای مثل $v$ (که متناظر با یک عدد است) ، مساله را برای اعداد درون زیردرخت آن راس حل کنیم، یعنی بخواهیم با $j$ عملیات حذف $1 \le j \le k$ ، اعداد درون زیردرخت $v$ را به $v$ تبدیل کنیم. برای محاسبه این مقادیر به این نتیجه می‌رسیم که لازم است روی این که آیا همه اعداد زیردرخت حذف شده‌اند یا خیر حالت‌بندی کنیم در نتیجه لازم است آرایه $dp$ای‌داشته باشیم که $$dp[v][j][t]$$ کمترین تعداد عملیات‌های نوع اول لازم برای اینکه اعداد درون زیردرخت $v$ را به $v$ تبدیل کنیم و حداکثر $j$ بار ار عملیات حذف استفاده کنیم. هم‌چنین اگر $t=0$ تضمین می‌شود که همه اعداد درون این زیردرخت حذف شده‌اند و هیچ عددی باقی نمانده است و درحالت $t=1$، ممکن است تعدادی از اعداد (طبیعتا همگی $v$ هستند)، باقی بمانند. </details> <details class="blue"> <summary> راه حل </summary> در این بخش شیوه پرکردن آرایه $dp$ را شرح می‌دهیم. فرض کنید بخواهیم $dp[v][j][t]$ را محاسبه کنیم. فرزند چپ $v$ را $v_l$ و فرزند راست آن‌ را $v_r$ بنامید. حالت بندی کنید که چه تعداد عملیات حذف را در زیردرخت $v_l$ و چه تعداد را در زیر درخت $v_r$ استفاده کنیم، هم‌چنین با حالت بندی روی اینکه در هر کدام از زیردرخت‌ها کل اعداد حذف شده‌اند یا خیر، می‌توان دریافت که یک عملیات اضافه برای تبدیل $v_l$ و یا $v_r$ به $v$ نیاز داریم یا خیر. هم‌چنین یک حالت این است که روی $v$ عملیات حذف را انجام دهیم که نباید آن را فراموش کنید. در نهایت پیچیدگی نهایی حل این مساله $\theta (n k^2 \log_2 A_i)$ خواهد بود. </details>