Статична складність#1073

Статична складність

1 секунда
64 мегабайти
Дуже легка

Аналіз часової складності алгоритмів є важливим інструментом для створення ефективних програм. Алгоритми з лінійним часом виконання зазвичай значно швидші за ті, які для тієї ж задачі вимагають квадратичного часу. Тому перевагу слід надавати саме лінійним алгоритмам.

Зазвичай час виконання алгоритму визначається щодо — "розміру" вхідних даних. Це може бути, наприклад, кількість об'єктів для сортування, кількість точок у багатокутнику тощо. Оскільки знайти формулу, яка описує часову складність як функцію від , часто важко, було б чудово, якби цей процес міг виконуватись автоматично. На жаль, це неможливо в загальному випадку. Проте, у цій задачі ви будете аналізувати дуже прості програми, для яких це можна зробити. Такі програми описуються наступною BNF-граматикою, де <\textbf{number}> — це будь-яке невід'ємне ціле число:

<\textbf{Program}> ::= "BEGIN" <\textbf{Statement list}> "END"

<\textbf{Statement list}> ::= <\textbf{Statement}> | <\textbf{Statement}> <\textbf{Statement list}>

<\textbf{Statement}> ::= <\textbf{LOOP statement}> | <\textbf{OP statement}>

<\textbf{LOOP statement}> ::= <\textbf{LOOP header}> <\textbf{Statement list}> "END"

<\textbf{LOOP header}> ::= "LOOP" <\textbf{number}> | "LOOP n"

<\textbf{OP statement}> ::= "OP" <\textbf{number}>

Час виконання такої програми обчислюється наступним чином: команда OP вимагає стільки одиниць часу, скільки зазначено в параметрі. Список команд усередині LOOP-команди виконується стільки разів, скільки зазначено в параметрі: за фіксоване число — якщо це число, або разів — якщо вказано . Час виконання списку команд дорівнює сумі часів виконання його складових. Відповідно, повний час виконання залежить від .

Вхідні дані

У першому рядку записане одне ціле число — кількість програм у вхідному файлі. Далі йдуть програм, що відповідають наведеній вище граматиці. Пробіли та розриви рядків можуть з'являтися де завгодно у програмі, крім середини ключових слів BEGIN, END, LOOP, OP або чисел.

Глибина вкладеності операторів LOOP не перевищує , розмір вхідного файлу не перевищує КБ, а коефіцієнти у вихідному многочлені не перевищують .

Вихідні дані

Для кожної програми спочатку виведіть рядок із номером програми. У наступному рядку запишіть час виконання як многочлен від ступеня не більше (зі зведенням подібних доданків). Члени вищих ступенів мають передувати нижчим, не виводьте доданки, у яких коефіцієнт , та не записуйте коефіцієнт . Загальний вигляд: "Runtime = a*n^10 + b*n^9 + ... + i*n^2 + j*n + k". Якщо час виконання дорівнює нулю, виведіть "Runtime = 0". Після кожного випадку, крім останнього, виведіть порожній рядок.

Приклади

Приклад 1

Loading
Loading