<PREV Problem:
NEXT>
Solved by 274 users: ...
UserDateAttemptTimeCMSC
big-piglet10 mar 2008Scheme500.31232 
Anju7a04 apr 2006C++200.02238 
Philip_PV12 jul 2008C++600.01251 
adech07 may 2011Python200.06262 
army20 aug 2009C++100.01264 
david_it2111 oct 2008C++200.01264 
Philip_PV12 jul 2008C++500.01264 
Philip_PV12 jul 2008C++400.01271 
kornakovBSU06 oct 2010C++500.01271 
glueray31 oct 2006C++200.01276 
Fat01 sep 2007Ruby900.02280 
tomek18 feb 2006C++100.02281 
Languages
C++
144
FPC
57
C
43
Kylix
14
Java
13
Python
2
Haskell
1
Scheme
1
Ruby
1
Perl
1
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

Algorithm Complexity

Analyzing the run-time complexity of algorithms is an important tool for designing efficient programs that solve a problem. An algorithm that runs in linear time is usually much faster than an algorithm that takes quadratic time for the same task, and thus should be preferred.

Generally, one determines the run-time of an algorithm in relation to the `size' n of the input, which could be the number of objects to be sorted, the number of points in a given polygon, and so on. Since determining a formula dependent on n for the run-time of an algorithm is no easy task, it would be great if this could be automated. Unfortunately, this is not possible in general, but in this problem we will consider programs of a very simple nature, for which it is possible. Our programs are built according to the following rules (given in BNF), where <number > can be any non-negative integer less than 2000:

The run-time of such a program can be computed as follows: the execution of an OP-statement costs as many time-units as its parameter specifies. The statement list enclosed by a LOOP-statement is executed as many times as the parameter of the statement indicates, i.e., the given constant number of times, if a number is given, and n times, if n is given. The run-time of a statement list is the sum of the times of its constituent parts. The total run-time therefore generally depends on n.

Input

The program constructed according to the grammar given above. Whitespace and newlines can appear anywhere in a program, but not within the keywords BEGIN, END, LOOP and OP or in an integer value. The nesting depth of the LOOP-operators will be at most 10.

Output

Output the run-time of the program in terms of n; this will be a polynomial of degree < 10.

Print the polynomial in the usual way, i.e., collect all terms, and print it in the form

Runtime = a*n^10+b*n^9+ . . . +i*n^2+ j*n+k,
where terms with zero coefficients are left out, and factors of 1 are not written. If the runtime is zero, just print
Runtime = 0.
It is guaranteed that all coefficient are less than 2^30.

Sample Input
BEGIN
LOOP n
OP 4
LOOP 3
LOOP n
OP 1
END
OP 2
END
OP 1
END
OP 17
END
Sample Output
Runtime = 3*n^2+11*n+17

Sample Input
BEGIN
OP 1997 LOOP n LOOP n OP 1 END END
END
Sample Output
Runtime = n^2+1997

Author
from Valladolid, 1997

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 200ms

SW soft NIX
ID = 3.233.239.102