В 2025 году в ЕГЭ по информатике была довольно непростая задача №26 на имитационное моделирование. Нужно было воспроизвести логику распределения заявок по окнам в реальном времени, учитывая:
- порядок поступления заявок (по времени начала),
- правило «свободное окно с минимальным номером»,
- запрет на прерывание приёма,
- и то, что новый посетитель может начать приём только с следующей минуты после завершения предыдущего.
Решить её в LibreOffice Calc практически невозможно — слишком много условий, зависимостей и пересчётов.
Но в Python — это простой и надёжный алгоритм, который мы уже реализовали.
Давайте разберём решение — с полным объяснением почему каждая строка нужна и как она работает.
📌 Условие задачи
Входной файл содержит информацию о заявках граждан, обращающихся во многофункциональный центр (МФЦ) в течение календарных суток. В заявке указаны время начала и время окончания приёма специалистом (в минутах от начала суток).
Рабочие места специалистов МФЦ (окна) пронумерованы натуральными числами начиная с 1. Приём одного гражданина ведёт свободный специалист в окне с минимальным номером. Новый посетитель может обратиться к освободившемуся специалисту начиная со следующей минуты после завершения приёма предыдущего. Если в момент обращения в МФЦ свободных специалистов нет, то гражданин уходит. Определите, сколько граждан смогут попасть на приём в МФЦ в течение 24 ч, и каков номер окна специалиста, который начнёт принимать посетителя последним. Если таких окон несколько, укажите наименьший номер окна.
Входные данные
В первой строке входного файла находится натуральное число К, не превышающее 1000, - количество окон в МФЦ. Во второй строке
натуральное число N (N ≤ 10 000), обозначающее количество граждан. Каждая из следующих N строк содержит два натуральных числа, каждое из которых не превышает 1440: указанные в заявке время начала и время окончания приёма (в минутах от начала суток).
Запишите в ответе два числа: количество граждан, которые смогут воспользоваться услугами МФЦ, и номер окна, в котором специалист примет последнего гражданина.
Типовой пример организации данных во входном файле
2
5
30 60
40 100
59 60
61 100
101 144
При таких исходных данных воспользоваться услугами МФЦ смогут первый, второй, четвёртый и пятый граждане. Наименьший номер окна, где последний из граждан будет принят специалистом, - 1, так как будут свободны окна 1 и 2.
📌 Условие задачи кратко
- Есть K окон (специалистов), пронумерованных от 1 до K.
- Приходят N граждан с заявками: [начало, конец] (в минутах от 00:00).
- Заявки обрабатываются в порядке поступления — но в файле они могут быть в любом порядке, поэтому сортируем по времени начала.
- Приём одного гражданина занимает [st, fin) — то есть до fin включительно? Нет!
→ В условии сказано: «Новый посетитель может обратиться к освободившемуся специалисту начиная со следующей минуты после завершения приёма предыдущего».
→ Значит: если предыдущий закончил в fin = 60, то следующий может начать с 61-й минуты.
🔑 Ключевой момент: окно свободно в момент t, если okna[i] < t, а не <=.
Это — основа всего алгоритма.
✅ Код решения — построчное объяснение
Открываем входной файл.
Имя файла — МФЦ.txt
На экзамене файл будет называться 26.txt
Читаем первые две строки:K — количество окон (≤ 1000),
N — количество заявок (≤ 10 000).
Преобразуем в целые числа — это обязательно.
Читаем все оставшиеся строки (по одной на заявку): s.split() делит строку по пробелу → ['30', '60'],
[int(x) for x in ...] преобразует в числа → [30, 60],
сохраняем как список [st, fin] в общий список d.
💡 Почему именно так? Потому что:заявки могут идти в любом порядке (например, сначала 59 60, потом 30 60),
а мы должны обрабатывать их в порядке поступления, то есть по st (времени начала).
Сортируем список d по первому элементу (st) — это стандартная сортировка списков в Python.
После этого d[0] — заявка с самым ранним началом, d[1] — следующая и т.д.
⚠️ Важно: если у двух заявок одинаковое st, Python сохранит их в том порядке, в котором они были в файле — это допустимо, потому что в условии не сказано, как разрешать равенство.
Создаём массив okna, где индекс — номер окна (от 1 до K), значение — момент окончания приёма в этом окне.
Инициализируем нулями: в начале суток все окна свободны (никто ещё не работал).
📌 Почему K+1, а не K?
Чтобы удобно обращаться к okna[1], okna[2], ..., okna[K] — без сдвига на -1.
okna[0] не используется, но это нормально.
count — счётчик успешно принятых граждан.
last — номер окна, в котором был принят последний гражданин.
Изначально — 0 (ещё никто не был принят).
Это — ядро алгоритма. Разберём его по шагам:
Шаг 1: берём текущую заявку (st, fin)
Мы обрабатываем заявки по порядку — сначала те, кто пришёл раньше.
Шаг 2: перебираем окна от 1 до K
for i in range(1, K+1) — именно в этом порядке, потому что:
«Приём одного гражданина ведёт свободный специалист в окне с минимальным номером».
Шаг 3: проверка if okna[i] < st
okna[i] — время, когда окно i освободится,
st — время начала приёма по заявке,
условие okna[i] < st означает: окно освободится до начала этой заявки → можно назначить.
🔑 Это ключевое условие.
Если бы было <=, то при okna[i] == st (окно освобождается в ту же минуту, что и начинается приём) — это запрещено по условию: «начиная со следующей минуты».
Поэтому строго <.
Шаг 4: назначаем заявку окну i
okna[i] = fin — теперь окно i будет занято до fin включительно,
count += 1 — увеличиваем счётчик успешных приёмов,
last = i — запоминаем номер окна, где сейчас приняли гражданина,
break — выходим из внутреннего цикла, потому что нашли первое (минимальное) свободное окно — больше искать не нужно.
✅ Именно этот break делает алгоритм эффективным: мы не проверяем все окна, а только до первого подходящего.
Запись на занятия здесь: https://t.me/nka39
Код решения полностью
🧮 Как работает алгоритм на типовом примере
Входные данные:
- d = [[30,60], [40,100], [59,60], [61,100], [101,144]]
(уже отсортировано по st) - okna = [0, 0, 0] (индексы 0,1,2; используем 1 и 2)
- Обработка: Заявка [30,60]:
okna[1] = 0 < 30 → назначаем окно 1.
okna = [0, 60, 0], count=1, last=1.
Заявка [40,100]:
okna[1] = 60 ≥ 40 → окно 1 занято,
okna[2] = 0 < 40 → назначаем окно 2.
okna = [0, 60, 100], count=2, last=2.
Заявка [59,60]:
okna[1] = 60 ≥ 59 → нет,
okna[2] = 100 ≥ 59 → нет → гражданин уходит.
Заявка [61,100]:
okna[1] = 60 < 61 → да! Окно 1 освободилось в 60, новый приём может начаться с 61.
Назначаем окно 1.
okna = [0, 100, 100], count=3, last=1.
Заявка [101,144]:
okna[1] = 100 < 101 → да → окно 1 снова свободно.
Назначаем окно 1.
count=4, last=1.
Ответ: 4 1 — совпадает с условием.
✅ Итог: почему решение стоит использовать на экзамене
- Оно точно следует условию: сортировка по st, поиск окна с минимальным номером, проверка okna[i] < st, обновление okna[i] = fin, запоминание последнего окна.
- Оно эффективно: O(N·K) в худшем случае, но на практике — ближе к O(N),
break экономит время. - Оно понятно и воспроизводимо: ни одной «магической» строки,
каждая переменная имеет ясный смысл, даже новичок может повторить алгоритм.
Готовы к следующей задаче? Или хотите разбор другого прототипа? Пишите в комментариях!
Если Вам информация была для Вас полезна, то можно поддержать автора, нажав на кнопку "Поддержать".
Подпишитесь на канал и научитесь решать все задания ЕГЭ по информатике!
Удачи на экзамене!
Записаться ко мне на занятия можно тут https://t.me/nka39