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

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

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

• <Программа> ::= "BEGIN" <Список операторов> "END"
• <Список операторов> ::= <Оператор> | <Оператор> <Список операторов>
• <Оператор> ::= <Оператор LOOP> | <Оператор OP>
• <Оператор LOOP> ::= <Заголовок LOOP> <Список операторов> "END"
• <Заголовок LOOP> ::= "LOOP" <число> | "LOOP n"
• <Оператор OP> ::= "OP" <число>

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

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

В первой строке входного файла INPUT.TXT находится целое число k – число программ во входном файле. Затем идут k программ, удовлетворяющих приведённой грамматике. Пробелы и переводы строк могут встречаться везде в программе, но не в ключевых словах BEGIN, END, LOOP и OP, нет их и в целых числах. Вложенность операторов LOOP не превышает 10, размер входного файла не более 2 Кбайт, коэффициенты многочлена в ответе не превышают 50 000.

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

В выходной файл OUTPUT.TXT выведите решение в следующем формате. Для каждой программы сначала идёт строка с номером программы. В следующей строке записывается время работы программы в терминах n – многочлен степени не более 10. Многочлен должен быть записан обычным способом, то есть подобные слагаемые должны быть приведены, слагаемое с большей степенью должно предшествовать слагаемому с меньшей степенью, слагаемые с коэффициентом 0 не записываются, множители 1 не записываются. Общий вид второй строки:

Runtime = a*n^10+b*n^9+...+i*n^2+j*n+k

Если время выполнения нулевое, нужно вывести «Runtime = 0». За строкой с многочленом должна следовать пустая строка.

Пример

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

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]