var
n, m, x, y, t1, t2, countA, countB: integer;
z: string;
arrayA: array [1..500,1..2] of integer;
arrayB: array [1..500,1..2] of integer;
sum, countSumA: integer;
f: text;
begin
assign(f,'C:\26.txt');
reset(f);
readln(f, n, m);
countA := 0;
countB := 0;
sum := 0;
for i: integer := 1 to m do begin
if not eof(f) then
readln(f, x, y, z)
else break;
if z.Contains('A') then begin
arrayA[i,1] := x;
arrayA[i,2] := y;
countA := countA + 1;
end;
if z.Contains('B') then begin
arrayB[i,1] := x;
arrayB[i,2] := y;
countB := countB + 1;
end;
end;
for i:integer := 1 to n do
for j:integer := i + 1 to n do
if arrayA[i,1] > arrayA[j,1] then begin
t1 := arrayA[i,1];
t2 := arrayA[i,2];
arrayA[i,1] := arrayA[j,1];
arrayA[i,2] := arrayA[j,2];
arrayA[j,1] := t1;
arrayA[j,2] := t2;
end;
for i:integer := 1 to n do
for j:integer := i + 1 to n do
if arrayB[i,1] > arrayB[j,1] then begin
t1 := arrayB[i,1];
t2 := arrayB[i,2];
arrayB[i,1] := arrayB[j,1];
arrayB[i,2] := arrayB[j,2];
arrayB[j,1] := t1;
arrayB[j,2] := t2;
end;
for i:integer := n-countB+1 to n do
for j:integer := 1 to arrayB[i,2] do
if (sum + arrayB[i,1]) < m then
sum := sum + arrayB[i,1]
else break;
for i:integer := n-countA+1 to n do
for j:integer := 1 to arrayA[i,2] do
if (sum + arrayA[i,1]) < m then begin
sum := sum + arrayA[i,1];
countSumA := countSumA + 1;
end
else break;
writeln(countSumA, ' ', m - sum);
end.
В результате работы данного алгоритма при вводе данных из файла в условии получаем ответ — 7165 245.
f = open('26.txt')
x, y = f.readline().split()
y = int(y)
for_A_price = []
for_A_kol = []
for i in f:
if 'B' in i:
a, b, c = i.split()
y -= int(a) * int(b)
else:
a2, b2, c2 = i.split()
for_A_price.append(int(a2))
for_A_kol.append(int(b2))
mini = min(for_A_price)
index_mini = 0
for i in range(len(for_A_price)):
if mini == for_A_price[i]:
index_mini = i
kol_B = 0
while y > for_A_price[index_mini]:
y -= for_A_price[index_mini]
for_A_kol[index_mini] -= 1
kol_B += 1
if for_A_kol[index_mini] == 0:
for_A_price[index_mini] = 1000000000
mini = min(for_A_price)
for i in range(len(for_A_price)):
if mini == for_A_price[i]:
index_mini = i
print(kol_B, y)