e-olymp
Задачи

Статическая сложность

Статическая сложность

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

Обычно определяют время выполнения алгоритма по отношению к n - "размеру" входных данных. Это может быть число объектов, которые нужно отсортировать, число точек многоугольника и т.п. Поскольку определение формулы зависимости временной сложности алгоритма от n - непростая задача, было бы замечательно, если бы её можно было автоматизировать. К сожалению, в общем случае это невозможно. Но в этой задаче мы будем рассматривать программы очень простой природы, над которыми это можно проделать. Рассматриваемые программы записаны согласно следующим правилам БНФ, где <число> может быть любым неотрицательным целым числом:

<Программа>::="BEGIN"<Список операторов>"END"

<Список операторов>::=<Оператор>|<Оператор><Список операторов>

<Оператор>::=<Оператор LOOP>|<Оператор OP>

<Оператор LOOP>::=<Заголовок LOOP><Список операторов>"END"

<Заголовок LOOP>::="LOOP"<число>|"LOOP n"

<Оператор OP>::="OP"<число>

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

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

В первой строке находится целое число k - число программ во входном файле. Затем идут k программ, удовлетворяющих приведенной грамматике. Пробелы и переводы строк могут встречаться везде в программе, но не в ключевых словах BEGIN, END, LOOP и OP, нет их и в целых числах.

Вложенность операторов LOOP не превышает 10, размер входного файла не более 2 Кбайт, коэффициенты многочлена в ответе не превышают 50000.

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

Для каждой программы сначала идет строка с номером программы. В следующей строке записывается время работы программы в терминах n - многочлен степени не более 10. Многочлен должен быть записан обычным способом, то есть подобные слагаемые должны быть приведены, слагаемое большей степени должно прдшествовать слагаемому меньшей степени, слагаемые с коэффициентом 0 не записываются, множители 1 не записываются. Общий вид второй строки "Runtime = a*n^10+b*n^9+...+i*n^2+j*n+k". Если время выполнения нулевое, нужно вывести "Runtime = 0". За строкой с многочленом должна следовать пустая строка, кроме последнего тестового случая.

Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные
2
BEGIN
 LOOP n
  OP 4
   LOOP 3
    LOOP n
     OP 1
    END
    OP 2
   END
  OP 1 
 END
 OP 17 
END

BEGIN
 OP 1997 LOOP n LOOP n OP 1 END END
END
Выходные данные
Program #1
Runtime = 3*n^2+11*n+17

Program #2
Runtime = n^2+1997