#P1472. Instant Complexity

    ID: 473 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 10 上传者: 标签>树结构图结构数据结构Southwestern European Regional Contest 1997

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)