Решение олимпиадной задачи "Тарифы"

@TheBlackBear · Регистрация: 18.04.2017

Студворк — интернет-сервис помощи студентам

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

Формат входных данных
В первой строке входного файла записаны два числа: количество VIP-абонентов компании N (1≤N≤100) и количество тарифных планов K (1≤K≤100). Далее записано N целых чисел A_i — сумма, которую i-ый абонент готов тратить на связь в месяц (0≤A_i≤100000).

Формат выходных данных
Выведите в выходной файл K натуральных чисел — размеры абонентской платы в тарифных планах в порядке возрастания. Размер абонентской платы не должен быть меньше 1 и не может превышать 10^9. Считается, что каждому абоненту будет предложен тарифный план, в котором абонентская плата максимально возможная, но не превышающая A_i, и этот абонент будет обслуживаться по этому тарифному плану. Если такого тарифного плана не окажется, абонент не будет обслуживаться компанией.
Доходы компании вычисляются как сумма абонентской платы, внесенной всеми абонентами компании.

Идея решия
Допустим, дан список A: 9 1 5 5 5 5 4 8 80. N = 9, K = 4.
Мы будем формировать новый двумерный список, где j (столбцы) - это количество абонентов, а i (строки) - количество тарифов, т.е. в первой списке мы будем записывать прибыль компании для 1 тарифа. Сначала идёт прибыль от 1 пользователя, потом от 2 пользователей, потом для от пользователей и т.д. до N-ого пользователя. Для этого мы отсортируем исходный список A.
Нужно ещё учитывать, что тариф меньше той суммы, которую может заплатить пользователь тоже подходит.
Например, есть четыре пользователя 1, 4, 5, 5, 6 и 2 тарифа. Тогда оптимально будет сделать тарифы по 5 и по 4, тогда общая прибыль будет 19. Если мы возьмем по 5 и по 6, тогда прибыль будет 16.
В случае работы с 1 тарифом получается всё, но как сделать так, чтобы программа решала задание для K тарифов?
Вот код

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
f = open('tests/H/001.dat').read().split('\n')[:-1]
answer = list(map(int, open('tests/H/001.ans').read().split()))
n = int(f[0].split()[0])
k = int(f[0].split()[1])
A = sorted(list(map(int, f[1].split()))) # Сортируем исходный список
Ans = [-1] * k  # Формируем двумерный список, который будем заполнять
for i in range(k):
    Ans[i] = [-1] * n
Ans[0][0] = A[0]
for i in range(k):
    for j in range(n):  # A[j]
        # Вот здесь необходима помощь
        pass

Новые блоги и статьи Все статьи Все блоги /
Перемещение выделенных строк ТЧ из одного документа в другой Maks 30.03.2026 Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .	Functional First Web Framework Suave DevAlt 30.03.2026 Sauve. IO Апнулись до NET10. Из зависимостей один пакет, работает одинаково хорошо как в режиме проекта так и в интерактивном режиме. из сложностей - чисто функциональный подход. Решил. . .	Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .	Настройка движения справочника по регистру сведений Maks 29.03.2026 Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .
Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .	Автозаполнение реквизитов при создании документа Maks 26.03.2026 Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .	Команды формы и диалоговое окно Maks 26.03.2026 1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .