В 2025 году в ЕГЭ по информатике появился новый прототип задачи №26 — про оптимизацию выбора оборудования.
Текст задания:
Для дачных участков СНТ необходимо закупить снегоуборщики. Для каждого из N участков будет куплен свой снегоуборщик. Известны минимальные требования к мощности этой техники для каждого из участков.
Для закупки доступно К моделей снегоуборщиков определённой мощности и стоимости. Количество экземпляров каждой модели не ограничено. Для каждого участка выбирается снегоуборщик минимальной стоимости, мощность которого не меньше требуемой; при одной и той же стоимости выбирается модель максимальной мощности.
Требуется определить общую стоимость закупки и максимальную мощность снегоуборщика, входящего в число купленных. В ответе запишите два числа: сначала суммарную стоимость всех купленных снегоуборщиков, затем максимальную мощность среди них.
Входные данные
Первая строка входного файла содержит два натуральных числа: N (1 < N < 1 000 000) - количество участков CHT и К (1 < K < 100 000) - количество моделей снегоуборщиков соответственно.
Следующие N строк содержат по одному натуральному числу, не превышающему 1000, минимальные мощности снегоуборщиков, которые можно закупить для каждого из N участков. Далее в каждой из К строк содержится пара натуральных чисел - мощность очередной модели снегоуборщика и её стоимость соответственно. Мощность снегоуборщиков не превосходит 1000, стоимость - 100 000. Гарантируется, что любые две модели снегоуборщиков различаются по мощности или по стоимости. Закупить подходящий набор снегоуборщиков всегда можно.
Выходные данные
В ответе укажите два искомых числа: суммарную стоимость всех купленных снегоуборщиков и максимальную мощность среди них.
Типовой пример организации данных во входном файле
3 4
1
2
3
10 7
1 5
3 7
2 3
При таких исходных данных для первого и второго участков оптимально закупить одинаковые снегоуборщики мощностью 2 и стоимостью 3, для третьего участка будет закуплен снегоуборщик мощностью 10. Стоимость закупки составит 3 + 3 + 7 = 13. Ответ: 13; 10.
На первый взгляд — просто: «выбрать модель с наименьшей ценой при достаточной мощности».
Но на деле — это типичная задача на перебор с оптимизацией, которую нельзя решить в LibreOffice Calc, потому что:
- данных слишком много (до 1 000 000 участков и 100 000 моделей),
- требуется быстрый поиск по условию,
- нужно минимизировать стоимость при ограничении на мощность.
Единственный рабочий инструмент — Python с предварительной обработкой данных.
Разберём решение пошагово!
📌 Условие задачи кратко
Для N участков нужно закупить снегоуборщики.
Для каждого участка задана минимально допустимая мощность.
Есть K моделей снегоуборщиков, каждая с указанием мощности и стоимости.
Требуется:
- Для каждого участка выбрать самую дешёвую модель, у которой мощность не ниже требуемой.
- Если таких моделей несколько — выбрать с наибольшей мощностью (условие устойчивости).
- Вывести: общую стоимость закупки,
максимальную мощность среди всех купленных снегоуборщиков.
🔍 Почему LibreOffice Calc не подходит?
- В таблице может быть до 1 000 000 строк с участками и 100 000 моделей.
- Для каждого участка нужно найти все модели с мощностью ≥ требуемой, затем выбрать с минимальной стоимостью.
- В Excel/Calc это потребует вложенных циклов → время выполнения — часы.
- На экзамене — ограничение по времени → такой подход не пройдёт.
Только алгоритмически оптимизированный Python-код справится за секунды.
💻 Решение пошагово
🔹 Блок 1: чтение входных данных
Что делает:
Открывает файл с данными.
Читает первую строку: N — количество участков, K — количество моделей.
Преобразует строку в два целых числа.
🔹 Блок 2: считываем требования по участкам
Что делает: Считывает N строк — по одной на каждый участок.
Каждая строка — минимально допустимая мощность для этого участка.
Сохраняет всё в список u.
🔹 Блок 3: инициализация массива минимальных цен
Что делает:
Создаёт массив s длиной K (по количеству возможных мощностей).
Заполняет его очень большим числом — это «бесконечность» для стоимости.
Индекс массива = мощность модели, значение = минимальная стоимость для этой мощности.
⚠️ Важно: в условии сказано, что мощность ≤ 1000, поэтому массив размером 1000–2000 — достаточно.
🔹 Блок 4: обработка моделей — поиск минимальной цены для каждой мощности
Что делает:
Читает K строк — каждая содержит V (мощность) и price (стоимость).
Для каждой модели обновляет s[V] — оставляет только самую дешёвую цену для данной мощности.
Если есть две модели с мощностью 10 и ценами 5 и 7 — запомнится 5.
✅ Это первый уровень оптимизации: сжимаем все модели до лучшей цены на каждую мощность.
🔹 Блок 5: сортировка по стоимости и мощности
Запись на занятия здесь: https://t.me/nka39
Что делает:
Преобразует массив s в список пар: [мощность, стоимость].
Сортирует его по возрастанию стоимости, а при равной стоимости — по убыванию мощности (-x[0]).
💡 Зачем нужна lambda?
Функция sort() в Python позволяет задать ключ сортировки через параметр key.
lambda x: [x[1], -x[0]] — это короткая запись функции, которая говорит: «Сортируй по второму элементу (x[1] — стоимость),
а если стоимости равны — по первому элементу в обратном порядке (-x[0] — чтобы большая мощность шла раньше)».
Это гарантирует, что при равной цене будет выбрана модель с большей мощностью — как того требует условие.
✅ Теперь первые элементы — самые дешёвые, и среди них — самые мощные.
🔹 Блок 6: выбор модели для каждого участка — подробная логика
Как работает алгоритм:
Мы уже отсортировали все модели так, что сначала идут самые выгодные (дешёвые + мощные).
Для каждого участка (uc — требуемая мощность) мы проходим по списку сверху вниз.
Как только встречаем первую модель, у которой V >= uc (мощность достаточна), — останавливаемся (break).
Эта модель — оптимальна:она самая дешёвая среди всех подходящих,
и при равной цене — самая мощная (благодаря сортировке).
Добавляем её стоимость к общей сумме и запоминаем мощность.
✅ Такой подход гарантирует глобальный минимум стоимости и соблюдение условия устойчивости.
🔹 Блок 7: вывод ответа
Что делает:
Выводит два числа: Общую стоимость закупки,
Максимальную мощность среди всех купленных снегоуборщиков.
✅ Это и есть ответ на задачу.
🧾 Полный код решения с комментариями
⚡ Почему этот код работает быстро?
- Предварительная обработка (s[V] = min(...)) — O(K).
- Сортировка — O(M log M), где M ≤ 1000 (макс. мощность).
- Выбор для N участков — O(N × M), но благодаря сортировке и break — в среднем O(N).
- Итого: даже при N = 1 000 000 — код выполняется за доли секунды.
В LibreOffice Calc такой объём данных просто зависнет.
💬 Заключение
Задача про снегоуборщики — яркий пример того, как реальные инженерные задачи приходят в ЕГЭ.
Она проверяет не только знание алгоритмов, но и умение оптимизировать перебор.
Ключевые идеи:
- Сжать данные до лучшей цены на каждую мощность.
- Отсортировать по стоимости и мощности.
- Использовать ранний выход (break) при поиске.
И помните:
На ЕГЭ по информатике разрешено использовать Python. Используйте это — особенно когда Calc бессилен.
Подпишитесь на канал и научитесь решать все задания ЕГЭ по информатике!
Удачи на экзамене!
Записаться ко мне на занятия можно тут https://t.me/nka39