Задание 22. Информатика. ЕГЭ. Шастин. 6.11.2024

(Л. Шастин) В файле содержится информация о совокупности \(N\) вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс \(B\) зависит от процесса \(A\), если для выполнения процесса \(B\) необходимы результаты выполнения процесса \(A\). В этом случае процессы могут выполняться только последовательно. Все процессы запускаются при первой же возможности, никакие задержки не допускаются. Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы — время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение \(0\).

Определите, какое количество процессов не может быть завершено за первые \(T=100\) мс с момента запуска первого процесса.

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

ID процесса B	Время выполнения процесса B (мс)	ID процесса(-ов) A
1	2	0
2	4	0
3	1	1;2
4	7	3

Для приведённого выше примера при \(T=6\) мс процессы № 1, 2 и 3 успеют завершиться, если каждый из них будет запущен при первой же возможности. Процесс же №4 в лучшем случае успеет завершиться только по прошествии \(12\) мс. Ответ для примера: \(1.\)