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

В файле со­дер­жит­ся ин­фор­ма­ция о со­во­куп­но­сти N вы­чис­ли­тель­ных про­цес­сов, ко­то­рые могут вы­пол­нять­ся па­рал­лель­но или по­сле­до­ва­тель­но. Будем го­во­рить, что про­цесс B за­ви­сит от про­цес­са A, если для вы­пол­не­ния про­цес­са B не­об­хо­ди­мы ре­зуль­та­ты вы­пол­не­ния про­цес­са A. В этом слу­чае про­цес­сы могут вы­пол­нять­ся толь­ко по­сле­до­ва­тель­но.

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

Ти­по­вой при­мер ор­га­ни­за­ции дан­ных в файле:

 

ID про­цес­са BВремя вы­пол­не­ния
про­цес­са B (мс)		ID про­цес­са(ов) A
140
230
311; 2
473

 

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

Вы­пол­ни­те за­да­ния, ис­поль­зуя дан­ные из файла ниже:

За­да­ние 22

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

Ре­ше­ние.

FG
Время, мсID про­цес­са
1
2
32
41
53
6
79
810
9
10
115
124
1311
146, 12
157
16
178

Ис­поль­зуя дан­ные из файла, со­ста­вим таб­ли­цу, на какой мс может за­кон­чит­ся каж­дый из про­цес­сов. Про­цес­сы с ID «1», «2», «9» и «10» не­за­ви­си­мые, по­это­му их вы­пол­не­ние за­кон­чит­ся на 4, 3, 7 и 8 мс со­от­вет­ствен­но. Про­цесс с ID «3» может вы­пол­нять­ся толь­ко после за­вер­ше­ния про­цес­сов с ID «1» и «2», по­это­му он может за­вер­шить­ся на 5 мс. Про­цес­сы с ID «4» и «5» за­ви­сят от про­цес­са с ID «3», зна­чит, они за­вер­шат­ся через 5 + 7  =  12 мс и 5 + 6  =  11 мс со­от­вет­ствен­но. Про­цесс с ID «6» за­ви­сит от про­цес­са с ID «5», зна­чит, он за­вер­шит­ся через 11 + 3  =  14 мс. Про­цесс с ID «7» за­ви­сит от про­цес­сов с ID «4» и «6», сле­до­ва­тель­но, по­сколь­ку про­цесс с ID «6» за­вер­шит­ся толь­ко на 14 мс, про­цесс с ID «7» вы­пол­нит­ся на 14 + 1  =  15 мс. Про­цесс с ID «8» за­ви­сит от про­цес­са с ID «7», зна­чит, он вы­пол­нит­ся на 15 + 2  =  17 мс. Про­цесс с ID «11» за­ви­сит от про­цес­са с ID «9», по­это­му он вы­пол­нит­ся на 7 + 6  =  13 мс. Про­цесс с ID «12» за­ви­сит от про­цес­са с ID «10», по­это­му он вы­пол­нит­ся на 8 + 6  =  14 мс.

Таким об­ра­зом, вся со­во­куп­ность про­цес­сов за­вер­шит­ся на 17 мс.

 

Ответ: 17.

 

При­ведём дру­гое ре­ше­ние на языке Python.

import sys

d = {'0': 0}

for elem in sys.stdin:

num, dur, *subs = elem.replace(';', ' ').split()

d[num] = max([d[i] for i in subs]) + int(dur)

print(max(d.values()))

 

За­пу­стив про­грам­му вво­дим дан­ные из таб­ли­цы по­строч­но, цифры в стро­ках раз­де­ля­ем про­бе­лом. За­кон­чив ввод всех строк таб­ли­цы не­об­хо­ди­мо на­жать CTRL + D.

 

При­ме­ча­ние.

За­ме­тим, что дан­ный спо­соб ра­бо­та­ет для любой таб­ли­цы, но уме­стен толь­ко для таб­лиц с не­боль­шим ко­ли­че­ством строк (про­цес­сов).

 

При­ведём дру­гое ре­ше­ние Ни­ки­ти­ной Ели­за­ве­ты на языке Python.

f = open("22.txt").read().split("\n")

m = {}

for i in f:

s = i.split()

if s[2] == '0':

m[s[0]] = int(s[1])

else:

w = s[2].split(";")

sp = []

for j in w:

j = j.replace(" ", "")

sp.append(int(m[j]))

m[s[0]] = int(s[1]) + max(sp)

print(max(m.values()))

 

При­ме­ча­ние.

Дан­ные из таб­ли­цы не­об­хо­ди­мо со­хра­нить в тек­сто­вый до­ку­мент.

Источник: Де­мон­стра­ци­он­ная вер­сия ЕГЭ−2023 по ин­фор­ма­ти­ке
Спрятать решение · Помощь


О про­ек­те · Ре­дак­ция · Пра­во­вая ин­фор­ма­ция · О ре­кла­ме
© Гущин Д. Д., 2011—2026