Задание 22 ЕГЭ по информатике 2027 — сколько процессов идёт на k-й миллисекунде
Разбор задания 22 ЕГЭ по информатике 2027: таблица процессов с 0 у независимых и зависимостями вперемешку, вопрос «сколько процессов выполняются на 7-й мс» (ответ 8). Расписание на Python, перенос данных из таблицы в текст и ловушка сдвига на единицу.
Задание 22 в 2027 году задаёт новый вопрос к знакомой таблице процессов: сколько процессов параллельно выполняются на k-й миллисекунде. В демоверсии ФИПИ это 7-я миллисекунда и ответ 8. Таблица та же, что в демо 2026: независимый процесс помечен нулём, а зависимости идут вперемешку — процесс 1 ждёт процессы 3 и 25, которые стоят в таблице ниже. Ниже — условие демо, расчёт расписания, разбор типового примера из условия руками, код на Python, который печатает 8, и ловушка сдвига на единицу.
Вопрос «минимальное время выполнения всех процессов» разобран в статье о задании 22, включая решение в LibreOffice Calc. Расписание там считается так же; отличается вопрос.
Условие демоверсии 2027
В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Процесс B зависит от процесса A, если для выполнения B нужны результаты A; тогда они выполняются только последовательно.
Таблица в файле: ID процесса, время его выполнения в миллисекундах, ID процессов, от которых он зависит, через «;». Если процесс независимый, в таблице указано значение 0.
Определите максимальное количество процессов, которые параллельно выполняются на 7-й мс. Считать, что каждый процесс начинается в самое раннее допустимое время. Нумерация миллисекунд начинается с 1.
Типовой пример из условия:
| ID процесса B | Время выполнения (мс) | ID процесса(-ов) A |
|---|---|---|
| 1 | 3 | 0 |
| 2 | 4 | 1 |
| 3 | 2 | 2; 4 |
| 4 | 5 | 0 |
| 5 | 8 | 1; 4 |
| 6 | 3 | 1 |
Для этой таблицы процесс 3 начинается на 8-й мс и заканчивается на 9-й. Ответ ФИПИ для файла демо: 8.
Расписание: когда процесс стартует и заканчивается
Каждый процесс стартует, как только закончился последний из тех, от кого он зависит, а независимые — в нулевой момент. Время окончания — старт плюс длительность. Если старт процесса — момент 7 (то есть предшественники закончились к концу 7-й мс), а длительность 2, то он занимает 8-ю и 9-ю миллисекунды: с begin + 1 по finish включительно.
Типовой пример из условия целиком:
| Процесс | Ждёт | Старт (момент) | Конец (момент) | Занятые мс |
|---|---|---|---|---|
| 1 | — | 0 | 3 | 1–3 |
| 4 | — | 0 | 5 | 1–5 |
| 2 | 1 | 3 | 7 | 4–7 |
| 6 | 1 | 3 | 6 | 4–6 |
| 5 | 1, 4 | 5 | 13 | 6–13 |
| 3 | 2, 4 | 7 | 9 | 8–9 |
Процесс 3 ждёт процессы 2 (конец 7) и 4 (конец 5) — старт в момент 7, занимает 8-ю и 9-ю мс, как и сказано в условии. На 7-й мс идут процессы 2 (4–7) и 5 (6–13) — два процесса. На 8-й — процессы 5 и 3, тоже два.
Демо-файл: 25 процессов и 17 миллисекунд
В файле демо 25 процессов, независимых три — 17, 22 и 25. Процесс 1 длится 4 мс и ждёт процессы 3 и 25; процесс 2 длится 3 мс и ждёт 8, 6 и 15. Всё расписание укладывается в 17 мс, а число одновременно идущих процессов по миллисекундам такое:
| Мс | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10–12 | 13 | 14 | 15–16 | 17 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Процессов | 3 | 3 | 4 | 4 | 6 | 8 | 8 | 8 | 7 | 7 | 5 | 4 | 2 | 1 |
На 7-й мс — 8 процессов. Обрати внимание: 8 держится с 6-й по 8-ю мс, а на 5-й и 9-й уже 6 и 7. Сдвиг на одну миллисекунду в этом демо ответ не меняет, но в банке заданий k выбирают так, чтобы менял, — считай точно.
Другие вопросы на том же примере
Расписание типового примера отвечает и на вопросы прошлых лет, и на «k-ю мс» при любом k:
| Мс | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10–13 |
|---|---|---|---|---|---|---|---|---|---|---|
| Процессов | 2 | 2 | 2 | 3 | 3 | 3 | 2 | 2 | 2 | 1 |
Минимальное время выполнения всех процессов — 13 мс (конец процесса 5). Наибольшее число одновременных процессов — три, на 4–6-й мс: на 4-й и 5-й идут 2, 4 и 6, на 6-й — 2, 5 и 6. На 7-й мс — два, как посчитано выше. Один раз построив расписание, дальше меняют только вопрос.
Решение на Python
ФИПИ в инструкции называет только категории программ — текстовый редактор, редактор таблиц и системы программирования, а в опубликованных регионами перечнях ПО — сами среды Python, без сторонних библиотек. Рассчитывать на odfpy на экзамене нельзя. Прочитать .ods стандартными средствами можно (это zip-архив с XML), но неудобно, поэтому данные сначала переносят в текст: открой файл в редакторе таблиц, выдели строки с данными, скопируй и вставь в новый текстовый файл 22.txt — столбцы разделятся табуляцией. Нуль в зависимостях отбрасываем, времена считаем повторными проходами, пока не посчитаны все процессы.
K = 7
rows = []
for line in open("22.txt"): # строки таблицы, скопированные в текстовый файл
cells = line.rstrip("\n").split("\t")
if cells[0].strip().isdigit(): # пустые строки и случайный заголовок пропускаем
rows.append(cells)
dur = {}
deps = {}
order = []
for cells in rows:
i = int(cells[0])
order.append(i)
dur[i] = int(cells[1])
deps[i] = []
tail = cells[2].strip()
if tail != "0": # 0 — независимый процесс
for d in tail.split(";"):
deps[i].append(int(d))
begin = {}
finish = {}
while len(finish) < len(order): # пока не посчитаны все
progress = False
for i in order:
if i in finish:
continue
start = 0
ready = True
for d in deps[i]:
if d not in finish:
ready = False
elif finish[d] > start:
start = finish[d]
if ready:
begin[i] = start
finish[i] = start + dur[i]
progress = True
if not progress: # за проход ничего не посчитано — данные прочитаны неверно
raise ValueError("не все процессы посчитаны: проверь, как прочитан файл")
count = 0
for i in order:
if begin[i] + 1 <= K <= finish[i]: # миллисекунды с единицы
count += 1
print(count) # 8
Цикл while — ответ на зависимости вперемешку: за первый проход посчитаются независимые процессы и те, чьи предшественники уже известны, за следующие — остальные. Если за целый проход не посчитан ни один процесс, значит, какой-то процесс потерян при чтении или в данных круг — программа остановится с ошибкой, а не зависнет.
Последняя часть — сам вопрос: процесс идёт на k-й мс, если begin + 1 <= k <= finish. Для «минимального времени всех процессов» вместо неё печатают max(finish.values()), для момента старта процесса — begin[i].
Вместо копирования лист можно сохранить из Calc в CSV («Файл → Сохранить как», формат CSV, разделитель — табуляция, потому что в зависимостях уже стоит точка с запятой) — код чтения тот же.
В кабинете и дома: чтение .ods библиотекой odfpy
В Python-панели кабинета TuteMe и на домашнем компьютере с установленным odfpy файл можно прочитать напрямую — на экзамене так не получится. Одна тонкость: LibreOffice склеивает одинаковые соседние ячейки в одну с повтором. В демо у процесса 4 номер и время равны 4 и записаны одной ячейкой, поэтому повтор нужно разворачивать — иначе процесс 4 теряется: на 7-й мс ответ случайно остаётся 8, а на 13–16-й выходит 4, 3, 1, 1 вместо 5, 4, 2, 2. Вместо блока чтения 22.txt:
from odf.opendocument import load
from odf.table import Table, TableRow, TableCell
sheet = load("demo_22.ods").spreadsheet.getElementsByType(Table)[0]
rows = []
for row in sheet.getElementsByType(TableRow):
cells = []
for cell in row.getElementsByType(TableCell):
repeat = int(cell.getAttribute("numbercolumnsrepeated") or 1)
cells += [str(cell)] * min(repeat, 3) # разворачиваем склеенные ячейки
if cells and cells[0].strip().isdigit():
rows.append(cells[:3])
Дальше код тот же. Приёмы работы с таблицами на экзамене — в справочнике по Calc.
Типичные ошибки
Сдвиг на единицу
Процесс со стартом 7 и длительностью 2 занимает 8-ю и 9-ю мс, а не 7-ю и 8-ю. Условие begin + 1 <= k <= finish — ровно про это. Проверь шаблон на типовом примере из условия: там процесс 3 должен занять 8-ю и 9-ю.
Один проход по строкам
При зависимостях вперемешку один проход оставит часть процессов без времени, а шаблон, который читает finish[d] без проверки, упадёт с KeyError. Нужен цикл while до полного заполнения.
Нуль прочитан как процесс
«0» в столбце зависимостей — независимый процесс. Если не отделить нуль до int, в зависимостях появится несуществующий процесс 0 и цикл while не закончится.
Ответ на другой вопрос
Прежние варианты спрашивали минимальное время всех процессов или сколько процессов завершатся за первые N мс. Если по привычке напечатать max(finish.values()), получится 17, а не 8. Перечитай вопрос.
Заголовок таблицы попал в данные
Первая строка листа — заголовок. Если он попал в текстовый файл, проверка isdigit() по первой клетке его пропустит и не даст int упасть на тексте.
Подборка ошибок по всем номерам — в статье Типичные ошибки на ЕГЭ по информатике.
Тайминг на экзамене
| Этап | Время |
|---|---|
| Открыть файл, понять столбцы и k из условия | 1 мин |
Чтение таблицы и проходы while по шаблону | 2 мин |
| Подсчёт на k-й мс, проверка на типовом примере | 1–2 мин |
| Итого | 4–5 мин |
Спецификация отводит семь минут. Проверка на типовом примере из условия — полминуты, и она ловит сдвиг на единицу до того, как ответ ушёл в бланк.
Как тренироваться
- Реши пять заданий с вопросом про k-ю мс на таблицах с зависимостями вперемешку, проверяя себя ручным расписанием на 5–6 процессах.
- Три задания прошлых лет про минимальное время тем же шаблоном — меняется только последняя часть.
- Один раз посчитай миллисекунды с нуля и увидь, как уезжает ответ, — ловушка запомнится.
- Отработай перенос данных из таблицы в текст — на экзамене это путь для Python; чтение через odfpy в кабинете должно давать то же расписание.
Как изменились остальные номера — в обзоре ЕГЭ по информатике 2027: что изменилось; демозадание в контексте варианта — в разборе демоверсии 2027. Соседние задания с файлами-таблицами — задание 9 и задание 18.
Короткий итог
Задание 22 в 2027 году — та же таблица процессов, но вопрос «сколько процессов идёт на k-й мс», нуль у независимых и зависимости вперемешку. Расписание считают проходами while, миллисекунды — с единицы, процесс занимает мс с begin + 1 по finish. На демо-файле ответ 8.
Задания 22 в форме демоверсии 2027 с автопроверкой есть в TuteMe: файлы .ods с нулём у независимых, зависимости вперемешку, вопрос про k-ю миллисекунду, и k подобран так, что сдвиг на миллисекунду меняет ответ.