[NWRRC 2017] Fygon 2.0

ID: 6049

远端评测题

3000ms

512MiB

难度: 8

上传者:

标签>

2017

ACM_ICPC

Description

心爱的编程语言 Fygon 的新版本发布了！全新的 Fygon 2.0 仍然只有两个语句。第一个语句是 lag。它几乎可以替代任何其他语句。第二个语句是一个 for 循环：

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

for 循环使得从 from 到 to 进行迭代，包含两端。

如果 from 大于 to，则循环体不执行。

是从 a 到 z 的小写字母，除了 n，它是一个在给定代码片段之前定义的变量。

和可以等于外层循环中定义的任何变量。此外，可以是 1，可以是 n。

循环体缩进四个空格，并且至少包含一个语句。

如果你熟悉 Fygon 1.0，你会注意到，秉承最佳编程实践的精神，Fygon 2.0 不向后兼容，因为 range 函数现在需要两个参数。

新版本的性能显著提高，因此你可以编写更多嵌套的 for 循环。这就是为什么我们不再关注操作的确切数量，而是关注程序的渐进复杂性。为简单起见，所有 for 循环都嵌套在一个链中，并且在所有 for 循环中恰好有一个 lag 语句。所有循环变量都不同，并且不等于 n。

让我们定义 $f(n)$ 为给定 Fygon 程序执行的 lag 操作的数量，作为 n 的函数。对于非负整数 $k$ 和正有理数 $C$ ，如果

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

我们称 $C \cdot n^{k}$ 是程序的渐进复杂性。

给定一个 Fygon 2.0 程序，找出其渐进复杂性。

输入的第一行包含单个整数 $m$ —— Fygon 2.0 程序中的行数。接下来的 $m$ 行包含程序本身。程序至少有 1 个，最多有 20 个 for 语句。每个 for 语句包含一个嵌套的 for 语句或 lag 语句。

输出数字 $k$ 和 $C$ 。 $C$ 应以不可约分数 $p/q$ 的形式输出，其中 $p$ 和 $q$ 互质。

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

3 1/3

时间限制：3 秒，内存限制：512 MB。

题面翻译由 ChatGPT-4o 提供。