<ПРЕД Задача:
СЛЕД>
Задачу решили 274 пользователя: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Algorithm Complexity

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

Обычно скорость работы алгоритма определяется по отношению к 'размеру' n входных данных, чем может служить число объектов, которые нужно отсортировать, число вершин многоугольника и т.д. Так как получение формулы, выражащей зависимость времени работы алгоритма от n, — непростая задача, было бы неплохо автоматизировать этот процесс. К сожалению, в общем случае это сделать невозможно, но в данной задаче мы будем рассматривать очень простые программы, для которых это можно сделать. Эти программы написаны в соответствии со следующими правилами (в виде БНФ), где < number > может быть любым неотрицательным целым числом меньше 2000:

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

Вход.

Программа, составленная согласно описанной грамматике. Пробельные символы и символы перевода строки могут встречаться в любом месте программы, но не внутри ключевых слов BEGIN, END, LOOP и OP и не внутри записи целых чисел. Максимальная вложенность операторов LOOP равна 10.

Выход.

Выведите время выполнения программы, выраженное через n; это будет полином степени меньше 10.

Полином следует выводить в обычном виде, т.е. привести подобные слагаемые и напечатать его в виде

Runtime = a*n^10+b*n^9+ . . . +i*n^2+ j*n+k,
где члены с нулевыми коэффициентами опускаются, а множители, равные 1, не пишутся. Если время выполнения равно нулю, выведите
Runtime = 0.
Гарантируется, что все коэффициенты меньше 230.

Вход #1
BEGIN
LOOP n
OP 4
LOOP 3
LOOP n
OP 1
END
OP 2
END
OP 1
END
OP 17
END
Выход #1
Runtime = 3*n^2+11*n+17

Вход #2
BEGIN
OP 1997 LOOP n LOOP n OP 1 END END
END
Выход #2
Runtime = n^2+1997

Автор
из Valladolid, 1997

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 200ms

SW soft NIX
ID = 3.234.244.18