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

Задания

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

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

Определите количество процессов, выполнение которых начнётся не ранее чем через 80 мс после запуска первого процесса.

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

Задание 22

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

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

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

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

	A	B	C	D	E	F	G
1	ID процесса	Время выполнения процесса (мс)	ID поставщиков данных
2	10068	23	0				23
3	10095	27	0				27
4	10158	67	0				67
5	10397	17	0				17
6	10465	28	0				28
7	10553	38	0				38
8	10646	2	0				2
9	10934	75	0				75
10	11054	14	0				14
11	11433	90	0				90
12	11549	54	0				54
13	11885	97	0				97
14	12003	3	0				3
15	12071	9	0				9
16	12215	98	0				98

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

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

39	14791	82	0		82
40	14876	46	0		46
41	10109	58	10068	23	81
42	12031	38	10068	23	61
43	14308	89	10068	23	112
44	10559	14	10095	27	41
45	10894	22	10095	27	49
46	11366	56	10095	27	83
47	10324	71	10109	81	152
48	13066	84	10255	86	170
49	10823	11	10397	17	28
50	12962	18	10465	28	46
51	12552	48	10486	101	149
52	11794	62	10553	38	100
53	13252	2	10553	38	40
54	11307	55	10746	59	114
55	11644	48	10746	59	107
56	10951	31	10934	75	106
57	11229	94	10951	106	200
58	11741	43	11025	142	185
59	11948	22	11025	142	164
60	14568	57	11054	14	71
61	12027	6	11307	114	120
62	13154	5	11307	114	119
63	13370	10	11644	107	117
64	14126	61	11644	107	168
65	14889	98	11644	107	205

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

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

77	15211	41	14594		81		122
78	10746	32	10068	10095	23	27	59
79	11025	93	10095	10894	27	49	142
80	10255	5	10109	10158	81	67	86
81	10486	15	10109	10255	81	86	101
82	11176	6	10109	10553	81	38	87
83	11218	11	10109	11148	81	143	154
84	11148	1	10486	11025	101	142	143
85	12099	32	10746	11148	59	143	175
86	12570	24	10934	11741	75	185	209
87	12838	5	11025	11885	142	97	147
88	12708	44	11054	12236	14	167	211
89	11521	57	11229	11307	200	114	257
90	12436	3	11229	12367	200	74	203
91	13377	46	11433	13351	90	68	136
92	12800	8	11644	12116	107	180	188
93	13885	86	11741	12116	185	180	271
94	13900	86	12071	12967	9	183	269
95	15023	57	12116	13256	180	19	237
96	13477	83	12254	12570	38	209	292
97	12746	11	12254	12615	38	8	49
98	13655	55	12436	13477	203	292	347
99	13554	51	12746	12967	49	183	234
100	13637	84	13538	13554	3	234	318
101	14960	88	14254	14889	54	205	293

В столбце H будем выписывать время начала процесса, для этого в ячейку H2 введем формулу =G2-B2 и скопируем ее на диапазон H2:H101. Окончательно, воспользовавшись формулой =СЧЁТЕСЛИ(H:H;">80"), получим ответ  — 39.

Ответ: 39.

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

f = list(map(lambda x: list(map(int, x.replace(';',' ').split())), open('22.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) - sl[i][0] >= 80]))

Примечание.

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

№ п/п	№ задания	Ответ
1	58489	39

Ключ