Задания
Версия для печати и копирования в MS Word
Тип 22 № 83180
i

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

Опре­де­ли­те ID про­цес­са, ко­то­рый может на­чать своё вы­пол­не­ние по­след­ним, при усло­вии, что все не­за­ви­си­мые друг от друга про­цес­сы могут вы­пол­нять­ся па­рал­лель­но, а время за­вер­ше­ния всех про­цес­сов ми­ни­маль­но. Если таких про­цес­сов может быть не­сколь­ко, ука­жи­те мак­си­маль­но воз­мож­ный ID та­ко­го про­цес­са.

За­да­ние 22

Спрятать решение

Ре­ше­ние.

На­ри­су­ем время вы­пол­ня­е­мых про­цес­сов:

Рас­ста­вим про­цес­сы по вре­ме­ни вы­пол­не­ния:

По­дви­нем про­цес­сы мак­си­маль­но впра­во, с усло­ви­ем, что время вы­пол­не­ния всей по­сле­до­ва­тель­но­сти не из­ме­нит­ся:

По­след­ни­ми на­чать свое вы­пол­не­ния могут про­цес­сы 103 и 116, мак­си­маль­но воз­мож­ный ID это про­цесс 116.

 

Ответ: 116.


Аналоги к заданию № 83152: 83180 Все