Главная > Параллельные вычисления
1995

Задана программа, состоящая из N операторов присваивания (1 ≤ N ≤ 15). Каждый оператор записывается в следующем виде: X=YopZ, где X, Y и Z - идентификаторы, состоящие из одной заглавной латинской буквы; op - символ одной из арифметических операций: "+" (сложение), "-" (вычитание), "*" (умножение) и "/" (деление).

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

Каждый оператор выполняется за один такт работы процессора. Чтобы синхронизировать работу процессоров введена команда "NOP", которая задерживает работу процессора на один такт. В процессе одновременной работы двух процессоров выполняемые операторы могут использовать только такие общие переменные, которые находятся в правых частях операторов присваивания (например, операторы "A=B+C" и "M=A+K" не могут выполняться одновременно).


Входные данные

Входные данные расположены в текстовом ASCII-файле, имя которго вводится с клавиатуры.

Каждый оператор находится на отдельной строке; файл не содержит пробелов и пустых строк; в конце последней строки файла символов конца строки нет.

Выходные данные

Результат работы помещается в выходной текстовый ASCII-файл с именем OUTPUT.TXT.

В первую строку файла записывается искомое минимальное число тактов P.

Далее следуют P строк, в которых в две колонки выписаны программы для каждого процессора; колонки должны быть выровнены по левому краю.


Пример

входной файлвыходной файл
W=A+B
F=A+P
B=W/F
W=B*C

3
W=A+B   F=A+P
NOP     B=W/F
W=B*C   NOP


Примечания

  1. Исходные данные корректны, и их проверка не требуется.
  2. Время тестирования каждого теста ограничено одной минутой.


Система оценки

Максимальная оценка за задачу - 30 баллов.

 
Hosted by uCoz