|
Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
MOG Training #4Ended |
F - Fygon
Languages: C, C++, Java, Haskell, Pascal, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)
Frederick is a young programmer. He participates in all programming contests he can find and always uses his favorite programming language Fygon. Unfortunately, he often receives Time Limit Exceeded outcome, even when his algorithm is asymptotically optimal. That's because the Fygon interpreter is very slow. Nevertheless, Frederick likes Fygon so much, that he uses non-asymptotical optimizations to fit the solution into time limit. To make it easier, he asks you to write a program, which will be able to estimate the exact number of operations that his Fygon program makes.
For simplicity, we will assume that Fygon has only two statements. The first statement is $\texttt{lag}$. It substitutes almost any other statement. The second statement is a $\texttt{for}$ loop:
$\\\verb| for <variable> in range(<limit>):|$
$\\\verb| <body>|$
This means that $\texttt{<variable>}$ iterates over values from $0$ to $\texttt{<limit>}-1$. In Fygon $\texttt{<variable>}$ is a lowercase letter from $\texttt{a}$ to $\texttt{z}$, and $\texttt{<limit>}$ is either already defined $\texttt{<variable>}$ or a positive integer constant. The $\texttt{<body>}$ of the loop is indented by four spaces and contains at least one statement.
The program receives the input in the variable $\texttt{n}$. This variable has special meaning and cannot be used as a loop variable.
Your task is to find the formula that calculates the number of performed $\texttt{lag}$ operations by the given Fygon program, depending on the value of the variable $\texttt{n}$.
Input
The input file contains the Fygon program. No two loops use the same variable as iterators. Each variable used inside a $\texttt{range}$ is either $\texttt{n}$ or declared in some outer loop.
The program has at most $20$ statements and at most $6$ of them are loops. All integer constants are from $1$ to $9$.
Output
Output the formula for the number of performed $\texttt{lag}$ operations depending on $n$. The length of the formula should be at most $100$ characters (excluding spaces). The formula should correspond to the following grammar:
Sample test(s)
Input
for i in range(n):
for j in range(i):
lag
for x in range(5):
for y in range(n):
for z in range(n):
lag
lag
Output
1/2 * n * (n-1) + 5 * (n*n + 1)