Задание 26 ЕГЭ по информатике: решайте с автопроверкой

В задании 26 дан файл с данными о заявках, грузах, местах в зале или файлах на диске. Нужно выбрать как можно больше элементов по правилу и ответить на дополнительный вопрос, например о последнем выбранном элементе.

Решать задачи номера

Как решать программой

Почти всегда решение начинается с сортировки. Для задачи о заявках на одно помещение сортируют по времени окончания и берут каждую заявку, которая начинается не раньше конца предыдущей выбранной. Такой жадный выбор даёт наибольшее число заявок.

Второй вопрос обычно сложнее первого. Сначала найдите наибольшее количество, затем проверьте, какой элемент может стать последним, не уменьшив его. Двоичный поиск из модуля bisect быстро считает, сколько выбранных окончаний не позже данного начала.

Прочитайте файл аккуратно: в первой строке обычно количество, дальше пары чисел. Проверьте решение на примере из условия, прежде чем запускать на файле.

Если в данных есть одинаковые заявки, жадный алгоритм с ними справляется: вторая такая заявка начинается раньше конца первой и не будет выбрана.

Разбор примера

Шесть заявок на спортзал, тренировки не пересекаются. Сколько заявок можно одобрить и как поздно может начаться последняя тренировка?

from bisect import bisect_right

req = [[60, 120], [0, 90], [100, 160], [120, 200], [170, 230], [200, 260]]
ends, last = [], -1
for s, e in sorted(req, key=lambda r: r[1]):
    if s >= last:
        ends.append(e)
        last = e
k = len(ends)
print(k, max(s for s, e in req if bisect_right(ends, s) >= k - 1))

Программа печатает

3 200

Жадный выбор берёт заявки [0, 90], [100, 160] и [170, 230]. Последней можно поставить и [200, 260]: до её начала уже кончились две тренировки. Поэтому ответ 3 и 200.

Решить эту задачу

Задачи к заданию 26

  • Заявки на спортзалСложнаяРешать
  • Акция «третий в подарок»СредняяРешать
  • Камера хранения на вокзалеСложнаяРешать
  • Снимки зонда за один сеанс связиСредняяРешать
  • Башня из блоковСложнаяРешать
  • Уборка снега на трассеСредняяРешать
  • Пассажиры на остановкеСредняяРешать
  • Приборы зонда с приоритетомСложнаяРешать

Бесплатно и без регистрации: пишете код в браузере и проверяете его тестами (без аккаунта — несколько задач в день).

Вопросы и ответы

Почему сортируют по окончанию, а не по началу?
Заявка, которая кончается раньше, оставляет больше времени для остальных. По началу жадный выбор может ошибиться.
Что делает bisect_right?
Находит в отсортированном списке, сколько элементов не больше заданного числа. Это двоичный поиск.
Как читать файл задания 26?
Первую строку как количество, остальные через split() в пары чисел.
Что делать с одинаковыми заявками?
Ничего особенного: сортировка ставит их рядом, и жадный выбор возьмёт не больше одной, потому что они пересекаются.