Instant Complexity

Time limit1sMemory limit128 MB

Summary

Parse a small nested-loop program, compute its running time as a polynomial in n, and print the collected polynomial from highest degree down.

Level: Medium6 of 10
Topics: Implementation, Stack, Recursion, Math
Solved: No attempts yet

Problem

Analyzing the running-time complexity of an algorithm is an essential tool for designing efficient programs. An algorithm that runs in linear time is usually much faster than one that takes quadratic time for the same task, so it should be preferred.

Usually the running time is expressed in terms of the size $n$ of the input — the number of items to sort, the number of vertices of a polygon, and so on. Finding a formula in $n$ for the running time is generally hard, so it would be convenient to automate it. In general this is impossible, but here we consider programs of a very simple form for which it can be done. Our programs follow the grammar below (in BNF), where < number > is any non-negative integer:

< Program > ::= "BEGIN" < Statementlist > "END"
< Statementlist > ::= < Statement > | < Statement > < Statementlist >
< Statement > ::= < LOOP-Statement > | < OP-Statement >
< LOOP-Statement > ::= < LOOP-Header > < Statementlist > "END"
< LOOP-Header > ::= "LOOP" < number > | "LOOP n"
< OP-Statement > ::= "OP" < number >

The running time of such a program is computed as follows. Executing an OP statement costs as many time units as its parameter. The statement list enclosed by a LOOP statement is executed as many times as the loop parameter indicates: a fixed constant number of times when a number is given, or $n$ times when n is given. The running time of a statement list is the sum of the running times of its parts. The total running time therefore depends, in general, on $n$ .

Input

The first line contains the number $k$ of programs. It is followed by $k$ programs built according to the grammar above. Whitespace and newlines may appear anywhere in a program, but never inside the keywords BEGIN, END, LOOP, OP, or inside an integer value. The nesting depth of LOOP operators is at most $10$ .

Output

For each program, first print a line Program #i, where $i$ is the program's number starting from $1$ . Then print its running time as a polynomial in $n$ ; this polynomial has degree at most $10$ . Print it in the form

Runtime = a*n^10+b*n^9+...+i*n^2+j*n+k

Collect like terms, list them from the highest degree down to the lowest, and join them with + (no spaces). Omit any term whose coefficient is $0$ , and omit a coefficient of $1$ (write n^2, not 1*n^2; write n, not 1*n). The degree- $1$ term is written as n, not n^1, and the constant term is always written as its value (even when it is $1$ ). If the whole running time is $0$ , print Runtime = 0.

Print a blank line between the outputs of consecutive programs.

Examples4

Example 1

Input

2
BEGIN
  LOOP n
    OP 4
    LOOP 3
      LOOP n
        OP 1
      END
      OP 2
    END
    OP 1
  END
  OP 17
END

BEGIN
  OP 1997 LOOP n LOOP n OP 1 END END
END

Expected output

Program #1
Runtime = 3*n^2+11*n+17

Program #2
Runtime = n^2+1997

Example 2

Input

1
BEGIN OP 5 END

Expected output

Program #1
Runtime = 5

Example 3

Input

1
BEGIN LOOP n OP 1 END END

Expected output

Program #1
Runtime = n

Example 4

Input

3
BEGIN OP 7 END
BEGIN LOOP n OP 2 END LOOP 3 OP 4 END END
BEGIN LOOP n LOOP n OP 1 END OP 2 END END

Expected output

Program #1
Runtime = 7

Program #2
Runtime = 2*n+12

Program #3
Runtime = n^2+2*n