QOJ.ac

QOJ

Time Limit: 2.0 s Memory Limit: 256 MB Total points: 100

#12740. Fygon

Statistics

Frederick 是一位年轻的程序员。他参加了所有能找到的编程竞赛,并且总是使用他最喜欢的编程语言 Fygon。不幸的是,即使他的算法在渐进意义上是最优的,他也经常收到“超出时间限制”(Time Limit Exceeded)的结果。这是因为 Fygon 解释器非常慢。尽管如此,Frederick 还是非常喜欢 Fygon,以至于他使用非渐进优化来使解决方案符合时间限制。为了简化这一过程,他请求你编写一个程序,能够估算他的 Fygon 程序执行的确切操作次数。

为简单起见,我们假设 Fygon 只有两条语句。第一条语句是 lag。它几乎可以替代任何其他语句。第二条语句是 for 循环:

for <variable> in range(<limit>):
    <body>

这意味着 <variable> 在 $0$ 到 <limit>$-1$ 的值之间迭代。在 Fygon 中,<variable> 是从 az 的小写字母,而 <limit> 要么是已经定义的 <variable>,要么是一个正整数常量。循环的 <body> 缩进四个空格,并且至少包含一条语句。

程序在变量 n 中接收输入。该变量具有特殊含义,不能用作循环变量。

你的任务是找到一个公式,根据变量 n 的值计算给定 Fygon 程序执行的 lag 操作次数。

输入格式

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

该程序最多有 20 条语句,其中最多 6 条是循环。所有整数常量都在 1 到 9 之间。

输出格式

输出关于 nlag 操作执行次数的公式。公式的长度应最多为 100 个字符(不包括空格)。公式应符合以下语法:

$\langle\text{Expression}\rangle ::= \langle\text{Product}\rangle \, ((\text{'+'} \mid \text{'-'}) \, \langle\text{Product}\rangle)^*$ $\langle\text{Product}\rangle ::= \langle\text{Value}\rangle \, (\text{'*'} \, \langle\text{Value}\rangle)^*$ $\langle\text{Value}\rangle ::= \text{'n'} \mid \langle\text{Number}\rangle \mid \text{'-'} \langle\text{Value}\rangle \mid \text{'('} \langle\text{Expression}\rangle \text{')'}$ $\langle\text{Number}\rangle ::= [\text{'0'}..\text{'9'}]^+ \, (\text{'/'} \, [\text{'0'}..\text{'9'}]^+)?$

样例

输入 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)

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.