РЕШУ ЕГЭ — информатика

Задания

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

1.  Нужно купить как можно больше изделий, независимо от их типа и модификации.

2.  Если можно разными способами купить максимальное количество изделий, нужно выбрать тот способ, при котором будет куплено как можно больше изделий B.

3.  Если можно разными способами купить максимальное количество изделий с одинаковым количеством изделий B, нужно выбрать тот способ, при котором вся покупка будет дешевле.

Определите, сколько всего будет куплено изделий B и какая сумма останется неиспользованной.

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

Задание 26

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

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

Пример входного файла:

6 130

30 A

50 A

60 B

20 B

70 B

10 A

В данном случае можно купить не более 4 изделий, из них не более 2 изделий B. Минимальная цена такой покупки 120 рублей (покупаем изделия 30A, 60B, 20B, 10A). Останется 10 рублей. В ответе надо записать числа 2 и 10.

Ответ:

Решение. Создадим два двумерных массива. В первый массив считаем все элементы из файла и отсортируем его по возрастанию. После этого посчитаем максимальное количество изделий, которое можем закупить на заданную сумму, последовательно прибавляя к переменной sum цену изделия в текущем элементе. Далее в отдельный двумерный массив вынесем только оставшиеся изделия B. Далее будем перебирать уже взятые изделия с конца, пытаясь заменить изделия A на изделия B таким образом, чтобы сумма взятых изделий не превышала заданную сумму. После этого посчитаем, сколько изделий B получилось закупить.

Приведём решение на языке Pascal.

var

n, m, x, t1, t2, countB, count, i, j: integer;

z: string;

arrayAB: array [1..916, 1..2] of integer;

arrayB: array [1..916, 1..2] of integer;

sum: integer;

f: text;

begin

assign(f,'C:\26.txt');

reset(f);

readln(f, n, m);

countB := 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;

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] = 1 then begin

arrayB[x, 1] := arrayAB[i, 1];

arrayB[x, 2] := arrayAB[i, 2];

x := x + 1;

end;

x := 1;

for i := count downto 1 do begin

if arrayAB[i, 2] = 0 then begin

if ((sum - arrayAB[i, 1] + arrayB[x, 1]) > m) then break;

sum := sum - arrayAB[i, 1] + arrayB[x, 1];

arrayAB[i, 1] := arrayB[x, 1];

arrayAB[i, 2] := arrayB[x, 2];

x := x + 1;

end;

for i := 1 to count do

if arrayAB[i, 2] = 1 then countB := countB + 1;

writeln(countB, ' ', m - sum);

end.

В результате работы данного алгоритма при вводе данных из файла в условии получаем ответ  — 154 87.

Ответ: 154 87.

Примечание. Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.

Приведём решение на языке Python.

f = open('26 (11).txt')

n, m = f.readline().split()

arrayAB = [[0] * 2 for i in range(916)]

arrayB = [[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 == 'B':

arrayAB[i][1] = 0

if z == 'A':

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:

arrayB[x][0] = arrayAB[i][0]

arrayB[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] + arrayB[x][0]) > m:

break

sumi = sumi - arrayAB[i][0] + arrayB[x][0]

arrayAB[i][0] = arrayB[x][0]

arrayAB[i][1] = arrayB[x][1]

x += 1

countB = 0

for i in range(count):

if arrayAB[i][1] == 0:

countB = countB + 1

print(countB, m - sumi)

Приведём решение Александра Кузнецова на языке Python.

f = open('26.txt')

n, m = [int(i) for i in (f.readline()).split()]

lA, lB= [], []

l=[]

for i in f:

p, t = [str(j) for j in i.split()]

p=int(p)

l.extend([(p, t)])

f.close()

sumi=0

l.sort()

k=0

for p, t in l:

if sumi+p <= m:

if t=='A': lA.append(p)

if t=='B': k+=1

sumi+=p

elif t=='B' and sumi+p>m and len(lB)<=len(lA):

lB.append(p)

lA.sort()

lA=lA[::-1]

lB.sort()

for i in lB:

for j in range(len(lA)):

if sumi-lA[j]+i<=m:

sumi=sumi-lA[j]+i

k+=1

lA.pop(j)

break

print(k, m-sumi)

№ п/п	№ задания	Ответ
1	39255	154 87

Ключ