#148. 时间复杂度

时间复杂度

题目描述

小明 正在学习一种新的编程语言 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 表示循环体结束。循环体结束时,这个循环体新建的变量也被销毁。

输入格式

输入第一行包含一个正整数 tt,表示有 tt 个程序需要计算时间复杂度。每个程序我们只需抽取其中 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 是一个小写字母,表示新建的变量名,xxyy 可能是正整数或 n ,已知若为正整数则一定小于 100100

程序行若以 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

数据规模与约定

对于全部的测试点,保证 1t101 \le t \le 101L1001 \le L \le 100