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

Задания

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

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

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

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

Задание 22

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

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

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

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

	A	B	C
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	10533	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
17	12254	38	0	38
18	12262	43	0	43

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

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

38	14710	17	0		17
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	0	84
49	10823	11	10397	17	28
50	12962	18	10465	28	46
51	12552	48	10486	0	48
52	11794	62	10553	38	100
53	13252	2	10553	38	40
54	11307	55	10746	0	55
55	11644	48	10746	0	48
56	10951	31	10934	75	106
57	11229	94	10951	106	200
58	11741	43	11025	0	43

В ячейку 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

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

Ответ: 30.

Приведем решение на языке 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] >= 100]))

Примечание.

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

№ п/п	№ задания	Ответ
1	58530	30

Ключ