Предприятие производит оптовую закупку некоторых изделий A и B, на которую выделена определённая сумма денег. У поставщика есть в наличии партии этих изделий различных модификаций по различной цене. На выделенные деньги необходимо приобрести как можно больше изделий A независимо от модификации. Если у поставщика закончатся изделия A, то на оставшиеся деньги необходимо приобрести как можно больше изделий B. Известны выделенная для закупки сумма, а также количество и цена различных модификаций данных изделий у поставщика. Необходимо определить, сколько будет закуплено изделий А и B и какая сумма останется неиспользованной.
Входные данные.
Первая строка входного файла 26_6.txt содержит два целых числа: N — общее количество партий изделий у поставщика и M — сумма выделенных на закупку денег (в рублях). Каждая из следующих N строк описывает одну партию и содержит два целых числа (цена одного изделия в рублях и количество изделий в партии) и один символ (латинская буква A или B), определяющий тип изделия. Все данные в строках входного файла отделены одним пробелом.
В ответе запишите два целых числа без пробела: сначала количество закупленных изделий обоих типов, затем оставшуюся неиспользованной сумму денег.
Пример входного файла:
4 1000
30 8 A
50 12 B
40 14 A
30 60 B
В данном случае сначала нужно купить изделия A: 8 изделий по 30 рублей и 14 изделий по 40 рублей. На это будет потрачено 800 рублей. На оставшиеся 200 рублей можно купить 6 изделий B по 30 рублей. Таким образом, всего будет куплено 28 изделий типа А и В и останется 20 рублей. В ответе надо записать числа 28 и 20.
Решение с помощью электронных таблиц
Размер выделенных на закупку денег — 4200000
1. Сначала переносим информацию из текстового файла в Exel, а затем сортируем столбец С от А до Я, после сортируем столбец А по возрастанию. Таким образом получится, что в файле сначала идут изделия типа А от самых дешевых до самых дорогих, затем изделия В от самых дешевых до самых дорогих.
2. Далее, в ячейке D1 считаем сколько денег максимум будет потрчено на данное изделие, то есть умножаем A1 на В1.
3. Далее, начиная с ячейки D1, начинаем спускать вниз, выделяя диапазон. В это время смотрим как меняется счетчик суммы в правом нижнем углу:
4. Все изделия А (ячейки от 1 до 260) стоили 2845492 рублей, значит на изделия В осталось 1354508 рублей.
5. Далее, начиная с ячейки D261, начинаем спускать вниз, выделяя диапазон. В это время смотрим как меняется счетчик суммы в правом нижнем углу: остановились на ячейке D427, сумма изделий достигла 1347484 рублей, дальше мы сможем взять не все изделия из ячейки 428. Остается всего 1354508 — 1347484 = 7024 рубля.Тогда мы можем взять 19 изделий по 363 рубля. 6. Считаем количество купленных изделий типа А и В: = СУММ(В1:В427)+19. Количество равно 17173.
Считаем неиспользованную сумму денег: 4200000 — СУММ(D1:D427)-19*363 = 127 руб. Таким образом, ответ 17173 127
Решение с помощью программы
f=open(’2.txt’)
n, m = map(int, f.readline().split())
a = []
b = []
for i in range(n):
price, count, type_ = f.readline().split()
price = int(price)
count = int(count)
if type_ == ’A’:
a.append((price, count))
else:
b.append((price, count))
a.sort()
c_a = 0
money = m
for price, count in a:
if money <= 0:
break
maxim = min(count, money // price)
c_a += maxim
money -= maxim * price
b.sort()
c_b = 0
for price, count in b:
if money <= 0:
break
maxim = min(count, money // price)
c_b += maxim
money -= maxim * price
print(c_a + c_b, money)