Статья Автор: Лебедев Дмитрий Алексеевич

Задание 22

ЕГЭ-2026. 22 Центр

Формулировка задачи (ID 95563, КЕГЭ 22, 2026 Центр)
В прилагаемом файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается.

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

Формат строки файла: ID время зависимости, например:

3 2 2;4
5 8 1;4

Для приведённого примера процесс 3 начинается на 8-й мс и заканчивается на 10-й мс.

Определите минимальное время (в мс), к которому завершат свою работу 18 процессов.

Данные даны в формате txt, что "подталкивает" к программному решению
Программу напишем из расчета, что процессов и зависимостей немного (то есть не слишком эффективную, попроще)

Считаем данные и занесем в словарь {номер процесса : (время выпольнения, список зависимостей)}
Создадим словарь завершенных процессов, {0 : 0} (то есть есть процесс 0, завершившийся в 0)
Пока словарь завершенных не больше (по размеру) словаря всех - пробегаем по всем словарям и проверям на завершенность
Находим нужный ответ (делаем список завершенных, сортируем и находим нужное - помним, что есть 0

fin = open('22_95563.txt')
dp,zp ={}, {0:0}
for s in fin:
  p, t, z = s.split()
  zv = list(map(int,z.split(';')))
  dp[int(p)] = (int(t) ,zv)
while len(zp) <= len(dp) :
  k = 0
  for p in dp :
    if p in zp : continue
    tp, zv = dp[p]
    try :
      ts = tp + max([zp[z] for z in zv])
      zp[p] = ts
    except :
      k += 1
  print(dp[16])    
a = [zp[p] for p in zp]
a.sort()
print(a[18])

Можно написать и с одним словарем. Сделаем это в следующей задаче.
Алгоритм тот же, только вначале:

файл открывается в табличном редакторе
копируется и сохраняется в блокноте

это этап уже сделан

Формулировка задачи (ID 95476, КЕГЭ 22, 2026 Центр)

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

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

Выполните задания, используя данные из файла

Определите максимальное количество процессов, которые могут быть завершены за первые 21 мс. Считать, что каждый процесс начинается в самое раннее допустимое время. Нумерация миллисекунд начинается с 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-й мс. Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

fin = open('22_95476.txt')
dp ={}
for s in fin:
  p, d, z = s.split()
  zv = list(map(int,z.split(';')))
  p, d = int(p), int(d) #номер процесса, длительность процесса
  if zv == [0] : dp[p] = d #для независимого записываем время окончания
  else : dp[p] = (d, zv) # для зависимого: продолжительность и зависимости
while True :
  k = 0 # инициализация незавершенных
  for p in dp : # перебор процессов
    if type(dp[p]) == type(0) : continue # процесс завершен (значение целого типа)
    try : # проверка на завершение через попытку вычислить старт 
      d, zv = dp[p] 
      ts = max([dp[z] for z in zv])
      dp[p] = ts + d 
    except:  
      k += 1
  if k == 0 : break    
ans = len([p for p in dp if dp[p]<=21 ])
print(ans)

Формулировка задания (ID 95564, КЕГЭ 22, 2026 ДВ)

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

Формат строки файла: ID время зависимости, например:

3 2 2;4
5 8 1;4

Для приведённого примера процесс 3 начинается на 8-й мс и заканчивается на 10-й мс.

Определите максимальное количество процессов, которые начнут выполняться не ранее 15-й секунды (время начала, равное 15 000 мс, также учитывается).

fin = open('22_95564.txt')
dp, zp = {},{0:0}
for s in fin :
  p, d, zv = s.split()
  p, d = int(p), int(d)
  zv = list(map(int, zv.split(';')))
  dp[p] = (d, zv)
while len(zp) <= len(dp) :
  k = 0
  for p in dp :
    if p in zp : continue
    d, zv = dp[p]
    try :
      ts = d + max([zp[z] for z in zv])
      zp[p] = ts
    except :
      k += 1
ans = [(zp[p]-dp[p][0], p)  for p in dp if zp[p]-dp[p][0] >=15*1000]  
ans.sort()
print(len(ans),*ans, sep = '\n')

Формулировка задачи (ID 95565, КЕГЭ 22 2026 Сибирь)
В прилагаемом файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается.

Формат строки файла: ID время зависимости, например:

3 2 2;4
5 8 1;4

Для приведённого примера процесс 3 начинается на 8-й мс и заканчивается на 10-й мс.

Определите количество активных (выполняющихся) процессов на 13-й мс после запуска первого процесса.

fin = open('22_95565.txt')
dp, zp = {}, {0:0}
for s in fin :
  p, d, zv = s.split()
  p, d = int(p), int(d)
  zv = list(map(int, zv.split(';')))
  dp[p] = (d, zv)
while len(zp) <= len(dp) :
  for p in dp :
    if p in zp : continue
    d, zv = dp[p]  
    try :
      ts = d + max([zp[z] for z in zv])
      zp[p] = ts
    except :
      k = 1
ans = [ p for p in dp if zp[p] > 13 and (zp[p] - dp[p][0])<=13]
print(len(ans))

Attached files
22_95476.ods
22_95476.txt
22_95563.txt
22_95564.txt
22_95565.txt

Печать