Дошкольникам
1 класс
2 класс
3 класс
4 класс
5 класс
6 класс
7 класс
8 класс
9 класс
10 класс
11 класс
ОГЭ
ЕГЭ
ВУЗ
Для всех
Назад

22. Вычислительные процессы: Это 3 процесса (за это время завершатся процессы 1, 2 и 4)

Задание #298200
Решено верно
Решено неверно
Сообщить о проблеме

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

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

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

ID процесса $B$Время выполнения процесса $B$ (мс)ID процесса(ов) $A$
$1$$3$$0$
$2$$4$$1$
$3$$2$$2$; $4$
$4$$5$$0$
$5$$8$$1$; $4$

Определите максимальное количество процессов, которые могут быть завершены за первые $17$ мс. Считать, что каждый процесс начинается в самое раннее допустимое время. Нумерация миллисекунд начинается с $1$.

Например, для приведённой таблицы найдём количество процессов, которые могут быть завершены за первые $7$ мс. Это $3$ процесса (за это время завершатся процессы $1$, $2$ и $4$).

Используя данные из файла, составим таблицу, на какой мс может закончиться каждый из процессов. Независимые процессы $106$, $113$ и $124$ завершатся на $2$, $5$ и $6$ мс соответственно. Процесс $114$ зависит от $106$, значит завершится на $2+3=5$ мс. Процесс $110$ зависит от $124$ и $106$: позже заканчивается $124$ (на $6$ мс), поэтому $110$ завершится на $6+2=8$ мс. От процесса $110$ зависят сразу три процесса — $103$, $116$ и $122$, и все они завершатся на $8+6=14$ мс.

Процесс $101$ зависит от $106$ и $122$, позже заканчивается $122$, значит $101$ завершится на $14+1=15$ мс; процесс $111$ зависит от $116$ и завершится на $14+1=15$ мс. Процесс $107$ зависит от $116$ и выполнится на $14+3=17$ мс, а процесс $121$ зависит от $106$ и $116$ — позже заканчивается $116$, поэтому $121$ тоже выполнится на $14+3=17$ мс. Все остальные процессы завершаются позже: ближайшие из них, $105$ и $125$, лишь на $18$ мс.

Таким образом, за первые $17$ мс успевают завершиться процессы $106$, $113$, $114$, $124$, $110$, $103$, $116$, $122$, $101$, $111$, $107$ и $121$ — всего $12$ процессов.

Время, мсID процесса
$2$$106$
$5$$113$, $114$
$6$$124$
$8$$110$
$14$$103$, $116$, $122$
$15$$101$, $111$
$17$$107$, $121$
$18$$105$, $125$
$19$$118$
$20$$112$, $119$
$22$$104$, $120$
$23$$102$
$24$$109$
$25$$108$
$26$$117$
$28$$123$
$29$$115$

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

import pandas as pd
from functools import lru_cache

df = pd.read_excel('22-02.ods', engine='odf', header=None, skiprows=1)

t, dep = {}, {}
for _, row in df.iterrows():
    pid = int(row[0])
    t[pid] = int(row[1])
    s = str(row[2]).strip()
    dep[pid] = [] if s == '0' else [int(x) for x in s.split(';')]

@lru_cache(None)
def finish(p):                        # момент завершения процесса p
    return t[p] + max([finish(d) for d in dep[p]], default=0)

print(sum(1 for p in t if finish(p) <= 17))   # 12

Процесс не может стартовать раньше, чем закончатся все, от которых он зависит, но и ждать дольше незачем — значит время его завершения равно собственной длительности плюс максимум по временам завершения предшественников. Рекурсия с кэшированием считает это за один проход, а дальше остаётся сосчитать процессы, у которых время завершения не превышает $17$.

Показать
Очки опыта 20
Спросить Зави
0 заданий сегодня

Предложить улучшение