Информатика. ЕГЭ

Перейти к заданиям

Задание 26. Информатика. ЕГЭ. Основная волна. Пересдача. 03.07.2025

Просмотры: 2496
Изменено: 21 августа 2025

Для дачных участков СНТ необходимо закупить снегоуборщики. Для каждого из \(N\) участков будет куплен свой снегоуборщик. Известны минимальные требования к мощности этой техники для каждого из участков.

Для закупки доступно \(K\) моделей снегоуборщиков определённой мощности и стоимости. Количество экземпляров каждой модели не ограничено. Для каждого участка выбирается снегоуборщик минимальной стоимости, мощность которого не меньше требуемой; при одной и той же стоимости выбирается модель максимальной мощности.

Требуется определить общую стоимость закупки и максимальную мощность снегоуборщика, входящего в число купленных. В ответе запишите два числа: сначала суммарную стоимость всех купленных снегоуборщиков, затем максимальную мощность среди них.

Входные данные

Первая строка входного файла содержит два натуральных числа: \(N\) \((1 \leqslant N \leqslant 1~000~000)\) — количество участков СНТ и \(K\) \((1 \leqslant K \leqslant 100~000)\) — количество моделей снегоуборщиков соответственно. Следующие \(N\) строк содержат по одному натуральному числу, не превышающему \(1000,\) минимальные мощности снегоуборщиков, которые можно закупить для каждого из \(N\) участков. Далее в каждой из \(K\) строк содержится пара натуральных чисел — мощность очередной модели снегоуборщика и её стоимость соответственно. Мощность снегоуборщиков не превосходит \(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.\)

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Файл с данными

Решение:

Python


fd = open('26.txt')
N, K = map(int, fd.readline().split())
wanted = []
for _ in range(N):
    wanted.append(int(fd.readline()))
price_power = {}
for _ in range(K):
    power, pr = map(int, fd.readline().split())
    price_power[pr] = max(power, price_power.get(pr, 0))

snow = [[0, 0] for _ in range(1001)]
snow[0] = [10**20, 10**20]
for price, power in sorted(list(price_power.items())):
    if not snow[power][1]:
        i = power
        while not snow[i][1]:
            snow[i] = [price, power]
            i -= 1
total_sum, max_pow = 0, 0
for power in wanted:
    total_sum += snow[power][0]
    max_pow = snow[power][1]
print(total_sum, max_pow)

Ответ: \(1879667450 \,\, 924\)

kege1

kege2

kege3

Новый тренажёр-эмулятор
Станции КЕГЭ

Эффективно готовьтесь к ЕГЭ по информатике с новым тренажёром, эмулирующем работу станции КЕГЭ, которая используется на реальном экзамене

Новое видео
Методы решения задания 16 ЕГЭ по Информатике «Вычисление рекуррентных выражений»
Поддержать автора сайта!
​ Поддержите автора сайта, если материалы, размещённые здесь, оказались вам полезны.
Расписание пробников Статграда в 2026/27 учебном году
Информатика ОГЭ 9 класс
  1. 13 октября 2026 года
  2. 3 декабря 2026 года
  3. 21 января 2027 года
  4. 19 февраля 2027 года
  5. 23 марта 2027 года
  6. 27 апреля 2027 года
Математика ОГЭ 9 класс
  1. 23 сентября 2026 года
  2. 1 декабря 2026 года
  3. 22 января 2027 года
  4. 3 марта 2027 года
  5. 14 апреля 2027 года
Физика ОГЭ 9 класс
  1. 19 октября 2026 года
  2. 10 декабря 2026 года
  3. 29 января 2027 года
  4. 17 марта 2027 года
  5. 22 апреля 2027 года
Математика ЕГЭ 10 класс
  1. 3 февраля 2027 года
  2. 11 мая 2027 года
Информатика ЕГЭ 11 класс
  1. 22 октября 2026 года
  2. 15 декабря 2026 года
  3. 26 января 2027 года
  4. 2 марта 2027 года
  5. 13 апреля 2027 года
Математика ЕГЭ 11 класс
  1. 30 сентября 2026 года
  2. 17 декабря 2026 года
  3. 9 февраля 2027 года
  4. 16 марта 2027 года
  5. 21 апреля 2027 года
Физика ЕГЭ 11 класс
  1. 14 октября 2026 года
  2. 16 декабря 2026 года
  3. 4 февраля 2027 года
  4. 12 марта 2027 года
  5. 9 апреля 2027 года