Задание 22 ЕГЭ: процессы в заданном промежутке времени

Процессы в заданном промежутке времени. Тема номера — параллельные процессы. Ниже — пример с ответом и решением; кнопкой под ним можно решить такую же задачу с другими числами, ответ проверится сразу.

Пример

Задание выполняется с использованием прилагаемого файла.

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

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

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

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

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

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Скачать файл к примеру

Решение

Процесс может начаться, только когда завершатся все процессы, от которых он зависит, поэтому время его окончания = максимум из времён окончания этих процессов (0, если их нет) плюс его длительность. Считаем его рекурсией с запоминанием (порядок строк в таблице не важен). Процесс длительностью t, заканчивающийся на мс E, занимает миллисекунды E − t + 1 … E. Процесс задевает промежуток [A; B], если он начинается не позже B (start + 1 ≤ B) и заканчивается не раньше A (end ≥ A).

Ответ: 11.

from functools import lru_cache
from openpyxl import load_workbook

ws = load_workbook("22.xlsx").active
dur, deps = {}, {}
for pid, t, d in ws.iter_rows(min_row=2, values_only=True):
    if pid is None:
        continue
    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]

start = {p: end(p) - dur[p] for p in dur}   # процесс занимает мс start + 1 … end

A, B = 8, 10
print(sum(1 for p in dur if start[p] + 1 <= B and end(p) >= A))

Решить такую задачу — новый вариант с проверкой