Задание 26 ЕГЭ: сортировка и отбор: скидки

Скидки, архив и закупка: сортировка и отбор. Тема номера — обработка данных и моделирование. Ниже — пример с ответом и решением; кнопкой под ним можно решить такую же задачу с другими числами, ответ проверится сразу.

Пример

Задание выполняется с использованием прилагаемого файла.

Предприятие производит оптовую закупку изделий A и Z, на которую выделена определённая сумма денег. У поставщика есть в наличии партии этих изделий различных модификаций по различной цене. На выделенные деньги необходимо приобрести как можно больше изделий Z независимо от модификации. Закупать можно любую часть каждой партии. Если у поставщика закончатся изделия Z, то на оставшиеся деньги необходимо приобрести как можно больше изделий A. Известна выделенная для закупки сумма, а также количество и цена различных модификаций данных изделий у поставщика.

Необходимо определить, сколько будет закуплено изделий A и какая сумма останется неиспользованной.

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

Первая строка входного файла 26.txt содержит два целых числа: N — общее количество партий изделий у поставщика и M — сумма выделенных на закупку денег (в рублях). Каждая из следующих N строк содержит два целых числа (цена одного изделия в рублях и количество изделий в партии) и одну букву (латинская заглавная буква A или Z — тип изделия). Все данные в строках входного файла разделены одним пробелом.

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

Два целых неотрицательных числа: сначала количество закупленных изделий типа A, затем оставшаяся неиспользованной сумма денег.

Типовой пример организации данных во входном файле

4 1000
30 8 A
50 12 Z
40 14 A
30 60 A

В данном случае сначала нужно купить изделия Z: 12 изделий по 50 рублей, на это будет потрачено 600 рублей. На оставшиеся 400 рублей можно купить 13 изделий A по 30 рублей и потратить 390 рублей; останется 10 рублей. Ответ для примера: 13 10.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Запишите два числа через пробел.

Скачать файл к примеру

Решение

Чтобы купить как можно больше изделий, выгодно брать самые дешёвые: сортируем партии по цене и из каждой берём столько изделий, сколько позволяют деньги (но не больше, чем есть в партии). Сначала так скупаем все изделия Z (денег на них хватает), затем тем же способом — изделия A.

Ответ: 48945 377.

f = open("26.txt")
n, money = map(int, f.readline().split())
z, a = [], []
for _ in range(n):
    price, cnt, kind = f.readline().split()
    (z if kind == "Z" else a).append((int(price), int(cnt)))

for price, cnt in sorted(z):              # сначала Z, от дешёвых к дорогим
    money -= min(cnt, money // price) * price
bought = 0
for price, cnt in sorted(a):              # затем A
    take = min(cnt, money // price)
    bought += take
    money -= take * price
print(bought, money)

Решить такую задачу — новый вариант с проверкой