РЕШУ ЕГЭ — информатика

Задания

В компьютерной системе необходимо выполнить некоторое количество вычислительных процессов, которые могут выполняться параллельно или последовательно. Для запуска некоторых процессов необходимы данные, которые получаются как результаты выполнения одного или двух других процессов  — поставщиков данных. Независимые процессы (не имеющие поставщиков данных) можно запускать в любой момент времени. Если процесс B (зависимый процесс) получает данные от процесса A (поставщика данных), то процесс B может начать выполнение сразу же после завершения процесса A. Любые процессы, готовые к выполнению, можно запускать параллельно, при этом количество одновременно выполняемых процессов может быть любым, длительность процесса не зависит от других параллельно выполняемых процессов.

В таблице представлены идентификатор (ID) каждого процесса, его длительность и ID поставщиков данных для зависимых процессов.

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

Решение. Выполним сортировку данных по столбцу С.

Надо разделить данные в столбце «ID поставщиков данных» для тех процессов, где есть зависимость от двух процессов. Для этого выделим столбец С, далее  — меню «Данные  — Текст» по столбцам. В меню мастера разделения текста по столбцам последовательно выберем «Формат данных с разделителями», далее «Символ разделитель: точка с запятой». Формат данных столбца «Общий».

В столбце G будем считать общее время выполнения процесса. Для всех ячеек, у которых ячейка в столбце С равна нулю, это значение будет равно значению в ячейке столбца В. Запишем в ячейку G2 формулу =B2 и скопируем её на диапазон G2:G40.

Получаем таблицу:

	A	B	C	G
1	ID процесса	Время выполнения процесса (мс)	ID поставщиков данных
2	10026	18	0	18
3	10123	4	0	4
4	10218	92	0	92
5	10251	10	0	10
6	10374	41	0	41
7	10423	44	0	44
8	10594	13	0	13
9	10629	59	0	59
10	11040	72	0	72
11	11125	19	0	19
12	11324	7	0	7
13	11593	42	0	42
14	11680	19	0	19
15	11777	93	0	93
16	12344	17	0	17
17	12607	7	0	7
18	12690	81	0	81
19	12858	28	0	28
20	12931	83	0	83
21	13015	75	0	75

В ячейку E41 запишем формулу =ВПР(C41;A:G;7;0) и скопируем ее на диапазон E41:E99. Данная формула выведет время процесса, от которого зависит текущий. В ячейку G41 запишем формулу =E41+B41, чтобы посчитать общее время выполнения процесса. Скопируем формулу на диапазон G41:G68.

Получаем таблицу:

39	15030	85	0		85
40	15058	27	0		27
41	11177	8	10026	18	26
42	11612	3	10026	18	21
43	10824	25	10123	4	29
44	10495	2	10218	92	94
45	11502	5	10374	41	46
46	13421	61	10374	41	102
47	13391	81	10423	44	125
48	14490	79	10423	44	123
49	10994	23	10594	13	36
50	10707	55	10629	59	114
51	11742	42	10629	59	101
52	10746	35	10707	114	149
53	10856	33	10707	114	147
54	10980	91	10824	29	120
55	11229	23	10856	147	170
56	12107	50	11177	26	76
57	13720	94	11422	0	94
58	12371	33	11502	46	79

В ячейку F78 запишем формулу =ВПР(D69;A:G;7;0) и скопируем ее на диапазон F78:F99. Данная формула выведет время второго процесса, от которого зависит текущий. В ячейку G69 запишем формулу =МАКС(E69:F69)+B69, чтобы посчитать общее время выполнения процесса. Скопируем формулу на диапазон G78:G99.

Получаем таблицу:

14833	80	13877		191		271
14685	51	14552		77		128
10208	41	10026	10123	18	4	59
10285	70	10026	10218	18	92	162
12783	28	10123	12521	4	186	214
11842	41	10208	10980	59	120	161
14552	31	10251	11502	10	46	77
13658	75	10251	12783	10	214	289
10954	40	10374	10856	41	147	187
11245	100	10594	11040	13	72	172
13159	97	10629	11593	59	42	156
11930	48	10707	10856	114	29	162
12299	44	10707	11040	114	72	158
12380	10	10856	11612	147	21	157
15078	20	10856	14964	147	82	167
11422	67	10954	11229	187	170	254
12460	32	10980	12371	120	79	152
12521	25	10994	11842	36	161	186
12024	99	11229	11245	170	172	271
13520	99	11324	12380	7	157	256
13440	29	11422	11971	254	122	283
11971	76	11502	11593	46	42	122
13340	20	11930	12024	162	271	291
12201	94	12024	12107	271	76	365

Окончательно, воспользовавшись формулой =СЧЁТЕСЛИ(G:G;"<=170"), получим ответ  — 72.

Ответ: 72.

Приведем решение на языке Python.

f = list(map(lambda x: list(map(int, x.replace(';',' ').split())), open('22 (1).txt').readlines()))

sl = {x[0]: x[1:] for x in f}

y = lambda x: sl[x][0] + max(y(i) for i in sl[x][1:]) if sl[x][-1] else sl[x][0]

print(len([1 for i in sl if y(i) <= 170]))

Примечание.

Приведенный файл требуется сохранить в формате txt и поместить в каталог с программой.

№ п/п	№ задания	Ответ
1	51991	72

Ключ