На складе предприятия имеются заготовки двух видов: A и B, у каждой заготовки есть размер, измеряемый в миллиметрах. Для производства одного изделия необходима одна заготовка типа A и одна заготовка типа B, при этом разность размеров этих заготовок должна быть не более 20 мм. Прибыль от продажи полученного изделия численно равна сумме размеров использованных заготовок.
Руководство предприятия хочет использовать имеющиеся заготовки так, чтобы получить максимальную прибыль. Определите, сколько изделий для этого нужно произвести и какая прибыль будет получена.
Входные данные.
Первая строка входного файла содержит целое число N — общее количество изделий на складе. Каждая из следующих N строк содержит букву A или B, определяющую тип заготовки, и целое число — размер этой заготовки.
В ответе запишите два целых числа: сначала количество произведённых изделий, затем полученную прибыль.
Ответ:
##Приведём решение на языке Python.
f = open('26.txt')
N = int(f.readline())
a=[]
b=[]
for i in f:
start, end = map(str, i.split())
if start=='A':
a.append(int(end))
else:
b.append(int(end))
a.sort(reverse=True)
b.sort(reverse=True)
numa = 0
numb = 0
izdelie = 0
prib = []
while len(a) > numa and len(b) > numb:
if abs(a[numa] - b[numb]) > 20:
if a[numa] > b[numb]:
numa += 1
else:
numb += 1
else:
izdelie += 1
prib.append(a[numa] + b[numb])
numa += 1
numb += 1
print(izdelie, sum(prib))
Ответ: 5669; 29011899.
Приведём решение Юрия Красильникова на языке Python.
det = [s.split() for s in open('26.txt')][1:]
a,b,izdel = [],[],[] # детали A, детали B, изделия
for x in det: (a if x[0] == 'A' else b).append(int(x[1]))
a.sort()
b.sort()
while a and b: # пока оба списка A и B не пустые
while (a and b) and abs(a[-1] - b[-1]) > 20:
(a if a[-1] > b[-1] else b).pop()
if a and b: izdel.append(a.pop() + b.pop()) # добавляем изделие
print(len(izdel),sum(izdel))