[NWRRC2017] Fygon 2.0

ID: 6049

远端评测题

3000ms

512MiB

尝试: 0

已通过: 0

难度: 6

上传者:

root

标签>

2017

ACM_ICPC

题目描述

The new version of beloved programming language Fygon has been released! The brand new Fygon $2$ . $0$ still has only two statements. The first statement is lag. It substitutes almost any other statement. Second statement is a for loop:

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

The for loop makes iterate from to , both inclusive.

If is greater than , is not executed at all.

is a lowercase letter from a to $z$ , except for $n$ , which is a variable that is defined prior to the given code snippet.

and can be equal to any variable defined in outer loop. In addition to that, can be $1$ and can be $n$ .

The of the loop is indented by four spaces and contains at least one statement.

If you are familiar with Fygon $1$ . $0$ , you can notice that, in the spirit of the best programming practices, Fygon $2$ . $0$ is not backwards compatible, since the range function now requires two parameters.

The performance of the new version is significantly improved, so you can write more nested for loops. That is why we are no longer interested in the exact number of operations, but in the asymptotic complexity of the program instead. For simplicity, all for loops are nested in a single chain and there is exactly one lag statement that is inside all for loops. All loop variables are different and are not equal to $n$ .

Let's define $f(n)$ as the number of lag operations exectuted by a given Fygon program as the function of $n$ . For non-negative integer $k$ and positive rational number $C$ we say that $C · n^{k}$ is the asymptotic complexity of the program if

\lim_{n \to \infty}{\frac{f(n)}{C \cdot n^k}} = 1

Given a Fygon $2$ . $0$ program, find its asymptotic complexity.

输入格式

The first line of the input contains single integer $m$ -- the number of lines in Fygon $2$ . $0$ program. Next $m$ lines contain the program itself. The program has at least $1$ and at most $20$ for statements. Each for statement contains either single nested for statement or lag statement.

输出格式

Output numbers $k$ and $C$ . $C$ should be output in the form of irreducible fraction $p/q$ , where $p$ and $q$ are coprime.

题目大意

卡老师新发明了一种语言：Fygon 2.0。这种语言只有两种语句：lag 和 for。其中 for 的格式如下：

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

<variable> 是一个 a 到 z 之间的字符，但是不包括 n。
<from> 和 <to> 是外面的循环中定义的变量。特别的,<from> 还可以是 1，<to> 还可以是 n。
这个语句表示 <variable> 从 <from> 循环到 <to>，两端均包含。
如果 <from> 大于 <to>，则该语句不会执行。
这里的 <body> 一定是一个 for 语句或者 lag，前面一定有 4 个空格的缩进。

卡老师随手写出了一个 Fygon 2.0 程序。因为他忙着去托老师的精神世界中写神题，所以这个程序的 for 语句数不超过 $20$ 个。

现在他想要计算这个程序的渐进时间复杂度。渐进时间复杂度定义如下：

定义 $f(n)$ 为 lag 的执行次数，若非负整数 $k$ 和正有理数 $C$ 满足
$\lim_{n\to\infty}\frac{f(n)}{C\cdot n^k}=1$
则该程序的渐进时间复杂度为 $C\cdot n^k$ 。

卡老师看了一眼就算出来了，但是他想考考你，请你帮他求出这个程序的渐进时间复杂度。

4
for i in range(1, n):
    for j in range(1, i):
        for k in range(j, n):
            lag

3 1/3

提示

Time limit: 3 s, Memory limit: 512 MB.

#P7024. [NWRRC2017] Fygon 2.0

题目描述

输入格式

输出格式

题目大意

提示

还没有账户？

登录