题目描述

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 lag. It substitutes almost any other statement. The second statement is a for loop:

for in range $():$

This means that iterates over values from $0$ to $−1$ . In Fygon is a lowercase letter from a to $z$ , and is either already defined or a positive integer constant. The of the loop is indented by four spaces and contains at least one statement.

The program receives the input in the variable $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 lag operations by the given Fygon program, depending on the value of the variable $n$ .

输入格式

The input file contains the Fygon program. No two loops use the same variable as iterators. Each variable used inside a range is either $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$ . Outpu

输出格式

Output the formula for the number of performed 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:

$〈Expressio_n〉 ::= 〈Product〉 ( (‘+' | ‘-') 〈Product〉) ^{ \times }$

$〈Product〉 ::= 〈Value〉 (‘ \times '〈Value〉) ^{ \times }$

$〈Value〉 ::= ‘n' | 〈Number〉 | ‘-'〈Value〉 | ‘('〈Expressio_n〉‘)'$

$〈Number〉 ::= [‘0' \cdots ‘9'] ^{+} (‘/' [‘0' \cdots ‘9'] ^{+}) ^{?}$

题目大意

[NWRRC2015] Fygon 翻译

题目描述

弗雷德里克是一名年轻的程序员。他参加了所有能找到的编程比赛，并总是使用他最喜欢的编程语言 Fygon。不幸的是，他经常收到 "超过时间限制 "的结果，即使他的算法是渐近最优的。这是因为 Fygon 解释器非常慢。尽管如此，弗雷德里克还是非常喜欢 Fygon，所以他使用了非渐进优化的方法来使求解符合时间限制。为了方便起见，他要求你写一个程序，能够估算出他的 Fygon 程序所做的确切操作次数。

为了简单起见，我们假设 Fygon 只有两条语句。第一条语句是滞后的。它几乎可以替代任何其他语句。第二条语句是 for 循环：

for in range $():$

这意味着遍历从 $0$ 到 $-1$ 的值。 在 Fygon 中是从 $a$ 到 $z$ 的小写字母，并且要么是已经定义的，要么是正整数常数。循环语句缩进四个空格，至少包含一条语句。

程序接收变量 $n$ 的输入。该变量具有特殊含义，不能用作循环变量。您的任务是根据变量 $n$ 的值，找出计算 Fygon 程序执行滞后操作次数的公式。

输入格式

输入文件包含 Fygon 程序。没有两个循环使用相同的变量作为迭代器。范围内使用的每个变量要么是 $n$，要么是在某个外循环中声明的。

程序最多有 $20$ 语句，其中最多有 $6$ 是循环。所有整数常量从 $1$ 到 $9$ 不等。

输出格式

根据 $n$ 输出已执行滞后运算次数的公式。公式长度最多为 $100$ 字符（不包括空格）。公式应符合以下语法：

$〈表达式〉 ::= 〈产物〉 ( (‘+' | ‘-') 〈产物〉) ^{ \times }$

$〈产物〉 ::= 〈价值〉 (‘ \times '〈价值〉) ^{ \times }$

$〈价值〉 ::= ‘n' | 〈数〉 | ‘-'〈价值〉 | ‘('〈表达式〉‘)'$

$〈数〉 ::= [‘0' \cdots ‘9'] ^{+} (‘/' [‘0' \cdots ‘9'] ^{+}) ^{?}$

样例 #1

样例输入 #1

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

样例输出 #1

1/2 * n * (n-1) + 5 * (n*n + 1)

提示

时间限制：2 秒，内存限制：256 MB。

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

1/2 * n * (n-1) + 5 * (n*n + 1)

提示

Time limit: 2 s, Memory limit: 256 MB.