Страница: 1 Отображать по:
#1090
Тарифы
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Оператор сотовой связи решил разработать несколько безлимитных тарифных планов, отличающихся между собой ежемесячной абонентской платой и набором дополнительных услуг. Менеджерам по работе с клиентами удалось выяснить, сколько каждый из VIP-абонентов компании готов тратить в месяц на услуги сотовой связи. Теперь сотовая компания хочет предложить каждому из абонентов свой тарифный план, но, к сожалению, комитет по антимонопольной политике разрешает сотовой компании иметь не более K безлимитных тарифных планов.

Помогите менеджерам компании разработать эти K тарифных планов, чтобы максимизировать доходы компании.

Входные данные

В первой строке входного файла записаны два числа: количество VIP-абонентов компании N (1≤N≤100) и количество тарифных планов K (1≤K≤100).

Далее записано N целых чисел Ai — сумма, которую i-ый абонент готов тратить на связь в месяц (0≤Ai≤100000).

Выходные данные

Выведите в выходной файл K натуральных чисел — размеры абонентской платы в тарифных планах в порядке возрастания. Размер абонентской платы не должен быть меньше 1 и не может превышать 109.

Считается, что каждому абоненту будет предложен тарифный план, в котором абонентская плата максимально возможная, но не превышающая Ai, и этот абонент будет обслуживаться по этому тарифному плану. Если такого тарифного плана не окажется, абонент не будет обслуживаться компанией.

Доходы компании вычисляются как сумма абонентской платы, внесенной всеми абонентами компании.

Комментарии к примерам тестов

1. Мы не будем обслуживать абонента, который готов платить 1. Абонента, который готов платить 4, мы подключим к первому тарифному плану. Абонентов, готовых платить 5 — ко второму, готовых платить 8 и 9 — к третьему, и готового платить 80 — к четвертому. Итого суммарный доход компании составит 4 + 5*4 + 8*2 + 80 = 120

2. Подключаем каждого абонента к своему тарифу, 4-й тариф не используем. Суммарный доход — 1+2+30=33

3. Подключаем всех, кроме первого и третьего абонентов, к единственному тарифу. Суммарный доход — 4*4 = 16

4. Поскольку мы не имеем права делать тариф с нулевой абонентской платой, то 1-го и 3-го абонентов обслуживать не будем.

Примеры
Входные данные
9 4
9 1 5 5 5 5 4 8 80
Выходные данные
4 5 8 80
Входные данные
3 4
1 2 30
Выходные данные
1 2 30 31
Входные данные
6 1
0 4 3 5 13 6
Выходные данные
4
Входные данные
3 2
0 1 0
Выходные данные
1 2
#1093
Иностранные языки
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Папа Васи очень заботится об образовании сына. Особое значение он придает иностранным языкам. Недавно они приступили к изучению английского. Чтобы ускорить процесс, папа разговаривает с Васей исключительно на нем. Разумеется, это создает некоторые трудности при общении. Каждый раз, когда Вася что-нибудь скажет, папе приходится долго гадать, что именно он имел в виду.

Папа знает словарный запас сына. Считается, что Вася мог иметь в виду словарное слово P, если оно входит как подпоследовательность в слово T (то, что он сказал). Другими словами, если существует такая возрастающая последовательность индексов i1 < i2 < ... < im (где m — длина P), что P[j] = T[ij] для всех j = 1..m.

Вам дается словарный запас Васи и сказанное им слово. Для каждого словарного слова надо определить, мог ли Вася иметь его в виду.

Входные данные

В первой строке входного файла содержится единственное число K.

В следующих K строках идут слова из словаря, по одному на каждой строке. На последней (K + 2)-й строке входного файла содержится слово, сказанное Васей, длиной не более 100 000. Все слова в словаре непустые.

Все слова состоят из строчных латинских букв. Гарантируется, что суммарная длина слов из словаря не превышает 1 000 000 символов.

Выходные данные

В выходной файл выведите K строк. В i-й строке должно быть записано ‘YES’, если Вася мог иметь в виду слово номер i из словаря, и ‘NO’ в противном случае.

Примеры
Входные данные
4
hi
hello
bye
oh
ahhinellation
Выходные данные
YES
YES
NO
NO
Входные данные
5
want
drink
ink
ant
in
iwanttosleep
Выходные данные
YES
NO
NO
YES
YES
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест