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

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

Входные данные представлены в файле 26_5.txt следующим образом. В первой строке входного файла записаны два целых числа: N – общее количество грузов и М – грузоподъемность грузовика в кг. Каждая из следующих N строк содержит одно целое число – массу груза в кг. В ответе запишите два целых,числа: сначала общую массу всех грузов, затем массу последнего погруженного груза.

Откроем файл в Excel. Удаляем первую строку, предварительно запомнив значения в ней: 4000 и 18000. Сортируем столбец А в порядке возрастания.

Ищем грузы от 101 до 179 кг включительно, копируем их и вставляем в столбец C, при этом удаляем их из столбца А. Их масса равна 32001.

Посчитаем, сколько грузоподъемности у нас останется после набора выбранных грузов: 180000− 32001 = 147999  кг – оставшаяся грузоподъемность.

На оставшиеся места возьмем наименьшие по массе грузы. В ячейку B1 копируем значение из ячейки А1. В ячейку В2 записываем формулу: =В1+А2 и растягиваем вниз до конца таблицы.

Проходимся по столбцу В и ищем значение, максимально приближенное к 147999. Это значение – 147696. До полного заполнения грузовика остается 147999 − 147696 = 303  кг. Значит, нам выгодно взять груз не 366 кг, а 669. Такой груз присутствует в списке, значит число 669 будет ответом на второй вопрос.

Так как грузовик полностью забит, то масса всех грузов: 180000.

Ответ: 180000 669
Оцените статью
Я решу все!