Задание 22 ЕГЭ информатика

Как это было в демоверсии 2027

Задание выполняется с использованием прилагаемого файла.

В файле содержится информация о совокупности $N$ вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс $B$ зависит от процесса $A$ , если для выполнения процесса $B$ необходимы результаты выполнения процесса $A$ . В этом случае процессы $A$ и $B$ могут выполняться только последовательно.

Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.

Определите максимальное количество процессов, которые параллельно выполняются на 7-й мс. Считать, что каждый процесс начинается в самое раннее допустимое время. Нумерация миллисекунд начинается с 1.

Типовой пример организации данных в файле

ID процесса B	Время выполнения процесса 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-й мс.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Файл к заданию 22

Источник: ФИПИ, проект демоверсии ЕГЭ 2027, с. 19

Решение и ответ

Процесс начинается сразу после того, как закончился последний из процессов, от которых он зависит. Если он закончился на $k$ -й мс, наш процесс занимает миллисекунды с $k + 1$ по $k + t$ .
В таблице: добавляем столбец «конец» = длительность + МАКС(концов процессов из списка зависимостей); для независимых конец = длительность. Процесс занимает миллисекунды с (конец − длительность + 1) по конец, значит, на 7-й мс он идёт, если конец − длительность < 7 ≤ конец.
То же программой (строки таблицы без заголовка скопированы в 22.txt):

t, dep = {}, {}
for s in open('22.txt'):          # строки таблицы без заголовка
    i, d, a = s.split()
    t[int(i)] = int(d)
    dep[int(i)] = [int(x) for x in a.split(';') if x != '0']

end = {}
def fin(i):                       # миллисекунда, на которой процесс закончится
    if i not in end:
        end[i] = max([fin(j) for j in dep[i]], default=0) + t[i]
    return end[i]

print(sum(1 for i in t if fin(i) - t[i] < 7 <= fin(i)))

На 7-й мс одновременно идут 8 процессов.

Ответ: 8