/ Vijos / 题库 /

时间复杂度

时间复杂度

描述

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

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

F i x y
循环体
E

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

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

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

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

格式

输入格式

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

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

接下来 \(L\) 行代表程序中循环结构中的 "F i x y" 或者 "E"。

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

输出格式

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

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

样例1

样例输入1

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

样例输出1

Yes
Yes
ERR
Yes
No
Yes
Yes
ERR

限制

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

对于 \(50\%\) 的数据:不存在语法错误,\(L\le 100\),且若 \(x\)、\(y\) 均为整数,\(x\) 一定小于 \(y\),且只有 \(y\) 有可能为 \(n\)。

对于 \(70\%\) 的数据:不存在语法错误,\(L\le 100\)。

对于 \(100\%\) 的数据:\(L\le 100\)。

信息

ID
2029
难度
5
分类
(无)
标签
递交数
716
已通过
149
通过率
21%
被复制
2
上传者