На складе лежат пакеты с углём различного веса и стоимости. Вес и стоимость записаны на каждом пакете как натуральные числа: вес не превосходит 100, стоимость не превосходит 10000. Для транспортировки отбираются K пакетов с самой выгодной ценой угля за единицу веса. По заданной информации о пакетах с углём и количестве транспортируемых пакетов определите наибольший возможный вес отправленного угля и стоимость самого большого отправленного пакета.
Входные данные представлены в файле следующим образом. В первой строке через пробел записаны числа N — количество пакетов на складе (натуральное число, не превышающее 1000) и K – количество пакетов на отправку (натуральное число, не превосходящее 100). В каждой из последующих N строк через пробел записаны два числа – вес и стоимость каждого пакета.
Запишите в ответе два числа – сначала наибольший возможный вес отправленных пакетов, затем стоимость самого большого отправленного пакета.
Пример организации исходных данных во входном файле:
10 4
47 470
50 600
60 480
45 540
30 300
15 180
70 560
30 360
91 910
40 320
При таких исходных данных самая выгодная стоимость у пакетов весом 60, 70, 40; затем – у пакетов весом 91, 30, 47. Поэтому наибольший возможный вес к отправке равен 70+60+40+91 = 261, а стоимость самого большого отправленного пакета равна 910.
Ответ: _________________________.
Тренировочный вариант №1 от 23.11.2020 «ЕГЭ 100БАЛЛОВ»
Решение:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
f = open('26.txt') n, k = map(int, f.readline().split()) weight, cost = [0]*n, [0]*n for i in range(n): weight[i], cost[i] = map(int, f.readline().split()) for i in range(n-1): for j in range(i+1, n): if cost[i]/weight[i] > cost[j]/weight[j] or cost[i]/weight[i] == cost[j]/weight[j] and weight[i] < weight[j]: cost[i], cost[j] = cost[j], cost[i] weight[i], weight[j] = weight[j], weight[i] w = weight[0] c = cost[0] for i in range(1, k): if weight[i] > w: w = weight[i] c = cost[i] print(sum(weight[0:k]), w) |
5931 100
Ответ: 5931; 100