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

@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 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать контроль заполнения реквизита табличной части. . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/	Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .	Вывод данных в справочнике через динамический список Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .
Функция заполнения текстового поля в реквизите формы документа Maks 01.04.2026 Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .	К слову об оптимизации kumehtar 01.04.2026 Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .	Идея фильтра интернета (сервер = слой+фильтр). Hrethgir 31.03.2026 Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .	Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем

Опции темы