Задание 26 ЕГЭ по информатике · 70B483
Контейнеры и грузоподъёмностьПовышеннаяКЭС 3.10
На грузовом судне необходимо перевезти контейнеры, имеющие одинаковый габарит и разные массы. Общая масса всех контейнеров превышает грузоподъёмность судна. Количество грузовых мест на судне не меньше количества контейнеров, назначенных к перевозке. Какое максимальное количество контейнеров можно перевезти за один рейс и какова масса самого тяжёлого контейнера среди всех контейнеров, которые можно перевезти за один рейс?
В первой строке входного файла находятся два числа: S — грузоподъёмность судна и N — количество контейнеров. В следующих N строках находятся значения масс контейнеров, требующих транспортировки, каждое в отдельной строке. Все числа натуральные; S≤100 000, N≤10 000, масса каждого контейнера не превышает 100.
Выведите два целых неотрицательных числа: максимальное количество контейнеров, которые можно перевезти за один рейс, и массу наиболее тяжёлого из них.
1_70B483.zipВ первой строке входного файла находятся два числа: S — грузоподъёмность судна и N — количество контейнеров. В следующих N строках находятся значения масс контейнеров, требующих транспортировки, каждое в отдельной строке. Все числа натуральные; S≤100 000, N≤10 000, масса каждого контейнера не превышает 100.
Выведите два целых неотрицательных числа: максимальное количество контейнеров, которые можно перевезти за один рейс, и массу наиболее тяжёлого из них.
Показать ответ
1612 90
Подсказки (3)
- Чтобы перевезти как можно больше контейнеров, в первую очередь выбирайте контейнеры с наименьшей массой.
- Отсортируйте массы по возрастанию и последовательно добавляйте контейнеры, пока суммарная масса не превысит S.
- Ответом будут количество добавленных контейнеров и масса последнего добавленного контейнера.
Решение
1. Для максимального количества контейнеров выгодно выбирать самые лёгкие контейнеры: замена любого выбранного контейнера на более лёгкий не увеличивает суммарную массу.
2. Отсортируем массив масс по возрастанию.
m1≤m2≤⋯≤mN
3. Будем последовательно складывать массы, пока очередной контейнер помещается на судно. Пусть k — максимальный индекс, для которого сумма первых k масс не превышает грузоподъёмность.
∑i=1kmi≤S,∑i=1k+1mi>S
4. Тогда можно перевезти k контейнеров, а масса самого тяжёлого из них равна mk.
2. Отсортируем массив масс по возрастанию.
m1≤m2≤⋯≤mN
3. Будем последовательно складывать массы, пока очередной контейнер помещается на судно. Пусть k — максимальный индекс, для которого сумма первых k масс не превышает грузоподъёмность.
∑i=1kmi≤S,∑i=1k+1mi>S
4. Тогда можно перевезти k контейнеров, а масса самого тяжёлого из них равна mk.
Частые ошибки
- Выбирать контейнеры в исходном порядке, не сортируя их по массе.
- Максимизировать суммарную массу вместо количества контейнеров.
- Выводить массу следующего контейнера, который уже не помещается.
Источник: Открытый банк ФИПИ
Похожие задания
26Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 3, а во второй — 2…Игровая стратегия с обоснованием · 02861826В магазине для упаковки подарков есть N кубических коробок из материалов двух видов. Одну коробку можно…Коробки и коржи: вложение с заданной разностью · 05BFA626Два игрока, Петя и Ваня, играют в игру с двумя кучами камней. За один ход игрок может добавить в одну из куч…Игровая стратегия с обоснованием · 06BC0626Два игрока, Петя и Ваня, играют в следующую игру. У игроков есть табличка, на которой записана пара…Игровая стратегия с обоснованием · 07474E26Два игрока, Петя и Ваня, играют в игру с кучей камней. За один ход игрок может добавить в кучу 2 или 3 камня…Игровая стратегия с обоснованием · 09074E26Сервер выполняет запросы на передачу данных. Сведения о каждом выполненном запросе — время регистрации…Журнал сервера и резервные копии · 09681E
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.