''' программное решение
1. Подготовка файла:
- открыть файл в EXEL
- выделить и скопировать в блокнот
- заменить символ ';' на пробел
- сохранить (в данном примере имя файла '22_st1022.txt'
- запомнить число строк в таблице (переменная N) и
максимальный возможный номер процесса + сколько-то (переменная M)
2. Ввод данных, подготовительная работа
Создание и заполнение трех списков:
XX[M] - для заданных процессов = времени выполнения, остальные None
заполняем при считывании
YY[M] - времена завершения процессов. Начальное заполнение = None,
"независимые" процессы заполняются при вводе данных, остальные в
процессе обработки (3-й этап)
AA[] - список/стек с описанием процессов требующих обработки (лист ожидания)
'''
N = 100 # кол-во записей в таблице
M = 15000 # максимальный возможный номер процесса (фактически в примере 14989)
tz = 3 # время задержки перед запуском "зависимого" процесса (из условии)
XX = [None]*M # для записи времени выполнения процесса (по номерам)
YY = [None]*M # времена завершения процессов (по номерам)
AA = [] # список "неопределенных" процессов (есть зависимости)
f = open('22_st1022.txt') # открытие файла
for _ in range(N): # считывание строк таблицы
A = list(map(int,f.readline().split())) # преобразование в список чисел
if len(A) < 3 : A = A + [0] # если "независимые" процессы необозначены
j, t, B = A[0], A[1], A[2:] # номер, время выполнения, зависимости
XX[j] = t # фиксация времени выполнения
if B == [0] : # проверка на "независимость"
YY[j] = t # фиксация времени завершения
else : # процесс имеет зависимости
AA.append((j, B)) # занесение в лист ожидания
f.close() # завершение ввода данных и начальной обработки
'''
3. Основной этап. Обработка Листа ожидаения до его полного обнуления
Каждый проход состоит из:
- создание Резервного списка (BB)
- пока Лист ожидания не пуст:
- извлечение из Листа ожидания элемента (AA.pop())
- "простая" проверка статуса процесса в текущий момент
(проверка полная, не совсем оптимальная, без удаления определившихся)
- если процесс определился то фиксируем время завершения
- иначе "переносим" в резервный список
- Лист ожидания = Резервному списку (порядок процессов не важен)
Количество "проходов" алгоритма не более максимального числа зависимостей в процессах
'''
while AA : # начало основной обработки
print(len(AA)) # информационная печать - отладочная
BB = [] # создание Резервного списка
while AA: # обработка Листа ожидания
ii, pp = AA.pop() # ii - номер процесса, pp - список зависимостей
flag = False # флаг наличия зависимости
tm = 0 # максимальное время ожидания
for p in pp: # проверка по списку зависимостей
if YY[p] == None: # обнаружена зависимость
flag = True # изменение флага
break # необязательная оптимизация
else :
tm = max(tm, YY[p]) # фиксация времени ожидания
if flag : # процесс ещё "неопределен" -> в Резервный список
BB.append((ii,pp)) # добавление в Резервный список
else : # процесс определился ->
YY[ii] = tz + tm + XX[ii] # фиксация времени завершения
AA = BB # "перекладывание" Резервного списка в Лист ожидания
''' 4. Обработка результатов
Проводим несложную обработку массива YY - ищем максимум
условия обработки могут меняться
'''
rez, k = 0, 0 # rez - итоговое время обработки, k - номер процесса (мин.)
for i in range(len(YY)): # прогон по списку времен завершения
if YY[i] == None: # процесса с таким номером не было
continue
if YY[i] > rez : # максимум времени необходимо обновить
rez, k = YY[i], i # фиксация нового максимума и аргумента достижения
print(rez,k) # итоговая печать результатов