Как прочитать зависимости из таблицы?

Обычно это строка вида «1;3». Разбейте её через split(";") и переведите части в числа.

Что если процесс ни от кого не зависит?

Он начинается в момент 0, поэтому max с default=0 даёт ноль.

Можно ли решать в таблице?

Можно, формулой МАКС по ячейкам зависимостей. Программа проверит ответ.

Что значит «процессы выполняются параллельно»?

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

Задание 22 ЕГЭ по информатике: решайте с автопроверкой

В задании 22 дана таблица процессов: сколько длится каждый и от каких процессов он зависит. Процессы без зависимостей стартуют сразу, остальные сразу после окончания всех нужных. Нужно найти общее время или ответить на вопрос о моменте времени.

Решать задачи номера

Как решать программой

Задачу можно решить в электронной таблице, но программа короче. Момент окончания процесса равен его длительности плюс наибольший момент окончания среди процессов, от которых он зависит.

Эту формулу удобно записать рекурсивной функцией с @lru_cache: каждый процесс считается один раз. Общее время — это наибольший момент окончания среди всех процессов.

Для вопросов вроде «сколько процессов завершится к моменту T» сначала найдите окончания всех процессов, затем посчитайте те, что не больше T.

В задачах с паузой между процессами или с запасом времени формула та же, к ней только добавляется пауза. Запас процесса — это разница между самым поздним допустимым окончанием и фактическим.

Разбор примера

Четыре процесса длятся 4, 3, 5 и 2 мс. Второй и третий ждут первого, четвёртый ждёт второго и третьего. За какое время завершатся все?

from functools import lru_cache

times = [4, 3, 5, 2]
deps = [[], [1], [1], [2, 3]]

@lru_cache(None)
def end(i):
    return max((end(j) for j in deps[i - 1]), default=0) + times[i - 1]

print(max(end(i) for i in range(1, len(times) + 1)))

Программа печатает

Первый процесс заканчивается в момент 4, второй в 7, третий в 9. Четвёртый ждёт второго и третьего, начинается в 9 и заканчивается в 11. Это и есть общее время.

Решить эту задачу

Задачи к заданию 22

Минимальное время выполнения всех процессовСредняяРешать
Сколько процессов завершится к моменту TСредняяРешать
Процессы с паузой на передачу данныхСредняяРешать
Запас времени у процессаСредняяРешать
Наибольшее число процессов одновременноСредняяРешать

Бесплатно и без регистрации: пишете код в браузере и проверяете его тестами (без аккаунта — несколько задач в день).

Вопросы и ответы

Как прочитать зависимости из таблицы?: Обычно это строка вида «1;3». Разбейте её через split(";") и переведите части в числа.
Что если процесс ни от кого не зависит?: Он начинается в момент 0, поэтому max с default=0 даёт ноль.
Можно ли решать в таблице?: Можно, формулой МАКС по ячейкам зависимостей. Программа проверит ответ.
Что значит «процессы выполняются параллельно»?: Любое число процессов может идти одновременно, если их зависимости уже выполнены. Ограничения на число процессоров в таких задачах нет, если условие о нём не говорит.