В компьютерной системе необходимо выполнить некоторое количество вычислительных процессов, которые могут выполняться параллельно или последовательно. Для запуска некоторых процессов необходимы данные, которые получаются как результаты выполнения одного или двух других процессов — поставщиков данных. Независимые процессы (не имеющие поставщиков данных) можно запускать в любой момент времени. Если
В таблице представлены идентификатор (ID) каждого процесса, его длительность и ID поставщиков данных для зависимых процессов.
Определите, за какое минимальное время можно выполнить все процессы. В ответе запишите целое число — минимальное время в мс.
Для начала проведем сортировку данных, чтобы отделить не зависимые процессы, зависимые от одного процесса и зависимые от двух процессов вычисления. Для этого выделим первые три столбца, а затем выберем меню «Данные — Сортировка» и отсортируем по возрастанию.
Далее нам надо разделить данные в столбце «ID поставщиков данных» для тех процессов, где есть зависимость от двух процессов. Для этого выделим
В столбце E будем считать общее время на выполнение процесса. Для независимых процессов перенесем данные
Теперь посчитаем время у процессов зависящих от одного процесса. Для этого
Далее будем считать время процессов, зависящих от
=B38+5+МАКС(ВПР(C38;A:E;5;0);ВПР(D38;A:E;5;0)).
Скопируем формулу во все ячейки диапазона E38:E66.
Найдем самый длительный процесс введя формулу =МАКС(E2:E101), это и будет минимальное время выполнения всех процессов.
Ответ: 597.
Приведём решение Михаила Глинского на языке Python.
res={'0':0}
f=open('22.txt')
for s in f:
n,t,*FF=s.split()
if len(FF)==0:
res[n]=int(t)
else:
res[n]=int(t)+max([res[i]for i in FF])+5
print(max(res.values()))
Примечание. Предварительно удаляем в файле 1 строку и делаем «Данные»>«Текс по столбцам»>разделители ";".
Cохраняем текст как текст MSDOS.