Решение. Создадим два двумерных массива. В первый массив считаем все элементы из файла и отсортируем его по возрастанию. После этого посчитаем максимальное количество изделий, которое можем закупить на заданную сумму, последовательно прибавляя к переменной sum цену изделия в текущем элементе. Далее в отдельный двумерный массив вынесем только оставшиеся изделия A. Далее будем перебирать уже взятые изделия с конца, пытаясь заменить изделия B на изделия A таким образом, чтобы сумма взятых изделий не превышала заданную сумму. После этого посчитаем, сколько изделий A получилось закупить.
Приведём решение на языке Pascal.
var
n, m, x, t1, t2, countA, count, i, j: integer;
z: string;
arrayAB: array [1..916, 1..2] of integer;
arrayA: array [1..916, 1..2] of integer;
sum: integer;
f: text;
begin
assign(f,'C:\26.txt');
reset(f);
readln(f, n, m);
countA := 0;
count := 0;
sum := 0;
for i := 1 to n do begin
if not eof(f) then
readln(f, x, z)
else break;
if z.Contains('A') then begin
arrayAB[i, 1] := x;
arrayAB[i, 2] := 0;
end;
if z.Contains('B') then begin
arrayAB[i, 1] := x;
arrayAB[i, 2] := 1;
end;
end;
for i := 1 to n-1 do
for j := i + 1 to n do
if arrayAB[i, 1] > arrayAB[j, 1] then begin
t1 := arrayAB[i, 1];
t2 := arrayAB[i, 2];
arrayAB[i, 1] := arrayAB[j, 1];
arrayAB[i, 2] := arrayAB[j, 2];
arrayAB[j, 1] := t1;
arrayAB[j, 2] := t2;
end;
for i := 1 to n do
if (sum + arrayAB[i, 1]) < m then begin
sum := sum + arrayAB[i, 1];
count := count + 1;
end
else break;
x := 1;
for i := count + 1 to n do
if arrayAB[i, 2] = 0 then begin
arrayA[x, 1] := arrayAB[i, 1];
arrayA[x, 2] := arrayAB[i, 2];
x := x + 1;
end;
x := 1;
for i := count downto 1 do begin
if arrayAB[i, 2] = 1 then begin
if ((sum - arrayAB[i, 1] + arrayA[x, 1]) > m) then break;
sum := sum - arrayAB[i, 1] + arrayA[x, 1];
arrayAB[i, 1] := arrayA[x, 1];
arrayAB[i, 2] := arrayA[x, 2];
x := x + 1;
end;
end;
for i := 1 to count do
if arrayAB[i, 2] = 0 then countA := countA + 1;
writeln(countA, ' ', m - sum);
end.
В результате работы данного алгоритма при вводе данных из файла в условии получаем ответ — 157 267.
Ответ: 157 267.
Примечание. Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём решение на языке Python.
f = open('26.txt')
n, m = f.readline().split()
arrayAB = [[0] * 2 for i in range(916)]
arrayA = [[0] * 2 for i in range(916)]
n = int(n)
m = int(m)
count = 0
sumi = 0
for i in range(n):
x, z = f.readline().split()
arrayAB[i][0] = int(x)
if z == 'A':
arrayAB[i][1] = 0
if z == 'B':
arrayAB[i][1] = 1
arrayAB.sort()
i = 0
while m > arrayAB[i][0] + sumi:
if (sumi + arrayAB[i][0]) < m:
sumi = sumi + arrayAB[i][0]
count += 1
i += 1
x = 1
for i in range(count, n):
if arrayAB[i][1] == 0:
arrayA[x][0] = arrayAB[i][0]
arrayA[x][1] = arrayAB[i][1]
x += 1
x = 1
for i in range(count - 1, -1, -1):
if arrayAB[i][1] == 1:
if (sumi - arrayAB[i][0] + arrayA[x][0]) > m:
break
sumi = sumi - arrayAB[i][0] + arrayA[x][0]
arrayAB[i][0] = arrayA[x][0]
arrayAB[i][1] = arrayA[x][1]
x += 1
countA = 0
for i in range(count):
if arrayAB[i][1] == 0:
countA = countA + 1
print(countA, m - sumi)
Приведём решение Ильи Пащука (Липецк) на языке Python.
f = open('26.txt') # считывание входных данных
maxsum = int(f.readline().replace('\n','').split(' ')[1])
l = f.readlines()
f.close()
ll = []
for i in l:
ii = i.replace('\n','').split(' ')
ii[0] = int(ii[0])
ll.append(ii)
# создаём отдельные массивы для изделий a и b, и сортируем все 3 массива
alist = [k[0] for k in ll if k[1] == 'A']
blist = [k[0] for k in ll if k[1] == 'B']
alist.sort()
blist.sort()
ll.sort(key=lambda k: k[0])
# считаем максимальное количество изделий
msum = 0
maxc = 0
for i in ll:
if msum + i[0] <= maxsum:
msum += i[0]
maxc += 1
else: break
# "закупаем" максимальное количество изделий A
ba = []
for i in alist:
if len(ba) >= maxc: break
if sum(ba) + i <= maxsum:
ba.append(i)
else: break
# докупаем изделия B, при необходимости удаляя изделия A, пока не доберём до максимального значения
bb = []
for i in blist:
if len(ba) + len(bb) >= maxc: break
if sum(ba) + sum(bb) + i <= maxsum:
bb.append(i)
else:
while sum(ba) + sum(bb) + i > maxsum: del ba[-1]
bb.append(i)
# вывод ответа
print(len(ba))
print(maxsum - (sum(ba) + sum(bb)))
Приведём решение Вячеслава Ладынского на языке Python.
f = open('26.txt')
n, m = map(int, f.readline().split())
f = [i.split() for i in f]
f = sorted([[int(i[0]), i[1]] for i in f])
a = []
b = []
for i in range(len(f)):
if sum(a+b) + f[i][0] <= m:
if f[i][1] == 'A':
a.append(f[i][0])
f[i] = []
elif f[i][1] == 'B':
b.append(f[i][0])
f[i] = []
f = [i for i in f if i != []]
for i in f:
if i[1] == 'A':
if sum(a+b) - b[-1] + i[0] <= m:
a.append(i[0])
b.pop(-1)
print(len(a), m - sum(a + b))
Приведём решение Юрия Красильникова на языке Python.
f=open('26.txt')
n,s=map(int, f.readline().split())
a=sorted([[int(s.split()[0]),s.split()[1]] for s in f],key=lambda x: x[0],reverse=True)
packa,packb=[],[]
while s >= a[-1][0]:
x=a.pop()
(packa if x[1]=='A' else packb).append(x)
s-=x[0]
aa=[x for x in a if x[1]=='A']
while aa and packb and aa[-1][0]-packb[-1][0] <= s:
s-=aa[-1][0]-packb[-1][0]
packb.pop()
packa.append(aa.pop())
print(len(packa),s)
PDF-версии: 