Форум » Массивы, сортировка, работа с файлами » Не сходится ответ в задаче 40 Номер 26 ЕГЭ информатика » Ответить
Не сходится ответ в задаче 40 Номер 26 ЕГЭ информатика
Юлия Смолина: 40) Для перевозки партии грузов различной массы выделен грузовик, но его грузоподъёмность ограничена, поэтому перевезти сразу все грузы не удастся. Грузы массой от 310 до 320 кг грузят в первую очередь, выбирая грузы по убыванию массы, начиная с самого тяжёлого. На оставшееся после этого место стараются взять как можно большее количество грузов. Если это можно сделать несколькими способами, выбирают тот способ, при котором самый большой из выбранных грузов имеет наибольшую массу. Если и при этом условии возможно несколько вариантов, выбирается тот, при котором наибольшую массу имеет второй по величине груз, и т.д. Известны количество грузов, масса каждого из них и грузоподъёмность грузовика. Необходимо определить количество и общую массу грузов, которые будут вывезены при погрузке по вышеописанным правилам. Входные данные представлены в файле 26-39.txt следующим образом. В первой строке входного файла записаны два целых числа: N – общее количество грузов и M – грузоподъёмность грузовика в кг. Каждая из следующих N строк содержит одно целое число – массу груза в кг. В ответе запишите два целых числа: сначала максимально возможное количество грузов, затем их общую массу. Пример организации исходных данных во входном файле: 6 720 100 315 120 160 140 300 В данном случае сначала нужно взять груз массой 315 кг. Остается 405 кг. После этого можно вывезти ещё максимум 3 груза. Это можно сделать тремя способами: 100 + 120 + 140, 100 + 140 + 160, 100 + 120 + 160. Выбираем способ, при котором вывозится груз наибольшей возможной массы. Таких способов два: 100 + 120 + 160, 100 + 140 + 160. Из этих способов выбираем тот, при котором больше масса второго по величине груза, то есть 100 + 140 + 160. Всего получается 4 груза общей массой 715 кг. Ответ: 4 715. В задаче ответ 113 9999 Но мы можем не последний большой убрать, а предпоследний Решение Сумма грузов от 310 до 320 равна 2875 (количество таких 9) Останется места 10000-2875=7173 Ближайшая сумма, это сумма 104 элементов равна 7164. Далее мы мы считаем разницу 7173 - 7164=9 Если мы уберем 131+9 получим 140 ближайший элемент 139, тогда результат 9999 Но если уберем 129+9=138, а такой элемент есть , тогда результат 10000. Соответственно вся машина заполнена. В задаче написано максимально возможный груз и это 138. 104+9=113 первый ответ 10000 второй ответ
Ответов - 3
beep: Конец массива с грузами, которые грузятся во вторую очередь на первой итерации будет выглядеть так: [..., 124, 126, 128, 129, 131] Остается лишних 9 единиц, которые можно погрузить. Если заменить число 131, то конец массива будет выглядеть так: [..., 124, 126, 128, 129, 131, 139] Если менять число 129, то конец массива будет выглядеть так: [..., 124, 126, 128, 129, 131, 138] В первом случае максимальный элемент 139, во втором - 138. По условию, если есть неоднозначность, то выбор идет в пользу того варианта, где максимальный вес больше. В Вашем случае он меньше.
Юлия Смолина: просто здесь же задача максимально заполнить, а не найти максимальный груз, на сайте решу егэ, такая же задача, и решается она именно на полную загрузку и формулировка задания такая же.
beep: Юлия Смолина, я не знаю, что за задача на сайте решу егэ и что там за решение, но в задаче, про которую Вы пишите, нет требования максимально заполнить (кого? грузовик?), требуется забрать максимальное количество грузов. На оставшееся после этого место стараются взять как можно большее количество грузов. Если это можно сделать несколькими способами, выбирают тот способ, при котором самый большой из выбранных грузов имеет наибольшую массу. Если и при этом условии возможно несколько вариантов, выбирается тот, при котором наибольшую массу имеет второй по величине груз, и т.д. И ищется не максимальный груз, а вариант, при котором максимальное количество грузов получается. А если оказывается, что можно несколькими способами получить это число, то для однозначности задается способ, которым отбирается правильный вариант, и заключается он в том, что правилен тот способ, у которого максимальный груз больше, если есть 2 способа с одинаковым максимальным грузом, то сравниваются грузы вторые по величине и так до последнего (первого) груза (если все грузы одинаковой массы, то это один и тот же способ). Это Вы захотели максимально заполнить грузовик, а в задаче требуется взять максимальное количество грузов. Если у Вас будет один из грузов массой 10000 и 50 грузов массой 1, то правильным ответом будет взять 50 грузов массой 1 и уехать, а не взять 1 груз массой 10000 - понимаете? Таковы условия задачи.
полная версия страницы