#P20181. 「NOIP2017」时间复杂度

「NOIP2017」时间复杂度

题目描述

小明正在学习一种新的编程语言 A++,刚学会循环语句的他激动地写了好多程序并给出了他自己算出的时间复杂度,可他的编程老师实在不想一个一个检查小明的程序,于是你的机会来啦!下面请你编写程序来判断小明对他的每个程序给出的时间复杂度是否正确。

A++ 语言的循环结构如下:

F i x y
    循环体
E

其中 F i x y 表示新建变量 iiii 变量 ii 不可与未被销毁的变量重名)并初始化为 xx,然后判断 iiyy 的大小关系,若 ii 小于等于 yy 则进入循环,否则不进入。每次循环结束后 ii 都会被修改成 i+1i + 1,一旦 ii 大于 yy 终止循环。

xxyy 可以是正整数(xxyy 的大小关系不定)或变量 nnnn 是一个表示数据规模的变量,在时间复杂度计算中需保留该变量而不能将其视为常数,该数远大于 100100

E 表示循环体结束。循环体结束时,这个循环体新建的变量也被销毁。

注:本题中为了书写方便,在描述复杂度时,使用大写英文字母 OO 表示通常意义下 Θ\Theta 的概念。

输入格式

输入文件第一行一个正整数 tt,表示有 t(t10)t(t\le 10) 个程序需要计算时间复杂度。每个程序我们只需抽取其中 F i x yE 即可计算时间复杂度。注意:循环结构允许嵌套。

接下来每个程序的第一行包含一个正整数 LL 和一个字符串,LL 代表程序行数,字符串表示这个程序的复杂度,O(1) 表示常数复杂度,O(n^w) 表示复杂度为 nwn^w,其中 ww 是一个小于 100100 的正整数(输入中不包含引号),输入保证复杂度只有 O(1)O(n^w) 两种类型。

接下来 LL 行代表程序中循环结构中的 F i x y 或者 E

程序行若以 F 开头,表示进入一个循环,之后有空格分离的三个字符(串)i x y,其中 ii 是一个小写字母(保证不为 n ),表示新建的变量名,xxyy 可能是正整数或 n ,已知若为正整数则一定小于 100100

注意在第 10 组数据中可能存在变量名为 n 的情况,这与之前的描述不符。

程序行若以 E 开头,则表示循环体结束。

输出格式

输出文件共 tt 行,对应输入的 tt 个程序,每行输出 YesNo 或者 ERR,若程序实际复杂度与输入给出的复杂度一致则输出 Yes,不一致则输出 No,若程序有语法错误(其中语法错误只有: 1. FE 不匹配;2. 新建的变量与已经存在但未被销毁的变量重复两种情况),则输出 ERR

注意:即使在程序不会执行的循环体中出现了语法错误也会编译错误,要输出 ERR

样例

8
2 O(1)
F i 1 1
E
2 O(n^1)
F x 1 n
E
1 O(1)
F x 1 n
4 O(n^2)
F x 5 n
F y 10 n
E
E
4 O(n^2)
F x 9 n
E
F y 2 n
E
4 O(n^1)
F x 9 n
F y n 4
E
E
4 O(1)
F y n 4
F x 9 n
E
E
4 O(n^2)
F x 1 n
F x 1 10
E
E
Yes
Yes
ERR
Yes
No
Yes
Yes
ERR
  • 第一个程序 ii1111 是常数复杂度。
  • 第二个程序 xx11nnnn 的一次方的复杂度。
  • 第三个程序有一个 F 开启循环却没有E结束,语法错误。
  • 第四个程序二重循环,nn 的平方的复杂度。
  • 第五个程序两个一重循环,nn 的一次方的复杂度。
  • 第六个程序第一重循环正常,但第二重循环开始即终止(因为 nn 远大于 100100100100 大于 44)。
  • 第七个程序第一重循环无法进入,故为常数复杂度。
  • 第八个程序第二重循环中的变量 xx 与第一重循环中的变量重复,出现语法错误②,输出 ERR

数据范围与提示

对于 30%30\% 的数据:不存在语法错误,数据保证小明给出的每个程序的前 L/2L/2 行一定为以 F 开头的语句,第 L/2+1L/2+1 行至第 LL 行一定为以 E 开头的语句,L10L\le 10,若 x,yx,y 均为整数,xx 一定小于 yy,且只有 yy 有可能为 n

对于 50%50\% 的数据:不存在语法错误,L100L\le 100,且若 x,yx,y 均为整数,xx 一定小于 yy,且只有 yy 有可能为 n

对于 70%70\% 的数据:不存在语法错误,L100L\le 100

对于 100%100\% 的数据:t10,L100t\le 10,L\le 100