Статична складність
Аналіз складності алгоритмів по часу - важливий інструмент створення ефективних програм. Алгоритми, які виконуються за лінійний час, як правило, значно швидші алгоритмів, які вимагають для виконання тієї ж задачі квадратичного часу, так що перевага повинна бути віддана першим.
Як правило визначають час виконання алгоритму у порівнянні з 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". За рядком з многочленом повинен йти пустий рядок, крім останнього тестового випадку.