Задача к ЕГЭ по информатике на тему «Перевоз грузов» №1

Задание выполняется с использованием прилагаемых файлов

Для перевозки партии грузов различной массы выделен грузовик, но его грузоподъёмность ограничена, поэтому перевезти сразу все грузы не удастся. Грузы массой от $150$ до $200$ кг грузят в первую очередь. На оставшееся после этого место стараются взять как можно больше грузов. Если это можно сделать несколькими способами, выбирают тот способ, при котором самый большой из выбранных грузов имеет наибольшую массу. Если и при этом условии возможно несколько вариантов, выбирается тот, при котором наибольшую массу имеет второй по величине груз, и т.д. Известны количество грузов, масса каждого из них и грузоподъёмность грузовика. Необходимо определить количество и общую массу грузов, которые будут вывезены при погрузке по вышеописанным правилам.

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

Первая строка входного файла содержит два целых числа через пробел: $N$ — общее количество грузов и $M$ — грузоподъёмность грузовика в кг. Каждая из следующих $N$ строк содержит одно целое число — массу груза в кг.

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

В ответе запишите два целых числа: сначала максимально возможное количество грузов, затем их общую массу.

Пример входных данных:

$6 650$

$110$

$205$

$140$

$190$

$70$

$410$

В данном случае сначала нужно взять груз массой $190$ кг. После этого можно вывезти ещё максимум $3$ груза. Это можно сделать тремя способами: $110+ 205+ 140$ , $110 + 205+ 70$ , $205+ 140 + 70$ . Выбираем способ, при котором вывозится груз наибольшей возможной массы. Такой способ один: $110 + 205+ 140$ . Всего получается $4$ груза общей массой $645$ кг. В ответе надо записать числа $4$ и $645$ .

Решение 1 ( Excel / LibreOffice):

Откроем текстовый документ, скопируем значения и перенесем их в Excel или LibreOffice.
Перенесем числовые значения размера архива и кол-ва пользователей куда-нибудь, где они нам не помешают. Сортируем все данные ниже 1 строки (жмём н левую верхнюю ячейку $→$ Сортировка и фильтр $→$ Сортировка по возрастанию). Листаем вниз и находим первый груз размером 150, зажимаем эту ячейку и тянем вниз, пока не получим в правом нижнем углу максимальную сумму, не превышающую 8742. Получаем 8593 и количество 55. У нас остается 149 кг (8742 — 8593) свободного места, переходим в самый верх и с самого первого груза начинаем набирать максимальную сумму, не превышающую 149, выходит 147 и количество 35. Заменяем груз весом 8 на груз весом 10, так как займем больше место. Выходит, что мы заняли всё место, значит, сумм 8742, а количество 55 + 35 = 90.

Решение 2 (Python):

file = open("Задание_26__i0ia.txt")
lines = file.readlines()

n, m = map(int, lines[0].split())
array = list(map(int, lines[1:]))
array = sorted(array)

i = 0
current_sum = 0
last_elem = 0
ind_last = 0
count = 0

while array[i] <= 200:
    if array[i] >= 150 and current_sum + array[i] <= m:
        current_sum += array[i]
        last_elem = array[i]
        count += 1
    else:
        ind_last = i
    i += 1

for j in range(ind_last):
    if current_sum + array[j] <= m:
        current_sum += array[j]
        last_elem = array[j]
        count += 1

for j in range(i, len(array)):
    if current_sum + array[j] <= m:
        current_sum += array[j]
        last_elem = array[j]
        count += 1

free_space = m - current_sum + last_elem

for i in range(len(array) - 1, 0, -1):
    if array[i] <= free_space:












































































































































































































        current_sum += array[i] - last_elem
        break

print(count, current_sum)

Ответ: 90 8742