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

ЕГЭ, Информатика: 22. Вычислительные процессы: все задания

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

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

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

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

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

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

Используя данные из файла, составим таблицу, на какой мс может закончиться каждый из процессов. Независимые процессы $10$, $4$, $1$, $14$ и $2$ завершатся на $16$, $17$, $22$, $22$ и $24$ мс соответственно.

Процесс $5$ зависит от $1$ и $2$: позже заканчивается $2$ (на $24$ мс), значит $5$ завершится на $24+18=42$ мс. Процесс $16$ зависит от $14$ и тоже завершится на $22+20=42$ мс. Процесс $3$ зависит от $1$ и $2$ и завершится на $24+24=48$ мс.

Процесс $6$ зависит от $4$ и $5$, позже заканчивается $5$, поэтому $6$ завершится на $42+15=57$ мс. Процесс $7$ зависит от $1$, $4$ и $6$: позже всех $6$, значит $7$ завершится на $57+17=74$ мс. Процесс $9$ зависит от $2$ и $6$ и завершится на $57+19=76$ мс, процесс $11$ зависит от $4$ и $7$ и завершится на $74+18=92$ мс.

Процесс $8$ зависит от $3$, $5$ и $7$: позже всех заканчивается $7$ (на $74$ мс), поэтому $8$ завершится на $74+22=96$ мс. От него зависят $13$ и $12$. Процесс $13$ зависит от $5$, $8$ и $10$ и завершится на $96+19=115$ мс, процесс $12$ зависит от $8$ и завершится на $96+22=118$ мс. Процесс $17$ зависит от $12$ и завершится на $118+15=133$ мс.

Наконец, процесс $15$ зависит от $13$ и $14$: позже заканчивается $13$ (на $115$ мс), значит $15$ завершится на $115+21=136$ мс. Это позже, чем процесс $17$, поэтому именно $15$ и определяет ответ.

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

Время, мсID процесса
$16$$10$
$17$$4$
$22$$1$, $14$
$24$$2$
$42$$5$, $16$
$48$$3$
$57$$6$
$74$$7$
$76$$9$
$92$$11$
$96$$8$
$115$$13$
$118$$12$
$133$$17$
$136$$15$

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

import pandas as pd
from functools import lru_cache

df = pd.read_excel('22-21.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]).replace(' ', '').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(max(finish(p) for p in t))   # 136

Здесь две длинные ветки расходятся после процесса $8$: одна идёт через $12$ и $17$ и заканчивается на $133$ мс, другая через $13$ и $15$ — на $136$ мс. Поэтому нужен максимум по всем процессам, а не по какой-то одной цепочке. Обратите внимание и на разбор третьего столбца: зависимости в файле записаны с разными пробелами, их надо убрать перед разбиением по «;».

Показать
Очки опыта 20
Спросить Зави
22. Задание #298253
Решено верно
Решено неверно
Сообщить о проблеме

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

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

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

ID процесса $B$Время выполнения процесса $B$ (мс)ID процесса(-ов) $A$
$101$$4$$0$
$102$$3$$0$
$103$$1$$101$; $102$
$104$$7$$103$

Определите максимальную продолжительность отрезка времени (в мс), в течение которого возможно одновременное выполнение максимального количества процессов при условии, что все независимые друг от друга процессы могут выполняться параллельно.

Расписываем отрезок работы каждого процесса: он стартует сразу после окончания последнего из тех, от которых зависит, и занимает миллисекунды с $f-d+1$ по $f$, где $f$ — момент завершения, $d$ — длительность.

Независимые процессы $101$, $102$ и $109$ занимают мс $1$–$15$, $1$–$14$ и $1$–$8$. Процессы $110$ и $111$ зависят от $109$ и стартуют после $8$ мс: $110$ занимает мс $9$–$22$, $111$ — мс $9$–$14$. Процесс $113$ зависит от $111$ и занимает мс $15$–$22$. Процесс $103$ зависит от $101$ и $102$, позже заканчивается $101$ (на $15$ мс), значит $103$ занимает мс $16$–$18$. От него зависят $104$ (мс $19$–$21$) и $105$ (мс $19$–$33$), а от $104$ — процесс $106$ (мс $22$–$32$). Процесс $112$ зависит от $110$ и $111$ и занимает мс $23$–$35$, процесс $107$ — мс $34$–$38$, процесс $108$ — мс $39$–$46$.

Теперь считаем, сколько процессов идёт одновременно на каждой миллисекунде. Максимум равен $4$, и достигается он дважды. С $9$ по $14$ мс работают $101$, $102$, $110$ и $111$ — отрезок длиной $6$ мс; на $15$-й мс закончились $102$ и $111$, а добавился только $113$, и осталось три. Второй раз четвёрка набирается с $19$ по $22$ мс: сначала это $104$, $105$, $110$ и $113$, а на $22$-й мс вместо $104$ подключается $106$. Это отрезок длиной $4$ мс, на $23$-й мс процессы $110$ и $113$ заканчиваются, а добавляется только $112$.

Самый длинный отрезок — с $9$ по $14$ мс, его продолжительность $6$ мс.

ПроцессЗанятые мс
$101$$1$–$15$
$102$$1$–$14$
$109$$1$–$8$
$110$$9$–$22$
$111$$9$–$14$
$113$$15$–$22$
$103$$16$–$18$
$104$$19$–$21$
$105$$19$–$33$
$106$$22$–$32$
$112$$23$–$35$
$107$$34$–$38$
$108$$39$–$46$

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

import pandas as pd
from functools import lru_cache

df = pd.read_excel('22-22.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]).replace(' ', '').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)

T = max(finish(p) for p in t)
cnt = [0] * (T + 2)                   # сколько процессов идёт на каждой мс
for p in t:
    for ms in range(finish(p) - t[p] + 1, finish(p) + 1):
        cnt[ms] += 1

M = max(cnt[1:T+1])                   # максимум одновременных процессов

best = cur = 0                        # самая длинная цепочка мс со значением M
for ms in range(1, T + 1):
    cur = cur + 1 if cnt[ms] == M else 0
    best = max(best, cur)

print(best)   # 6

Спрашивается не про конкретный набор процессов, а про количество: во втором отрезке состав четвёрки на $22$-й мс меняется, но параллельных всё равно четыре. Вся совокупность процессов завершается на $46$ мс.

Показать
Очки опыта 20
Спросить Зави
23. Задание #298259
Решено верно
Решено неверно
Сообщить о проблеме

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

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

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

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

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

Используя данные из файла, составим таблицу, на какой мс может закончиться каждый из процессов. Независимые процессы $9$, $1$, $2$, $11$ и $4$ завершатся на $19$, $23$, $24$, $28$ и $29$ мс соответственно.

Процесс $3$ зависит от $2$, значит завершится на $24+25=49$ мс. Процесс $5$ зависит от $1$, $2$ и $3$: позже всех $3$, поэтому $5$ завершится на $49+26=75$ мс. Процесс $6$ зависит от $2$, $3$ и $4$ — здесь тоже позже всех $3$, значит $6$ завершится на $49+27=76$ мс.

Процесс $7$ зависит от $4$ и $6$, позже заканчивается $6$, поэтому $7$ завершится на $76+25=101$ мс. Процесс $13$ зависит от $4$, $5$, $9$ и $11$: позже всех $5$ (на $75$ мс), значит $13$ завершится на $75+34=109$ мс. Процесс $10$ зависит от $3$, $4$ и $7$ и завершится на $101+16=117$ мс. Процесс $8$ зависит от $3$, $5$, $6$ и $7$: позже всех $7$, поэтому $8$ завершится на $101+21=122$ мс.

Процесс $12$ зависит от $7$, $8$ и $11$: позже всех $8$ (на $122$ мс), значит $12$ завершится на $122+31=153$ мс. От него дальше идут две ветки: процесс $15$ зависит от $12$ и $13$ и завершится на $153+27=180$ мс, процесс $14$ зависит от $8$ и $12$ и завершится на $153+32=185$ мс.

Наконец, процесс $16$ зависит от $14$ и $15$: позже заканчивается $14$, поэтому $16$ завершится на $185+24=209$ мс. А процесс $17$ зависит от $10$, $11$ и $15$: позже всех $15$ (на $180$ мс), значит $17$ завершится на $180+33=213$ мс. Это и есть самое позднее время.

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

Время, мсID процесса
$19$$9$
$23$$1$
$24$$2$
$28$$11$
$29$$4$
$49$$3$
$75$$5$
$76$$6$
$101$$7$
$109$$13$
$117$$10$
$122$$8$
$153$$12$
$180$$15$
$185$$14$
$209$$16$
$213$$17$

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

import pandas as pd
from functools import lru_cache

df = pd.read_excel('22-23.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]).replace(' ', '').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(max(finish(p) for p in t))   # 213

Обратите внимание, что последним завершается не процесс с наибольшим номером в цепочке: $16$ заканчивается на $209$ мс, а $17$ — на $213$ мс, хотя стартует раньше. Поэтому и нужен максимум по всем процессам.

Показать
Очки опыта 20
Спросить Зави
24. Задание #298258
Решено верно
Решено неверно
Сообщить о проблеме

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

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

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

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

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

Используя данные из файла, составим таблицу, на какой мс может закончиться каждый из процессов. Независимые процессы $2$, $4$ и $1$ завершатся на $3$, $6$ и $8$ мс соответственно.

Процесс $3$ зависит от $1$ и $2$: позже заканчивается $1$ (на $8$ мс), значит $3$ завершится на $8+1=9$ мс. Процесс $6$ зависит от $3$ и завершится на $9+5=14$ мс. Процесс $5$ зависит от $3$ и $4$, позже заканчивается $3$, поэтому $5$ завершится на $9+7=16$ мс.

От процесса $5$ зависят два процесса: $8$ заканчивается на $16+9=25$ мс, $7$ — на $16+10=26$ мс. Процесс $9$ зависит от $8$ и завершится на $25+4=29$ мс, процесс $10$ зависит от $7$ и завершится на $26+4=30$ мс. Процесс $16$ зависит от $10$ и $9$: позже заканчивается $10$, значит $16$ завершится на $30+9=39$ мс.

Процесс $11$ зависит от $6$ и $7$: позже заканчивается $7$ (на $26$ мс), поэтому $11$ завершится на $26+8=34$ мс. От него зависят сразу три процесса: $13$ заканчивается на $34+4=38$ мс, $14$ — на $34+7=41$ мс, $12$ — на $34+9=43$ мс.

Наконец, процесс $15$ зависит от $12$, $13$ и $14$: позже всех заканчивается $12$ (на $43$ мс), значит $15$ завершится на $43+10=53$ мс.

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

Время, мсID процесса
$3$$2$
$6$$4$
$8$$1$
$9$$3$
$14$$6$
$16$$5$
$25$$8$
$26$$7$
$29$$9$
$30$$10$
$34$$11$
$38$$13$
$39$$16$
$41$$14$
$43$$12$
$53$$15$

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

import pandas as pd
from functools import lru_cache

df = pd.read_excel('22-24.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]).replace(' ', '').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(max(finish(p) for p in t))   # 53

Обратите внимание, что процесс $16$ заканчивается на $39$ мс, хотя стоит в таблице почти последним, а критический путь идёт через $1 \to 3 \to 5 \to 7 \to 11 \to 12 \to 15$ и упирается в $53$ мс. Поэтому нужен максимум по всем процессам, а не по последней строке таблицы.

Показать
Очки опыта 20
Спросить Зави
25. Задание #298265
Решено верно
Решено неверно
Сообщить о проблеме

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

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

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

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

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

Используя данные из файла, составим таблицу, на какой мс может закончиться каждый из процессов. Независимые процессы $1$, $2$, $11$, $4$ и $14$ завершатся на $17$, $18$, $21$, $24$ и $24$ мс соответственно.

Процесс $3$ зависит от $1$ и $2$: позже заканчивается $2$ (на $18$ мс), значит $3$ завершится на $18+19=37$ мс. Дальше на $56$ мс заканчиваются сразу два процесса: $5$ зависит от $1$ и $3$ и стартует после $37$ мс, а $6$ зависит от $2$, $3$ и $4$ — тоже после $37$ мс, поскольку $3$ заканчивается позже остальных.

Процесс $9$ зависит от $5$ и $6$, стартует после $56$ мс и завершится на $56+10=66$ мс. Процесс $7$ зависит от $1$, $4$ и $6$: позже всех $6$, поэтому $7$ завершится на $56+16=72$ мс. Процесс $10$ зависит от $3$, $6$ и $9$ и завершится на $66+11=77$ мс. Процесс $8$ зависит от $3$, $5$ и $7$: позже всех $7$, значит $8$ завершится на $72+15=87$ мс.

Процесс $13$ зависит от $5$, $9$ и $10$: позже всех $10$ (на $77$ мс), поэтому $13$ завершится на $77+29=106$ мс. Процесс $12$ зависит от $8$, $7$ и $11$, позже всех $8$, значит $12$ завершится на $87+22=109$ мс. Процесс $15$ зависит от $12$ и $13$ и завершится на $109+18=127$ мс.

Наконец, процесс $16$ зависит от $14$ и $15$ и завершится на $127+19=146$ мс, а процесс $17$ зависит от $10$, $12$ и $15$: позже всех $15$, поэтому $17$ завершится на $127+24=151$ мс. Это и есть самое позднее время.

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

Время, мсID процесса
$17$$1$
$18$$2$
$21$$11$
$24$$4$, $14$
$37$$3$
$56$$5$, $6$
$66$$9$
$72$$7$
$77$$10$
$87$$8$
$106$$13$
$109$$12$
$127$$15$
$146$$16$
$151$$17$

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

import pandas as pd
from functools import lru_cache

df = pd.read_excel('22-25.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]).replace(' ', '').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(max(finish(p) for p in t))   # 151

Здесь после процесса $15$ ветка расходится: $16$ заканчивается на $146$ мс, а $17$ — на $151$ мс. Поэтому нужен максимум по всем процессам, а не по последней строке таблицы.

Показать
Очки опыта 20
Спросить Зави
26. Задание #298263
Решено верно
Решено неверно
Сообщить о проблеме

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

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

Определите максимальное количество процессов, которые параллельно выполняются на $22$-й мс. Считать, что каждый процесс начинается в самое раннее допустимое время. Нумерация миллисекунд начинается с $1$.

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

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

Для приведённой таблицы процесс $3$ начинается на $8$-й мс, заканчивается на $9$-й мс.

Нужен отрезок работы каждого процесса. Процесс стартует сразу после того, как закончится последний из тех, от которых он зависит, и занимает миллисекунды с $f-d+1$ по $f$, где $f$ — момент завершения, $d$ — длительность. Процесс выполняется на $22$-й мс, если $f-d+1 \le 22 \le f$.

Расписываем цепочки. Независимые процессы $7$, $22$ и $20$ занимают мс $1$–$2$, $1$–$2$ и $1$–$4$. Дальше идут $8$ (мс $5$–$6$), $9$ (мс $5$), $10$ (мс $5$–$10$), $23$ (мс $5$–$9$), $12$ (мс $6$), $1$ (мс $7$), $17$ (мс $7$–$9$), $18$ (мс $10$–$11$), $2$, $4$ и $21$ (стартуют на $11$-й мс), $19$ (мс $12$–$13$), $14$ (мс $14$), $16$ (мс $14$–$19$), $24$ (мс $14$–$15$), $13$ (мс $16$–$20$).

Теперь важные для нас процессы. Процесс $11$ зависит от $16$, который заканчивается на $19$ мс, значит $11$ занимает мс $20$–$23$. Процесс $25$ зависит от $1$, $9$ и $16$: позже всех $16$, поэтому $25$ занимает мс $20$–$25$. Процесс $5$ зависит от $4$, $16$ и $8$ и занимает единственную $20$-ю мс, а зависящий от него процесс $6$ (зависит от $5$ и $4$) занимает мс $21$–$24$.

Все три процесса — $6$, $11$ и $25$ — работают на $22$-й миллисекунде. Остальные к этому моменту либо уже закончились, либо ещё не начались: процесс $3$ стартует только на $25$-й мс, а $15$ — на $26$-й.

Таким образом, на $22$-й мс параллельно выполняются процессы $6$, $11$ и $25$ — всего $3$ процесса.

ПроцессЗанятые мс
$7$, $22$$1$–$2$
$20$$1$–$4$
$9$$5$
$8$$5$–$6$
$23$$5$–$9$
$10$$5$–$10$
$12$$6$
$1$$7$
$17$$7$–$9$
$18$$10$–$11$
$4$$11$–$12$
$21$$11$–$13$
$2$$11$–$16$
$19$$12$–$13$
$14$$14$
$24$$14$–$15$
$16$$14$–$19$
$13$$16$–$20$
$5$$20$
$11$$20$–$23$
$25$$20$–$25$
$6$$21$–$24$
$3$$25$–$27$
$15$$26$

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

import pandas as pd
from functools import lru_cache

df = pd.read_excel('22-26.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]).replace(' ', '').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)

# процесс занимает мс с finish-t+1 по finish
print(sum(1 for p in t if finish(p) - t[p] < 22 <= finish(p)))   # 3

Условие finish(p) - t[p] < 22 означает, что процесс успел стартовать до конца $22$-й миллисекунды, а 22 <= finish(p) — что он к этому моменту ещё не закончился. Вся совокупность процессов в этом файле завершается на $27$ мс.

Показать
Очки опыта 20
Спросить Зави
27. Задание #298269
Решено верно
Решено неверно
Сообщить о проблеме

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

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

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

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

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

Используя данные из файла, составим таблицу, на какой мс может закончиться каждый из процессов. Независимые процессы $10$, $1$, $2$, $14$ и $4$ завершатся на $11$, $20$, $22$, $22$ и $24$ мс соответственно.

Процесс $16$ зависит от $14$ и завершится на $22+18=40$ мс. Процесс $3$ зависит от $1$ и $2$: позже заканчивается $2$ (на $22$ мс), значит $3$ завершится на $22+19=41$ мс. Процесс $5$ зависит от $1$ и $3$ и завершится на $41+19=60$ мс.

Процесс $6$ зависит от $4$ и $5$, позже заканчивается $5$, поэтому $6$ завершится на $60+16=76$ мс. Процесс $9$ зависит от $2$ и $6$ и завершится на $76+13=89$ мс. Процесс $7$ зависит от $1$, $4$ и $6$: позже всех $6$, значит $7$ завершится на $76+20=96$ мс.

Процесс $8$ зависит от $3$, $5$ и $7$: позже всех $7$, поэтому $8$ завершится на $96+19=115$ мс. Процесс $11$ зависит от $4$ и $7$ и завершится на $96+22=118$ мс. Процесс $12$ зависит от $8$ и завершится на $115+22=137$ мс, процесс $13$ зависит от $5$, $8$ и $10$ и завершится на $115+25=140$ мс.

Наконец, процесс $15$ зависит от $13$ и $14$ и завершится на $140+19=159$ мс, а процесс $17$ зависит от $11$ и $13$: позже заканчивается $13$, значит $17$ завершится на $140+25=165$ мс. Это и есть самое позднее время.

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

Время, мсID процесса
$11$$10$
$20$$1$
$22$$2$, $14$
$24$$4$
$40$$16$
$41$$3$
$60$$5$
$76$$6$
$89$$9$
$96$$7$
$115$$8$
$118$$11$
$137$$12$
$140$$13$
$159$$15$
$165$$17$

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

import pandas as pd
from functools import lru_cache

df = pd.read_excel('22-27.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]).replace(' ', '').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(max(finish(p) for p in t))   # 165

Критический путь здесь идёт по цепочке $2 \to 3 \to 5 \to 6 \to 7 \to 8 \to 13 \to 17$. После процесса $13$ ветка расходится: $15$ заканчивается на $159$ мс, а $17$ — на $165$ мс, поэтому нужен максимум по всем процессам.

Показать
Очки опыта 20
Спросить Зави
28. Задание #298268
Решено верно
Решено неверно
Сообщить о проблеме

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

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

Определите минимальное время (в мс), за которое завершатся $16$ процессов. Считать, что каждый процесс начинается в самое раннее допустимое время. Время отсчитывается непрерывно с первой миллисекунды. В ответе укажите только число – количество миллисекунд.

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

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

Для приведённой таблицы процесс $3$ начинается на $8$-й мс, заканчивается на $9$-й мс.

Составим таблицу, на какой мс завершится каждый из процессов, и будем накапливать их количество. Искомое время — момент завершения $16$-го по счёту процесса.

Независимые процессы $3$, $8$ и $13$ завершаются на $6$ мс — это сразу три процесса. Процесс $17$ зависит от $8$ и завершится на $6+1=7$ мс, процесс $23$ зависит от $3$ и тоже завершится на $7$ мс. Процесс $21$ зависит от $13$ и завершится на $8$ мс, процесс $20$ зависит от $21$ — на $9$ мс. К этому моменту завершено $7$ процессов.

Процесс $12$ зависит от $17$, $13$ и $8$: позже всех $17$ (на $7$ мс), значит $12$ завершится на $7+5=12$ мс. Процесс $19$ зависит от $12$ и завершится на $13$ мс, процесс $14$ зависит от $17$ и $8$ и тоже завершится на $7+6=13$ мс — всего $10$.

Процесс $2$ зависит от $19$, $12$ и $8$: позже всех $19$ (на $13$ мс), поэтому $2$ завершится на $13+2=15$ мс. Процесс $25$ зависит от $3$ и $14$ и завершится на $13+2=15$ мс — всего $12$.

Процесс $4$ зависит от $19$ и $17$ и завершится на $13+5=18$ мс, процесс $7$ зависит от $14$, $17$ и $2$: позже всех $2$ (на $15$ мс), значит $7$ завершится на $15+3=18$ мс — всего $14$.

И наконец на $19$ мс заканчиваются сразу два процесса: $16$ зависит от $2$ и завершается на $15+4=19$ мс, а $22$ зависит от $19$ и завершается на $13+6=19$ мс. Они и доводят счёт до $16$.

Значит минимальное время, за которое завершатся $16$ процессов, равно $19$ мс.

Время, мсID процессаВсего завершено
$6$$3$, $8$, $13$$3$
$7$$17$, $23$$5$
$8$$21$$6$
$9$$20$$7$
$12$$12$$8$
$13$$14$, $19$$10$
$15$$2$, $25$$12$
$18$$4$, $7$$14$
$19$$16$, $22$$16$
$20$$9$$17$
$21$$11$$18$
$23$$1$$19$
$24$$10$$20$
$25$$24$$21$
$26$$15$$22$
$28$$5$$23$
$29$$6$, $18$$25$

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

import pandas as pd
from functools import lru_cache

df = pd.read_excel('22-28.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]).replace(' ', '').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)

times = sorted(finish(p) for p in t)
print(times[15])   # 19 — время завершения 16-го по счёту процесса

Отсортировав времена завершения по возрастанию, достаточно взять элемент с индексом $15$. Обратите внимание, что на $19$-й мс заканчиваются сразу два процесса, поэтому счёт перескакивает с $14$ сразу до $16$.

Показать
Очки опыта 20
Спросить Зави
29. Задание #298251
Решено верно
Решено неверно
Сообщить о проблеме

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

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

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

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

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

Используя данные из файла, составим таблицу, на какой мс может закончиться каждый из процессов. Независимые процессы $9$, $1$, $6$, $4$, $11$ и $14$ завершатся на $11$, $15$, $19$, $20$, $20$ и $23$ мс соответственно.

Процесс $2$ зависит от $1$, значит завершится на $15+17=32$ мс. Процесс $7$ зависит от $4$ и $6$: позже заканчивается $4$ (на $20$ мс), поэтому $7$ завершится на $20+18=38$ мс. Процесс $3$ зависит от $1$ и $2$ и завершится на $32+16=48$ мс. Процесс $10$ зависит от $3$, $4$ и $7$ и завершится на $48+11=59$ мс.

Процесс $5$ зависит от $1$, $2$ и $3$: позже всех $3$, значит $5$ завершится на $48+19=67$ мс. Процесс $8$ зависит от $3$, $5$, $6$ и $7$: позже всех $5$, поэтому $8$ завершится на $67+16=83$ мс. Процесс $13$ зависит от $4$, $5$, $9$ и $11$ и завершится на $67+25=92$ мс.

Процесс $12$ зависит от $7$, $8$ и $11$: позже всех $8$ (на $83$ мс), значит $12$ завершится на $83+24=107$ мс. Процесс $18$ зависит от $4$, $6$, $8$, $12$ и $13$ и завершится на $107+13=120$ мс. Процесс $15$ зависит от $12$ и $13$: позже заканчивается $12$, поэтому $15$ завершится на $107+22=129$ мс.

Дальше процесс $16$ зависит от $3$ и $15$ и завершится на $129+16=145$ мс, процесс $17$ зависит от $2$, $7$ и $15$ и завершится на $129+28=157$ мс. Наконец, процесс $19$ зависит от $9$, $14$ и $17$: позже всех $17$, значит $19$ завершится на $157+18=175$ мс.

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

Время, мсID процесса
$11$$9$
$15$$1$
$19$$6$
$20$$4$, $11$
$23$$14$
$32$$2$
$38$$7$
$48$$3$
$59$$10$
$67$$5$
$83$$8$
$92$$13$
$107$$12$
$120$$18$
$129$$15$
$145$$16$
$157$$17$
$175$$19$

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

import pandas as pd
from functools import lru_cache

df = pd.read_excel('22-29.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]).replace(' ', '').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(max(finish(p) for p in t))   # 175

Критический путь идёт по цепочке $1 \to 2 \to 3 \to 5 \to 8 \to 12 \to 15 \to 17 \to 19$. Обратите внимание на процесс $18$: он зависит сразу от пяти процессов, но заканчивается на $120$ мс, то есть заметно раньше финала.

Показать
Очки опыта 20
Спросить Зави
30. Задание #298272
Решено верно
Решено неверно
Сообщить о проблеме

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

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

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

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

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

Используя данные из файла, составим таблицу, на какой мс может закончиться каждый из процессов. Независимые процессы $9$, $1$, $3$, $2$ и $11$ завершатся на $11$, $15$, $16$, $17$ и $20$ мс соответственно.

Процесс $4$ зависит от $1$ и $3$: позже заканчивается $3$ (на $16$ мс), значит $4$ завершится на $16+20=36$ мс. Процесс $5$ зависит от $1$, $2$ и $3$: позже всех $2$ (на $17$ мс), поэтому $5$ завершится на $17+19=36$ мс.

Процесс $6$ зависит от $2$, $3$ и $4$: позже всех $4$, значит $6$ завершится на $36+19=55$ мс. Процесс $13$ зависит от $4$, $5$, $9$ и $11$ — все они заканчиваются не позже $36$ мс, поэтому $13$ завершится на $36+25=61$ мс. Процесс $7$ зависит от $4$ и $6$ и завершится на $55+18=73$ мс.

Процесс $10$ зависит от $3$, $4$ и $7$ и завершится на $73+11=84$ мс. Процесс $8$ зависит от $3$, $5$, $6$ и $7$: позже всех $7$, значит $8$ завершится на $73+16=89$ мс. Процесс $12$ зависит от $7$, $8$ и $11$ и завершится на $89+24=113$ мс.

Дальше процесс $15$ зависит от $12$ и $13$: позже заканчивается $12$, поэтому $15$ завершится на $113+22=135$ мс, а процесс $14$ зависит от $8$ и $12$ и завершится на $113+23=136$ мс. Процесс $16$ зависит от $14$ и $15$: позже заканчивается $14$, значит $16$ завершится на $136+16=152$ мс.

Наконец, процесс $17$ зависит от $10$, $11$ и $15$: позже всех $15$ (на $135$ мс), поэтому $17$ завершится на $135+28=163$ мс. Это и есть самое позднее время.

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

Время, мсID процесса
$11$$9$
$15$$1$
$16$$3$
$17$$2$
$20$$11$
$36$$4$, $5$
$55$$6$
$61$$13$
$73$$7$
$84$$10$
$89$$8$
$113$$12$
$135$$15$
$136$$14$
$152$$16$
$163$$17$

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

import pandas as pd
from functools import lru_cache

df = pd.read_excel('22-30.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]).replace(' ', '').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(max(finish(p) for p in t))   # 163

Обратите внимание на финал: процесс $16$ заканчивается на $152$ мс, хотя стоит в таблице предпоследним, а последним завершается $17$ — на $163$ мс. Поэтому и нужен максимум по всем процессам, а не по последней строке.

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

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