Олимпиадный тренинг

Задача . ЕГЭ - 2025 - 2


Задача

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

Определите минимальное время (в мс), за которое завершатся 14 процессов. Считать, что каждый процесс начинается в самое раннее допустимое время. Минимальное время отсчитывается непрерывно с первой миллисекунды.
 
ID процесса B Время выполнения процесса B (мс) ID процесса(ов) A
1 3 0
2 4 1
3 2 2; 4
4 5 0
5 8 1; 4

Например, для приведённой таблицы найдём время, за которое завершатся 3 процесса. Минимальное время, которое для этого требуется, равно 7 мс. За это время завершатся процессы 1, 2 и 4.
 

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
Комментарий учителя