|
Олимпиады прошлых лет
|
||||||||||||||||||||||||||||||||||||
|
I Всероссийская заочная олимпиада школьников по информатике, 2006/07 учебный год
Задача H. Тарифы
| Имя входного файла: | h.in |
| Имя выходного файла: | h.out |
| Максимальное время работы на одном тесте: | 1 секунда |
| Максимальный объем используемой памяти: | 64 мегабайта |
Оператор сотовой связи решил разработать несколько безлимитных тарифных планов, отличающихся между собой ежемесячной абонентской платой и набором дополнительных услуг. Менеджерам по работе с клиентами удалось выяснить, сколько каждый из VIP-абонентов компании готов тратить в месяц на услуги сотовой связи. Теперь сотовая компания хочет предложить каждому из абонентов свой тарифный план, но, к сожалению, комитет по антимонопольной политике разрешает сотовой компании иметь не более K безлимитных тарифных планов.
Помогите менеджерам компании разработать эти K тарифных планов, чтобы максимизировать доходы компании.
Формат входных данных
В первой строке входного файла записаны два числа: количество VIP-абонентов компании N (1≤N≤100) и количество тарифных планов K (1≤K≤100). Далее записано N целых чисел Ai - сумма, которую i-ый абонент готов тратить на связь в месяц (0≤Ai≤100000).
Формат выходных данных
Выведите в выходной файл K натуральных чисел - размеры абонентской платы в тарифных планах в порядке возрастания. Размер абонентской платы не должен быть меньше 1 и не может превышать 109.
Считается, что каждому абоненту будет предложен тарифный план, в котором абонентская плата максимально возможная, но не превышающая Ai, и этот абонент будет обслуживаться по этому тарифному плану. Если такого тарифного плана не окажется, абонент не будет обслуживаться компанией.
Доходы компании вычисляются как сумма абонентской платы, внесенной всеми абонентами компании.
Примеры
| h.in | h.out | Комментарии |
9 4 9 1 5 5 5 5 4 8 80 |
4 5 8 80 |
Мы не будем обслуживать абонента, который готов платить 1. Абонента, который готов платить 4, мы подключим к первому тарифному плану. Абонентов, готовых платить 5 - ко второму, готовых платить 8 и 9 - к третьему, и готового платить 80 - к четвертому. Итого суммарный доход компании составит 4 + 5*4 + 8*2 + 80 = 120 |
3 4 1 2 30 |
1 2 30 35 |
Подключаем каждого абонента к своему тарифу, 4-й тариф не используем. Суммарный доход - 1+2+30=33 |
6 1 0 4 3 5 13 6 |
4 |
Подключаем всех, кроме первого и третьего абонентов, к единственному тарифу. Суммарный доход - 4*4 = 16 |
3 2 0 1 0 |
1 2 |
Поскольку мы не имеем права делать тариф с нулевой абонентской платой, то 1-го и 3-го абонентов обслуживать не будем. |