menu 大连理工大学 DP·AC算法竞赛协会 ICPC集训队 Online Judge
account_circle 请登录
home
首页
book
题目
library_books
题单
apps
分类
play_circle_outline
状态
layers
竞赛/作业
equalizer
排名
assignment_ind
登录
person_add
注册
1065: [NOIP2017]时间复杂度
时间限制:1.000s
内存限制:128MB

题目描述

给出了他自己算出的时间复杂度,可他的编程老师实在不想一个一个检查小明的程序,于是你的机会来啦!下面请你编写程序来判断小明对他的每个程序给出的时间复杂度是否正确。 A++ 语言的循环结构如下:
F i x y
循环体
E
然后判断 i 和 y 的大小关系,若 i 小于等于 y 则进入循环,否则不进入。每次循环结束后i都会被修改成 i +1,一旦 i 大于 y 终止循环。 x 和 y 可以是正整数(x 和 y 的大小关系不定)或变量 n。n 是一个表示数据规模的变量,在时间复杂度计算中需保留该变量而不能将其视为常数,该数远大于 100。 `E`表示循环体结束。循环体结束时,这个循环体新建的变量也被销毁。
注:本题中为了书写方便,在描述复杂度时,使用大写英文字母 O 表示通常意义下 Θ\ThetaΘ 的概念。

输入格式

输入文件第一行一个正整数 t,表示有 t(t≤ 10) 个程序需要计算时间复杂度。
每个程序我们只需抽取其中 `F i x y`和`E`即可计算时间复杂度。注意:循环结构允许嵌套。
接下来每个程序的第一行包含一个正整数 L 和一个字符串,L 代表程序行数,字符串表示这个程序的复杂度,`O(1)`表示常数复杂度,`O(n^w)` 表示复杂度为 nw,其中 w 是一个小于 100 的正整数(输入中不包含引号),输入保证复杂度只有 `O(1)` 和 `O(n^w)` 两种类型。
接下来 L 行代表程序中循环结构中的 `F i x y` 或者 `E`。 程序行若以 `F` 开头,表示进入一个循环,之后有空格分离的三个字符(串)`i x y`,其中 i 是一个小写字母(保证不为 `n` ),表示新建的变量名,x 和 y 可能是正整数或 `n` ,已知若为正整数则一定小于 100。 程序行若以 `E`开头,则表示循环体结束。


备注:
对于 100% 的数据:t≤ 10,L≤ 100。

输出格式

输出文件共 t 行,对应输入的 t 个程序,每行输出`Yes`或`No`或者`ERR`,若程序实际复杂度与输入给出的复杂度一致则输出 `Yes`,不一致则输出`No`,若程序有语法错误(其中语法错误只有: ①F 和 E 不匹配 ②新建的变量与已经存在但未被销毁的变量重复两种情况),则输出`ERR`。
注意:即使在程序不会执行的循环体中出现了语法错误也会编译错误,要输出`ERR`。

样例输入 content_copy

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

样例输出 content_copy

Yes
Yes
ERR
Yes
No
Yes
Yes
ERR

提示/说明

第一个程序 i 从1 到 1 是常数复杂度。
第二个程序 x 从 1 到 n 是 n 的一次方的复杂度。
第三个程序有一个 `F` 开启循环却没有E结束,语法错误。
第四个程序二重循环,n 的平方的复杂度。
第五个程序两个一重循环,n 的一次方的复杂度。
第六个程序第一重循环正常,但第二重循环开始即终止(因为 n 远大于 100,100 大于 4)。
第七个程序第一重循环无法进入,故为常数复杂度。
第八个程序第二重循环中的变量 x 与第一重循环中的变量重复,出现语法错误②,输出 `ERR`。

分类