问题 1811 --ZOJ问题

1811: ZOJ问题

时间限制: 1 Sec  内存限制: 32 MB
提交: 253  解决: 62
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][20kb]

题目描述

对给定的字符串(只包含'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不为空,则经过条件三变换后就不能得到符合条件一和条件二的形式了,因为经过条件三变换后的形式中zj之间的o的数目大于1,而在前两个条件当中中间o的数目只能为1。再仔细观察条件三的初始状态会发现起始时,aco的数目是相同的,这样每次经过条件三的变换zj之间会增加一个o,而j之后会增加与a中相同数目的o。因而最终j之后o的数目是z之前o数目与zj之间o数目的乘积。

来源

[提交][状态]