Вдоль дороги длиной 10 км расположены дома. В течение дня жители отправляют в управляющую компанию заявки на уборку снега. В каждой заявке указано, с какой точки (в метрах от начала дороги) нужно начать уборку и какова длина участка (в метрах), который требуется очистить.
Если участки дороги в двух или более заявках имеют общую часть дороги, то можно выполнить не более одной из таких заявок. Если конец одного участка совпадает с началом другого, то нужно убрать оба участка.
Определите, наибольшее количество заявок, которые может выполнить управляющая компания, и в этом случае минимальную длину неубранного участка, расположенного в конце дороги (в метрах).
Входные данные
Первая строка входного файла содержит целое число N (N ⩽ 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.
ЕГКР по информатике 18 апреля 2026 – задание №26
Разбор полного решения задания 26
Ниже приведён код решения:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
f = open('26.txt') n = int(f.readline()) a = [] for _ in range(n): s, l = map(int, f.readline().split()) e = s + l a.append((e, s)) a.sort() chosen = [] last = 0 for e, s in a: if s >= last: chosen.append((e, s)) last = e k = len(chosen) border = chosen[-2][0] mx = max(e for e, s in a if s >= border) print(k, 10000 - mx) |
Что означает каждая переменная
- s — начало участка, который нужно очистить;
- l — длина участка;
- e — конец участка;
- a — список всех заявок;
- chosen — список заявок, выбранных жадным алгоритмом;
- last — конец последнего выбранного участка;
- k — максимальное количество заявок, которое можно выполнить;
- border — конец предпоследнего выбранного участка;
- mx — максимально возможный конец последнего участка.
1. Чтение входных данных
|
1 2 3 |
f = open('26.txt') n = int(f.readline()) a = [] |
Открываем файл 26.txt.
В первой строке файла записано число n — количество заявок.
Создаём пустой список a, в который будем сохранять все заявки.
2. Преобразование заявок в отрезки
|
1 2 3 4 |
for _ in range(n): s, l = map(int, f.readline().split()) e = s + l a.append((e, s)) |
В каждой строке файла записаны два числа:
- s — место, где начинается участок;
- l — длина участка.
Дальше вычисляем:
|
1 |
e = s + l |
Это конец участка.
Заявку сохраняем в виде пары (e, s), то есть сначала конец, потом начало.
Почему именно так?
Потому что дальше мы будем сортировать заявки по концу участка. Для жадного алгоритма это самый удобный вариант.
Почему здесь используется именно e = s + l, а не s + l - 1?
В этой задаче удобно рассматривать участок как полуинтервал: начало включается, а конец не включается. Тогда две заявки не пересекаются, если следующая начинается в точке, где закончилась предыдущая. Именно поэтому дальше проверка будет такой:
|
1 |
s >= last |
3. Сортировка заявок
|
1 |
a.sort() |
После этой команды список заявок сортируется по возрастанию.
Так как каждая заявка записана как (e, s), сортировка идёт:
- сначала по концу участка;
- если концы равны — по началу.
Зачем сортировать по концу?
Это основа жадного алгоритма: чтобы выбрать максимальное количество непересекающихся отрезков, нужно каждый раз брать тот, который заканчивается раньше других.
4. Жадный выбор максимального числа заявок
|
1 2 |
chosen = [] last = 0 |
Создаём пустой список chosen. В него будем записывать те заявки, которые выбрали.
Переменная last хранит конец последнего выбранного участка. Сначала она равна 0, то есть дорога ещё свободна с самого начала.
|
1 2 3 4 |
for e, s in a: if s >= last: chosen.append((e, s)) last = e |
Перебираем все заявки в порядке возрастания их конца.
Для каждой заявки проверяем условие:
|
1 |
if s >= last: |
Это означает, что новая заявка начинается не раньше, чем закончилась предыдущая выбранная. Значит, пересечения нет, и такую заявку можно взять.
Если заявка подходит, то:
- добавляем её в список
chosen; - обновляем
last, теперь это конец новой выбранной заявки.
Почему этот жадный алгоритм даёт максимальное количество заявок?
Потому что, выбирая каждый раз заявку с самым ранним концом, мы оставляем как можно больше места для следующих заявок.
5. Нахождение максимального количества заявок
|
1 |
k = len(chosen) |
После завершения жадного прохода в списке chosen находятся все выбранные заявки.
Количество этих заявок:
|
1 |
k = len(chosen) |
Это и есть ответ на первую часть задачи: максимальное количество заявок, которое можно выполнить без пересечений.
6. Почему недостаточно только жадного алгоритма
Жадный алгоритм правильно находит максимальное количество заявок.
Но задача требует ещё и второй ответ:
при максимальном количестве заявок нужно сделать так, чтобы неочищенный участок в конце дороги был минимальным.
Это означает, что среди всех решений с тем же количеством заявок нужно выбрать то, где последняя выбранная заявка заканчивается как можно правее.
7. Что такое border
|
1 |
border = chosen[-2][0] |
chosen[-2] — это предпоследняя выбранная заявка.
[0] — её конец, потому что каждая заявка хранится как (e, s).
Значит, border — это конец предпоследнего выбранного участка.
Почему берём именно предпоследний участок?
Потому что первые k — 1 заявок уже удобно зафиксировать жадным алгоритмом. Они заканчиваются как можно раньше и оставляют максимум места для последней заявки.
Теперь остаётся подобрать последнюю, k-ю заявку так, чтобы она:
- не пересекалась с предпоследней;
- заканчивалась как можно правее.
8. Поиск лучшей последней заявки
|
1 |
mx = max(e for e, s in a if s >= border) |
Здесь мы перебираем все заявки из списка a и оставляем только те, которые можно поставить после предпоследнего участка:
|
1 |
if s >= border |
То есть их начало не раньше конца предпоследней заявки.
Из всех таких заявок выбираем ту, у которой конец максимальный:
|
1 |
max(e ...) |
Таким образом, mx — это самый правый конец дороги, до которого можно дойти, сохранив то же максимальное количество заявок.
9. Вывод ответа
|
1 |
print(k, 10000 - mx) |
Первое число:
- k — максимальное количество заявок.
Второе число:
- 10000 — mx — длина неочищенного участка в конце дороги.
Если последняя выбранная заявка заканчивается в точке mx, то от неё до конца дороги остаётся 10000 - mx метров.
Итоговая идея решения
- Считываем все заявки и переводим их в отрезки.
- Сортируем отрезки по правому концу.
- Жадным алгоритмом находим максимальное количество непересекающихся заявок.
- Фиксируем первые k — 1 заявок.
- Среди всех возможных последних заявок выбираем ту, которая заканчивается дальше всего.
- Выводим количество заявок и длину оставшегося неочищенного участка.
Коротко
Сначала находим максимум заявок, затем улучшаем последнюю заявку так, чтобы она заканчивалась как можно правее.
ИЛИ — (EXCEL)
Решение задания 26 в Excel (по таблице)
Рассмотрим решение задачи прямо в Excel по таблице.
Структура таблицы:
- A — start (начало участка)
- B — length (длина)
- C — end (конец участка)
- D — конец последнего выбранного отрезка
- E — количество выбранных заявок
- F — максимальное количество заявок (k)
- G — k-1
- H — border (конец предпоследнего отрезка)
- I — максимально возможный конец
- J — длина неубранного участка
1. Находим конец каждого участка
В ячейке C2:
|
1 |
=A2+B2 |
Протягиваем вниз.
Важно: после этого нужно отсортировать таблицу по столбцу C (по возрастанию).
2. Жадный выбор заявок
В столбце D храним конец последнего выбранного отрезка.
В D2:
|
1 |
=C2 |
В E2:
|
1 |
=1 |
Далее:
D3:
|
1 |
=ЕСЛИ(A3>=D2;C3;D2) |
E3:
|
1 |
=ЕСЛИ(A3>=D2;E2+1;E2) |
Протягиваем вниз.
В результате столбец E показывает, сколько заявок можно выбрать.
3. Находим максимальное количество заявок
В ячейке F2:
|
1 |
=МАКС(E:E) |
В вашем случае:
k = 77
4. Находим k-1
В G2:
|
1 |
=F2-1 |
Получаем:
76
5. Находим border
Это конец предпоследнего выбранного отрезка.
В H2:
|
1 |
=МАКС(ЕСЛИ(E:E=G2;D:D)) |
Формула:
- находит строки, где выбрано ровно k-1 заявок
- берёт из них значения столбца D
- выбирает максимальное
В вашем случае:
border = 9531
6. Находим лучший последний отрезок
В I2:
|
1 |
=МАКС(ЕСЛИ(A:A>=H2;C:C)) |
Формула:
- берёт все отрезки, у которых start ≥ border
- среди них выбирает максимальный конец
В вашем случае:
mx = 9816
7. Находим длину неубранного участка
В J2:
|
1 |
=10000-I2 |
В вашем случае:
10000 — 9816 = 184
Итог
Ответ:
|
1 |
77 184 |
Коротко
1. Находим максимум заявок (жадный алгоритм)
2. Фиксируем первые k-1
3. Последний отрезок выбираем максимально вправо
Ответ: 77 184