Question

Дана таблица с информацией о вычислительных процессах. Каждый процесс имеет:
- идентификатор (столбец A);
- время выполнения в миллисекундах (столбец B);
- идентификаторы процессов-предшественников, от которых он зависит (столбец C); если процесс независим, указано 0.

Процесс может начать выполняться только после завершения всех своих предшественников. Независимые процессы выполняются параллельно.

Найдите минимальное время (в миллисекундах), необходимое для завершения всех процессов.

Accepted Answer

347

Answer

Идея решения: для каждого процесса вычислить время его завершения как максимум времён завершения всех предшественников плюс собственная длительность; ответ — максимальное время завершения среди всех процессов.

**Шаг 1.** Подготовим данные в электронной таблице. Разделим содержимое столбца C (список предшественников, разделённых точкой с запятой) на отдельные столбцы. Для этого используем функцию «Данные → Текст по столбцам» с разделителем «;». Получим таблицу, где каждый предшественник находится в отдельном столбце (например, столбцы D, E, F, …).

**Шаг 2.** Добавим вспомогательный столбец для вычисления времени завершения каждого процесса. В ячейку G2 введём формулу:

```
=МАКС(ВПР(D2;$A$1:$I$102;7;0);ВПР(E2;$A$1:$I$102;7;0))+B2
```

Эта формула:
- ищет время завершения каждого предшественника (из столбцов D и E) в таблице результатов (столбец G);
- берёт максимум из этих времён;
- добавляет время выполнения текущего процесса (столбец B).

Для обработки случаев, когда предшественников меньше двух, добавим в ячейку A102 значение 0, чтобы избежать ошибок при поиске.

**Шаг 3.** Скопируем формулу из G2 вниз до конца таблицы (G2:G101).

**Шаг 4.** Найдём максимальное значение в столбце G:

```
=МАКС(G2:G101)
```

Это значение — минимальное время завершения всей совокупности процессов.

![Рисунок](https://inf-ege.sdamgia.ru/get_file?id=180531)

Задание №22Алгоритмы и исполнителиЕГЭ по информатике