#P1472. Instant Complexity
Instant Complexity
题目描述
分析算法的运行时间复杂度是设计高效解题程序的重要工具。对于同一任务,线性时间算法通常比二次时间算法快得多,因此应优先选择。
通常,我们根据输入“规模”n(例如待排序对象的数量、给定多边形的顶点数等)来确定算法的运行时间。由于推导依赖于n的运行时间公式并非易事,若能实现自动化将十分有益。遗憾的是,这在一般情况下不可行,但本题将考虑一类结构非常简单的程序,使其可行。程序按以下规则(BNF表示)构建,其中可以是任意非负整数:
<程序> ::= "BEGIN" <语句列表> "END"
<语句列表> ::= <语句> | <语句><语句列表>
<语句> ::= <循环语句> | <操作语句>
<循环语句> ::= <循环头> <语句列表> "END"
<循环头> ::= "LOOP" <数字> | "LOOP n"
<操作语句> ::= "OP" <数字>
运行时间计算规则:
- 操作语句(OP-statement)的执行时间等于其参数指定的时间单位数。
- 循环语句(LOOP-statement)包裹的语句列表执行次数由参数决定:若参数为数字,则执行指定的常数次;若参数为n,则执行n次。
- 语句列表的运行时间为各组成部分时间之和。因此,总运行时间通常与n相关。
输入格式
输入首行包含程序数量k,随后是k个按上述语法构建的程序。程序中可包含任意空格和换行,但关键字(BEGIN、END、LOOP、OP)或整数值内不得出现。循环操作(LOOP)的嵌套深度最多为10层。
输出格式
对每个程序,首先按样例输出格式打印程序编号,然后输出以n表示的运行时间——次数Y≤10的多项式。按常规方式打印多项式,即合并所有项,格式为"Runtime = an^10+bn^9+…+in²+jn+k",其中系数为0的项省略,系数1不显示。若运行时间为0,直接输出"Runtime = 0"。每个测试用例后输出空行。
输入样例1
2
BEGIN
LOOP n
OP 4
LOOP 3
LOOP n
OP 1
END
OP 2
END
OP 1
END
OP 17
END
BEGIN
OP 1997 LOOP n LOOP n OP 1 END END
END
输出样例1
Program #1
Runtime = 3*n^2+11*n+17
Program #2
Runtime = n^2+1997
题目来源
1997年西南欧洲区域竞赛(Southwestern European Regional Contest)