المپدیا

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

ابزار کاربر

ابزار سایت


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

مشاوران سلطان

سلطان شهر مالیپولیا تصمیم گرفته که بخشی از غنایم و هدایایی رو که تازگی به‌دست آورده، بین $m$ مشاور دلبندش تقسیم کنه. این اموال شامل $n$‌ تا کیسه زر میشه که روی یک میز در یک خط چیده شده‌اند. سلطان می‌خواد تعدادی (یعنی حداقل یکی) از کیسه‌های سمت چپ صف رو به مشاور شماره‌ی یک بده که اتفاقا خیلی هم باهاش حال می‌کنه(و احتمالا واسه همین شمارش یکه). بعد تعدادی از کیسه‌های باقی‌مانده رو که حالا در سمت چپ صف کیسه‌ها قرار دارن رو به مشاور شماره‌ی دو بده. البته این کار رو تا آخرین مشاور ادامه میده که باقی‌مانده‌ی کیسه‌ها (باز هم حداقل یک کیسه) رو به چنگ بیاره.

درایت شاهانه حکم می‌کنه که برای حفظ تاج و ملک، هیچ یک از مشاوران قدرت زیادی پیدا نکنه، لذا سلطان می‌خواد که بیش‌ترین سهم یک مشاور از این هدایا رو کمینه کنه.

البته اشاره شد که مشاور شماره‌ی یک محبوب‌ترین مشاور نزد سلطان است و پس از او مشاور شماره‌ی دو و … پس سلطان می‌خواد بدون این‌که به صلاح مملکت (ارضای شرط فوق‌الذکر) لطمه‌ای بخوره، کاری کنه بیش‌ترین سهم به مشاور اعظم برسه و بدون لطمه زدن به این علاقه بیش‌ترین سهم به مشاور شماره‌ی دو برسه و …(دنباله‌ی سهم وزرا به ترتیب محبوبیت از لحاظ لغت‌نامه‌ای بیشینه باشه).

به او کمک کنید که تا حد امکان به خواسته‌هاش برسه و سهم هر یک از مشاوران رو معلوم کنید.

ورودی

در سطر اول فایل ورودی به ترتیب $n$ و $m$ و در سطر دوم $n$ عدد آمده که تعداد سکه‌های درون کیسه‌ها را از چپ به راست نشان می‌دهد. هر یک از این اعداد در بازه‌ی $[1...10^7]$ می‌باشد و $1\leq m \leq n \leq 10^5$.

خروجی

در سطر اول فایل خروجی، بیش‌ترین سهم یک مشاور را بنویسید و در $m$‌ سطر بعدی تعداد کیسه‌هایی را که هر یک از مشاوران به‌دست خواهد آورد، بنویسید (بالطبع به ترتیب و با شروع از مشاور اعظم).

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

ورودي نمونه خروجي نمونه
5 3
50 50 50 50 200
200
3
1
1

ابزار صفحه