Версия для печати
Убрать все задачи
Задано арифметическое выражение, содержащее операции сложения,
умножения, круглые скобки и операнды, которыми являются буквы
английского алфавита. Нас будет интересовать скорость вычисления таких
выражений на многопроцессорной машине, поэтому скобки в них будем
расставлять в обязательном порядке для указания порядка проведения
операций.
Известно, что сложение двух чисел занимает время p, а умножение – время
q. Время, необходимое для вычисления сложного выражения
AoB, равно времени, затрачиваемому на выполнение операции
o, плюс максимальное из двух чисел – времени вычисления подвыражения A и времени вычисления
подвыражения B. Время вычисления операнда полагаем равным нулю.
Требуется написать программу, которая:
1. Определяет время, необходимое для вычисления заданного выражения на
многопроцессорной машине.
2. Находит эквивалентное заданному арифметическое выражение с
минимальным временем вычисления и само это время.
Выражения называется эквивалентными, если одно из них можно получить
из другого последовательностью следующих преобразований:
x + y → y + x
,
x * y → y * x
(коммутативный закон),
x + (y + z) → (x + y) + z , x * (y
* z) → (x * y) * z (ассоциативный закон).
Входные данные
В первой строке входного файла содержатся два целых числа p и q
(1 ≤ p,q ≤ 1000), во второй – арифметическое выражение длиной не более 200
символов.
Выходные данные
Первая строка выходного файла должна содержать ответ на первый пункт
задачи. Во вторую строку выведите эквивалентное заданному выражение с
минимальным временем вычисления, а в третью – само это время.
Пример входного файла
1 1
((a+(b+(c+d)))*e)*f
Пример выходного файла
5
((a+b)+(c+d))*(e*f)
3
Решение
Фильтр
