eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

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

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

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

Як правило визначають час виконання алгоритму у порівнянні з 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". За рядком з многочленом повинен йти пустий рядок, крім останнього тестового випадку.

Приклад

Вхідні дані #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