Теория к заданию 26 ЕГЭ по информатике Обработка целочисленных данных с сортировкой
Задание 26 — обработка набора чисел из файла. Типичные сюжеты: сколько файлов войдёт на диск и какой из них самый большой, самая длинная цепочка вложенных коробок, заявки на зал, сумма по ключу для товаров или клиентов. Почти всегда нужны сортировка по ключу и жадный выбор: на каждом шаге берут лучший из оставшихся вариантов.
Ответ — два числа. За верный ответ дают 2 балла, а 1 балл — если числа перепутаны местами или на своём месте верно только одно число. Задание решают программой: числа читают из файла, сортируют и проходят один раз. В демоверсии 2027 года сюжет другой — журнал сервера с резервными копиями раздела памяти, но приёмы те же: сумма по ключу словарём и сортировка.
Пример задания
Открытый банк ФИПИ
Входной файл содержит сведения о заявках на проведение мероприятий в конференц-зале. В каждой заявке указаны время начала и время окончания мероприятия (в минутах от начала суток). Если время начала одного мероприятия меньше времени окончания другого, то провести можно только одно из них. Если время окончания одного мероприятия совпадает со временем начала другого, то провести можно оба.
Определите, какое максимальное количество мероприятий можно провести в конференц-зале и каков при этом максимально возможный перерыв между двумя последними мероприятиями.
Входные данные:
В первой строке входного файла находится натуральное число N (N ≤ 1000) –
количество заявок на проведение мероприятий. Следующие N строк содержат пары чисел, обозначающих время начала и время окончания мероприятий. Каждое из чисел натуральное, не превосходящее 1440.
Запишите в ответе два числа: максимальное количество мероприятий и самый длинный перерыв между двумя последними мероприятиями (в минутах).
Типовой пример организации данных во входном файле:
5
10 150
100 120
131 170
150 180
120 130
При таких исходных данных можно провести максимум три мероприятия, например, мероприятия по заявкам 2, 3 и 5. Максимальный перерыв между двумя последними мероприятиями составит 20 мин., если состоятся мероприятия по заявкам 2, 4 и 5.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Что учить: от главного к редкому
Основа
Понятия, на которых стоят все правила
Главное
Самые частые правила — учите первыми
Реже
Учите, когда главное уже освоено
Тренировка в формате ЕГЭ
Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов. Известно, какой объём занимает файл каждого пользователя.
По заданной информации об объёме файлов пользователей и свободном объёме на архивном диске определите максимальное число пользователей, чьи файлы можно сохранить в архиве, а также максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
Входные данные:
В первой строке входного файла находятся два числа: S — размер свободного места на диске (натуральное число, не превышающее 10 000) и N — количество пользователей (натуральное число, не превышающее 1000). В следующих N строках находятся значения объёмов файлов каждого пользователя (все числа натуральные, не превышающие 100), каждое в отдельной строке.
Запишите в ответе два числа: сначала наибольшее число пользователей, чьи файлы могут быть помещены в архив, затем максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
Пример входного файла:
100 4
80
30
50
40.
При таких исходных данных можно сохранить файлы максимум двух пользователей. Возможные объёмы этих двух файлов 30 и 40, 30 и 50 или 40 и 50. Наибольший объём файла из перечисленных пар — 50, поэтому ответ для приведённого примера: 2 и 50.