Fygon 2.0 Asymptotic Complexity

ID: 20231

Type: Default

1000ms

256MiB

The new version of the Fygon programming language, Fygon 2.0, has only two kinds of statements: the lag statement and the for loop. A for loop has the syntax:

for <variable> in range(<from>, <to>):
    <body>

The loop variable is a lowercase letter (a–z) except n. The range function now requires two parameters and the loop iterates from the first parameter to the second inclusively. (If the from value is greater than the to value, the body is not executed at all.) In every valid Fygon 2.0 program in this problem the loops form a single nested chain and there is exactly one lag statement which is placed inside all the for loops. Note that a loop’s upper bound may be the literal n or a variable defined in an outer loop, and its lower bound is either the constant 1 or an outer‐loop variable (or even n).

Let f(n) be the number of times the lag statement is executed when running a given Fygon 2.0 program as a function of n. It turns out that f(n) is a polynomial in n (in the eventual cases where the loops are executed sufficiently often) so that for some nonnegative integer k and a positive rational number C we have $$\lim_{n\to\infty}\frac{f(n)}{C\cdot n^k}=1.$$

Your task is to compute the asymptotic complexity of a given Fygon 2.0 program. More precisely, if the program never executes any lag (i.e. f(n)=0 for all sufficiently large n) print 0. Otherwise, print the asymptotic complexity in the form:

If k = 0, print the constant C (in irreducible form, e.g. 1 or 3/2).
If k = 1, print n if C=1, otherwise print it as C*n.
If k > 1, print n^k if C=1, otherwise print C*n^k.

Note: In the above, every constant C must be output in its irreducible fraction form (if it is not an integer). In other words, if the answer is 1/2 * n^2 you should print 1/2*n^2 (without spaces).

Input Format:

The input is a valid Fygon 2.0 program. It consists of several lines. Each line is either a single for loop statement or the lag statement. The loops are nested in a single chain; that is, if there are m for loops then the first m lines are for statements (with appropriate indentation for their bodies) and the last line is the unique lag statement indented by 4 spaces m times.

Output Format:

Output a single line – the asymptotic complexity of the program. Print 0 if the program does not execute any lag statement for all sufficiently large n. Otherwise, output the complexity in the format described above.

## inputFormat

The input consists of several lines representing a Fygon 2.0 program. Each for statement is formatted as:

for x in range(L, U):

where x is a lowercase letter not equal to n, and L and U are either the constant 1, the literal n, or a variable previously defined by an outer loop. The only other statement is lag, which is indented so that it is inside all the loops. It is guaranteed that the program is valid and the loops are nested in a single chain.

You may assume that there is at least one for loop (and hence at least 2 lines) in the input.

## outputFormat

Print a single line — the asymptotic complexity. If f(n)=0 (i.e. no lag is executed for sufficiently large n), output 0. Otherwise, output the complexity in the form C*n^k (if C is 1 and/or k is 1 or 0, follow the formatting rules described in the statement). The constant C must be given in irreducible fraction form if it is not an integer.

## sample

for i in range(1, n):
    lag

#P7024. Fygon 2.0 Asymptotic Complexity

Fygon 2.0 Asymptotic Complexity