QOJ.ac

QOJ

Límite de tiempo: 3.0 s Límite de memoria: 512 MB Puntuación total: 100

#12717. Fygon 2.0

Estadísticas

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

for <variable> in range(<from>, <to>):
    <body>
  • for 循环使 <variable><from> 迭代到 <to>,且包含这两个端点。
  • 如果 <from> 大于 <to>,则 <body> 不会执行。
  • <variable> 是从 az 的小写字母,但不能是 nn 是在给定代码片段之前定义的变量。
  • <from><to> 可以等于外层循环中定义的任何变量。此外,<from> 可以是 1<to> 可以是 n
  • 循环的 <body> 缩进四个空格,并至少包含一条语句。

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

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

设 $f(n)$ 为给定 Fygon 程序执行的 lag 操作次数,它是 $n$ 的函数。对于非负整数 $k$ 和正有理数 $C$,如果满足以下条件,我们称 $C \cdot n^k$ 为该程序的渐进复杂度:

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

给定一个 Fygon 2.0 程序,求其渐进复杂度。

输入格式

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

输出格式

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

样例

输入 1

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

输出 1

3 1/3

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.