Разборы · ЕГЭ, задание 22

Задание 22 ЕГЭ по информатике: параллельные процессы

Что проверяет задание

В файле — таблица процессов: ID, время выполнения и список процессов, от которых данный зависит (0 — независимый). Процесс начинается, только когда закончились все, от которых он зависит. Нужно найти минимальное общее время, количество процессов в некоторый момент или что-то подобное. 1 балл.

Что нужно знать

• Время окончания процесса = максимум из времён окончания процессов, от которых он зависит (0, если таких нет), плюс его длительность.
• Если миллисекунды нумеруются с 1, процесс длительностью t, закончившийся в мс E, выполняется в мс с E − t + 1 по E.
• Минимальное время выполнения всех процессов — максимальное время окончания.

Как решать

1. В таблице: добавьте столбец «окончание». Для независимых процессов он равен длительности, для остальных — МАКС(окончаний зависимостей) + длительность. Заполнять придётся в правильном порядке, иногда вручную — таблица небольшая.
2. На Python: рекурсивная функция end(p) с lru_cache сама посчитает всё в нужном порядке.
3. Ответьте на вопрос: посчитайте процессы, чей промежуток содержит нужную миллисекунду, или возьмите максимум окончаний.

Пример из демоверсии 2027

Типовой пример из условия: процесс 1 (3 мс, независимый), 2 (4 мс, зависит от 1), 3 (2 мс, от 2 и 4), 4 (5 мс, независимый). Процесс 1 заканчивается в мс 3, процесс 2 — в мс 7, процесс 4 — в мс 5, поэтому процесс 3 начинается на 8-й мс и заканчивается на 9-й.

Задание: определите максимальное количество процессов, которые параллельно выполняются на 7-й мс, если каждый процесс начинается в самое раннее допустимое время.

import pandas as pd
from functools import lru_cache

df = pd.read_excel("22.ods")                    # для .ods нужен odfpy
dur, deps = {}, {}
for pid, t, d in df.values.tolist():
    dur[pid] = t
    deps[pid] = [int(x) for x in str(d).split(";") if int(x) != 0]

@lru_cache(None)
def end(p):                                     # мс, в которую процесс заканчивается
    return max((end(q) for q in deps[p]), default=0) + dur[p]

print(sum(1 for p in dur if end(p) - dur[p] + 1 <= 7 <= end(p)))

Для файла демоверсии ответ — 8.

Типичные ошибки

• Ошибаются на единицу: процесс длительностью 3, закончившийся в мс 5, занимает мс 3, 4 и 5, а не 2–5.
• Берут сумму окончаний зависимостей вместо максимума.
• Не учитывают, что ID в столбце зависимостей записаны через «;» с пробелами или одним числом — приводите значение к строке, как в коде.

Потренироваться: задание 22 новые варианты с проверкой ответа