ZOJ问题
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3341 Accepted Submission(s): 1002
Problem Description
对给定的字符串(仅仅包括'z','o','j'三种字符),推断他能否AC。
是否AC的规则例如以下:
1. zoj能AC;
2. 若字符串形式为xzojx,则也能AC。当中x能够是N个'o' 或者为空。
3. 若azbjc 能AC,则azbojac也能AC。当中a,b,c为N个'o'或者为空。
Input
输入包括多组測试用例,每行有一个仅仅包括'z','o','j'三种字符的字符串,字符串长度小于等于1000;
Output
对于给定的字符串,假设能AC则请输出字符串“Accepted”,否则请输出“Wrong Answer”。
Sample Input
zoj
ozojo
ozoojoo
oozoojoooo
zooj
ozojo
oooozojo
zojoooo
ozojo
ozoojoo
oozoojoooo
zooj
ozojo
oooozojo
zojoooo
Sample Output
Accepted
Accepted
Accepted
Accepted
Accepted
Accepted
Wrong Answer
Wrong Answer
Accepted
Accepted
Accepted
Accepted
Accepted
Wrong Answer
Wrong Answer
Source
思路:
z前面'o'的个数×z和j中间o的个数=j后面o的个数
oozoojoooo:
若azbjc 能AC。则azbojac也能AC,当中a,b,c为N个'o'或者为空;
这里的话a=oo b=o c=oo
把a,b,c带进去翻译过来是
若oozojoo能AC(当然能AC 依据第1条) 则oozoojoooo也能AC。所以能AC
zooj :
这里的话a=oo b=o c=oo
把a,b,c带进去翻译过来是
若oozojoo能AC(当然能AC 依据第1条) 则oozoojoooo也能AC。所以能AC
zooj :
也是依据第3条 这里a=空 c=空 b=o
翻译过来是
若zoj能AC 则zooj能AC
翻译过来是
若zoj能AC 则zooj能AC
若azbjc 能AC,则azbojac也能AC。当中a,b,c为N个'o'或者为空;
这里azbojac和azbjc相比 z和j中间+了一个o j后面就+了一个a 而z前面也有一个a
以此类推
假设再运行一次这个规定
那么z和j中间就+了2个o 后面也+了2个前面的a
...
所以z前面'o'的个数乘以z和j中间o的个数=j后面o的个数。
这里azbojac和azbjc相比 z和j中间+了一个o j后面就+了一个a 而z前面也有一个a
以此类推
假设再运行一次这个规定
那么z和j中间就+了2个o 后面也+了2个前面的a
...
所以z前面'o'的个数乘以z和j中间o的个数=j后面o的个数。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
#define M 1010
char s[M];
int main()
{
while(~scanf("%s",s))
{
int len=strlen(s)-1;
int i=0,a=0;
while(s[i++]=='o')
a++;
int c=0;
while(s[len--]=='o')
c++; int p1=0,p2=0,b=0;
for(int j=i-1;j<=len+1;j++)
{
if(s[j]=='z')
p1++;
if(s[j]=='o')
b++;
if(s[j]=='j')
p2++;
} if(s[i-1]=='z'&&s[len+1]=='j')
{
if(b>0&&b*a==c&&(p1==1)&&(p2==1))
printf("Accepted\n");
else
printf("Wrong Answer\n");
}
else
printf("Wrong Answer\n");
}
return 0;
}