Информатика. ЕГЭ
Задание 26. Информатика. ЕГЭ 2026. ЕГКР. 18.04.2026
- Просмотры: 2977
- Изменено: 20 апреля 2026
Вдоль дороги длиной \(10\) км расположены дома. В течение дня жители отправляют в управляющую компанию заявки на уборку снега. В каждой заявке указано, с какой точки (в метрах от начала дороги) нужно начать уборку и какова длина участка (в метрах), который требуется очистить.
Если участки дороги в двух или более заявках имеют общую часть дороги, то можно выполнить не более одной из таких заявок. Если конец одного участка совпадает с началом другого, то нужно убрать оба участка.
Определите наибольшее количество заявок, которые может выполнить управляющая компания, и в этом случае минимальную длину неубранного участка, расположенного в конце дороги (в метрах).
Входные данные
Первая строка входного файла содержит целое число \(N\) \((N \leqslant 2000)\) — количество заявок на уборку снега. Следующие \(N\) строк содержат пары чисел, обозначающих начало участка (в метрах от начала дороги) и его протяжённость. Каждое из чисел натуральное, не превосходящее \(10~000.\) Гарантируется, что конец участка не выходит за пределы дороги.
В ответе запишите два целых числа: сначала наибольшее количество заявок, которые может выполнить управляющая компания, затем — минимально возможную при таком количестве заявок длину неубранного участка, расположенного в конце дороги (в метрах).
Типовой пример организации данных во входном файле
\(5\)
\(1 \,\, 1000\)
\(1001 \,\, 1000\)
\(2001 \,\, 2500\)
\(4501 \,\, 500\)
\(4501 \,\, 1500\)
При таких исходных данных будет выполнено не более \(4\) заявок. Могут быть выполнены заявки с номерами \(1, \, 2, \, 3\) и \(4\) или заявки с номерами \(1, \, 2, \, 3\) и \(5.\) Ответ: \(4 \,\, 3999.\)
Решение:
Python
fd = open('26.txt')
N = int(fd.readline())
req = [] # список заявок
for line in fd:
st, length = map(int, line.split())
req.append((st, st + length))
# сортируем список заявок в порядке возрастания последнего метра в заявке
# а при их равенстве, в порядке убывания начального метра в заявке
req.sort(key=lambda r: (r[1], -r[0]))
start, fin = req[0]
perf = [(start, fin)]
for i in range(1, N):
ts, tf = req[i]
if ts >= fin:
start, fin = ts, tf
perf.append((start, fin))
z = len(perf) # число исполненных заявок
# оптимизируем последнюю заявку, выбираем такую из возможных,
# чтобы последний метр был как можно больше
last = perf[-1][1]
prev = perf[-2][1]
curr = N - 1
while req[curr][1] >= prev:
if req[curr][0] >= prev and req[curr][1] > last:
last = req[curr][1]
curr -= 1
print(z, 10_000 - last)
Ответ: \(77 \,\, 184\)
Новый тренажёр-эмулятор
Станции КЕГЭ
Эффективно готовьтесь к ЕГЭ по информатике с новым тренажёром, эмулирующем работу станции КЕГЭ, которая используется на реальном экзамене
Новое видео
Поддержать автора сайта!
Расписание пробников Статграда в 2026/27 учебном году
Информатика ОГЭ 9 класс
- 13 октября 2026 года
- 3 декабря 2026 года
- 21 января 2027 года
- 19 февраля 2027 года
- 23 марта 2027 года
- 27 апреля 2027 года
Математика ОГЭ 9 класс
- 23 сентября 2026 года
- 1 декабря 2026 года
- 22 января 2027 года
- 3 марта 2027 года
- 14 апреля 2027 года
Физика ОГЭ 9 класс
- 19 октября 2026 года
- 10 декабря 2026 года
- 29 января 2027 года
- 17 марта 2027 года
- 22 апреля 2027 года
Математика ЕГЭ 10 класс
- 3 февраля 2027 года
- 11 мая 2027 года
Информатика ЕГЭ 11 класс
- 22 октября 2026 года
- 15 декабря 2026 года
- 26 января 2027 года
- 2 марта 2027 года
- 13 апреля 2027 года
Математика ЕГЭ 11 класс
- 30 сентября 2026 года
- 17 декабря 2026 года
- 9 февраля 2027 года
- 16 марта 2027 года
- 21 апреля 2027 года
Физика ЕГЭ 11 класс
- 14 октября 2026 года
- 16 декабря 2026 года
- 4 февраля 2027 года
- 12 марта 2027 года
- 9 апреля 2027 года