#987. ZOJ问题_1
ZOJ问题_1
说明
对给定的字符串(只包含'z','o','j'三种字符),判断他是否能AC。
是否AC的规则如下:
1. zoj能AC;
2. 若字符串形式为xzojx,则也能AC,其中x可以是N个'o' 或者为空;
3. 若azbjc 能AC,则azbojac也能AC,其中a,b,c为N个'o'或者为空;
输入格式
输入包含多组测试用例,每行有一个只包含'z','o','j'三种字符的字符串,字符串长度小于等于1000。
输出格式
对于给定的字符串,如果能AC则请输出字符串“Accepted”,否则请输出“Wrong Answer”。
样例
zoj
ozojo
ozoojoo
oozoojoooo
zooj
ozojo
oooozojo
zojoooo
Accepted
Accepted
Accepted
Accepted
Accepted
Accepted
Wrong Answer
Wrong Answer
提示
怎样的字符串才是符合条件的呢?这个需要仔细分析题目描述中的三个条件。前两个条件比较简单,主要分析第三个条件。我们注意前两个条件,每个条件只确定了一个比较明显的形式,第三个条件每次变换就会有很多形式了。那么,通过条件三的变换会得到怎样的形式呢?条件三的变化必然是基于一个初始状态的,这个初始状态就来自于条件一或者条件二。如果条件三种的a不为空,则经过条件三变换后就不能得到符合条件一和条件二的形式了,因为经过条件三变换后的形式中z与j之间的o的数目大于1,而在前两个条件当中中间o的数目只能为1。再仔细观察条件三的初始状态会发现起始时,a和c中o的数目是相同的,这样每次经过条件三的变换z与j之间会增加一个o,而j之后会增加与a中相同数目的o。因而最终j之后o的数目是z之前o数目与z和j之间o数目的乘积。