Задачі
Статична складність
Статична складність
Аналіз складності алгоритмів по часу - важливий інструмент створення ефективних програм. Алгоритми, які виконуються за лінійний час, як правило, значно швидші алгоритмів, які вимагають для виконання тієї ж задачі квадратичного часу, так що перевага повинна бути віддана першим.
Як правило визначають час виконання алгоритму у порівнянні з \textbf{n} - "розміром" вхідних даних. Це може бути кількість об'єктів, які потрібно відсортувати, кількість точок многокутника і т.п. Оскільки визначення формули залежності часової складності алгоритму від \textbf{n} - непросте завдання, було б чудово, якби її можна було автоматизувати. На жаль, у загальному випадку це неможливо. Але у цій задачі ми будемо розглядати програми дуже простої природи, над якими це можна зробити. Розглядувані програми записані згідно наступним правилам БНФ, де <\textbf{число}> може бути довільним невід'ємним цілим числом:
<\textbf{Програма}>::="\textbf{BEGIN}"<\textbf{Список операторів}>"\textbf{END}"
<\textbf{Список операторів}>::=<\textbf{Оператор}>|<\textbf{Оператор}><\textbf{Список операторів}>
<\textbf{Оператор}>::=<\textbf{Оператор LOOP}>|<\textbf{Оператор OP}>
<\textbf{Оператор LOOP}>::=<\textbf{Заголовок LOOP}><\textbf{Список операторів}>"\textbf{END}"
<\textbf{Заголовок LOOP}>::="\textbf{LOOP}"<\textbf{число}>|"\textbf{LOOP n}"
<\textbf{Оператор OP}>::="\textbf{OP}"<\textbf{число}>
Час виконання такої програми може бути обрахований наступним чином: виконання оператора \textbf{OP} вимагає стільки одиниць часу, скільки вказано в його параметрі. Список операторів, поміщений в оператор \textbf{LOOP}, виконується стільки разів, скільки вказано у параметрі оператора, тобто або задану константну кількість разів, якщо задано число, або \textbf{n} разів, якщо параметром є \textbf{n}. Час виконання списку операторів дорівнює сумі часу виконання його частин. Таким чином, час виконання програми у цілому залежить від \textbf{n}.
\InputFile
у першому рядку знаходиться ціле число \textbf{k} - кількість програм у вхідному файлі. Далі йде \textbf{k} програм, які задовольняють наведеній граматиці. Пропуски і переведення рядків можуть зустрічатись скрізь у програмі, але не у ключових словах \textbf{BEGIN}, \textbf{END}, \textbf{LOOP} і \textbf{OP}, немає їх і у цілих числах.
Вкладеність операторів \textbf{LOOP} не перевищує \textbf{10}, розмір вхідного файлу не більше \textbf{2} Кбайт, коефіцієнти многочлена у відповіді не перевищують \textbf{50000}.
\OutputFile
Для кожної програми спочатку йде рядок з номером програми. У наступному рядку записується час роботи програми у термінах \textbf{n} - многочлен степеня не більше \textbf{10}. Многочлен повинен бути записаним звичайним способом, тобто подібні доданки повинні бути зведеними, доданки більшого степеню повинні передувати доданкам меншого степеня, доданки з коефіцієнтом \textbf{0} не записуються, множники \textbf{1} не записуються. Загальний вигляд другого рядка "\textbf{Runtime = a*n^10+b*n^9+...+i*n^2+j*n+k}". Якщо час виконання нульовий, потрібно вивести "\textbf{Runtime = 0}". За рядком з многочленом повинен йти пустий рядок, крім останнього тестового випадку.
Вхідні дані #1
1 BEGIN LOOP n OP 4 LOOP 3 LOOP n OP 1 END OP 2 END OP 1 END OP 17 END
Вихідні дані #1
Program #1 Runtime = 3*n^2+11*n+17