(А. Носкин) В файле 22-31.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы -- время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0. При составлении таблицы была потеряна информация о том, после какого процесса А начался процесс В с ID = 12. Однако известно, что вся совокупности процессов завершилась за минимальное время 25 мс. Определите ID процесса, после которого начался процесс с ID = 12. В ответе укажите только число.
Типовой пример организации данных в файле:
| ID процесса B |
Время выполнения
процесса B (мс) |
ID процесса(ов) A |
| 1 |
4 |
0 |
| 2 |
3 |
0 |
| 3 |
1 |
1; 2 |
| 4 |
7 |
[?] |
В данном случае независимые процессы 1 и 2 могут выполняться параллельно, при этом процесс 1 завершится через 4 мс, а процесс 2 -- через 3 мс с момента старта. Процесс 3 может начаться только после завершения обоих процессов 1 и 2, то есть, через 4 мс после старта. Он длится 1 мс и закончится через 4 + 1 = 5 мс после старта. Выполнение процесса 4 может начаться только после завершения процесса, ID которого потеряно. Его продолжительность равно 7 мс. Если бы минимальное время завершения всех процессов была равно 12 мс, то процесс 4 начинался бы после процесса 3 (12 -- 7 = 5мс).