Задание 26. Информатика. ЕГЭ 2026. ЕГКР. 18.04.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.\)

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)