AtCoder Regular Contest 069 D
AtCoder Regular Contest 069 D
D - Menagerie
Time limit : 2sec / Memory limit : 256MB
Score : 500 points
Problem Statement
Snuke, who loves animals, built a zoo.
There are N animals in this zoo. They are conveniently numbered 1 through N, and arranged in a circle. The animal numbered i(2≤i≤N−1) is adjacent to the animals numbered i−1 and i+1. Also, the animal numbered 1 is adjacent to the animals numbered 2 and N, and the animal numbered N is adjacent to the animals numbered N−1 and 1.
There are two kinds of animals in this zoo: honest sheep that only speak the truth, and lying wolves that only tell lies.
Snuke cannot tell the difference between these two species, and asked each animal the following question: "Are your neighbors of the same species?" The animal numbered i answered si. Here, if si is o, the animal said that the two neighboring animals are of the same species, and if si is x, the animal said that the two neighboring animals are of different species.
More formally, a sheep answered o if the two neighboring animals are both sheep or both wolves, and answered x otherwise. Similarly, a wolf answered x if the two neighboring animals are both sheep or both wolves, and answered o otherwise.
Snuke is wondering whether there is a valid assignment of species to the animals that is consistent with these responses. If there is such an assignment, show one such assignment. Otherwise, print -1.
Constraints
- 3≤N≤105
- s is a string of length N consisting of
oandx.
Input
The input is given from Standard Input in the following format:
N
sOutput
If there does not exist an valid assignment that is consistent with s, print -1. Otherwise, print an string t in the following format. The output is considered correct if the assignment described by t is consistent with s.
- t is a string of length N consisting of
SandW. - If ti is
S, it indicates that the animal numbered i is a sheep. If ti isW, it indicates that the animal numbered i is a wolf.
Sample Input 1
6
ooxooxSample Output 1
SSSWWSFor example, if the animals numbered 1, 2, 3, 4, 5 and 6 are respectively a sheep, sheep, sheep, wolf, wolf, and sheep, it is consistent with their responses. Besides, there is another valid assignment of species: a wolf, sheep, wolf, sheep, wolf and wolf.
Let us remind you: if the neiboring animals are of the same species, a sheep answers o and a wolf answers x. If the neiboring animals are of different species, a sheep answers x and a wolf answers o.
Sample Input 2
3
ooxSample Output 2
-1Print -1 if there is no valid assignment of species.
Sample Input 3
10
oxooxoxooxSample Output 3
SSWWSSSWWS题目链接：http://arc069.contest.atcoder.jp/tasks/arc069_b
题意：n只动物从1到n围成一个圈，每只动物要么是羊要么是狼。每只动物会说出一个字母，说'o'表示它两边动物种类相同，说'x'表示不同。但羊是说真话，狼是说反话。求出这n只动物的种类。
分析：模拟一下就可以了，不过这个模拟比较大！
下面给出AC代码：
1 #include <bits/stdc++.h>
2 using namespace std;
3 const int N=123456;
4 int gh(char *str,char *ch,int n) {
5 for(int i=1; i<n; i++) {
6 if(i<n-2) {
7 if(str[i]=='o') {
8 if(ch[i]=='S') {
9 ch[i+1]=ch[i-1];
10 } else {
11 if(ch[i-1]=='S') ch[i+1]='W';
12 else ch[i+1]='S';
13 }
14 } else {
15 if(ch[i]=='S') {
16 if(ch[i-1]=='S') ch[i+1]='W';
17 else ch[i+1]='S';
18 } else {
19 ch[i+1]=ch[i-1];
20 }
21 }
22 }
23 else if(i==n-2) {
24 if(str[i]=='o') {
25 if(ch[i]=='S') {
26 if(ch[i+1]!=ch[i-1]) {
27 return 1;
28 }
29 }
30 else {
31 if(ch[i+1]==ch[i-1]){
32 return 1;
33 }
34 }
35 }
36 else{
37 if(ch[i]=='S'){
38 if(ch[i+1]==ch[i-1]){
39 return 1;
40 }
41 }
42 else{
43 if(ch[i+1]!=ch[i-1]) {
44 return 1;
45 }
46 }
47 }
48 }
49 else if(i==n-1){
50 if(str[i]=='x'){
51 if(ch[i]=='S') {
52 if(ch[n-2]==ch[0]) return 1;
53 }
54 else{
55 if(ch[n-2]!=ch[0]) return 1;
56 }
57 }
58 else{
59 if(ch[i]=='S'){
60 if(ch[n-2]!=ch[0]) return 1;
61 }
62 else{
63 if(ch[n-2]==ch[0]) return 1;
64 }
65 }
66 }
67 }
68 return 0;
69 }
70 int main() {
71 char str[N];
72 char ch[N];
73 int n;
74 int flag=0;
75 scanf("%d",&n);
76 scanf("%s",str);
77 ch[0]='S';
78 if(str[0]=='o') {
79 memset(ch,0,sizeof(ch));
80 ch[0]='S';
81 ch[1]='S';
82 ch[n-1]='S';
83 flag=gh(str,ch,n);
84 if(flag==0) {
85 for(int i=0; i<n; i++) printf("%c",ch[i]);
86 puts("");
87 return 0;
88 } else {
89 memset(ch,0,sizeof(ch));
90 ch[0]='S';
91 ch[1]='W';
92 ch[n-1]='W';
93 flag=gh(str,ch,n);
94 if(flag==0){
95 for(int i=0;i<n;i++) printf("%c",ch[i]);
96 puts("");
97 return 0;
98 }
99 }
100 }
101 else{
102 memset(ch,0,sizeof(ch));
103 ch[0]='S';
104 ch[1]='S';
105 ch[n-1]='W';
106 flag=gh(str,ch,n);
107 if(flag==0){
108 for(int i=0;i<n;i++) printf("%c",ch[i]);
109 puts("");
110 return 0;
111 }
112 else{
113 memset(ch,0,sizeof(ch));
114 ch[0]='S';
115 ch[1]='W';
116 ch[n-1]='S';
117 flag=gh(str,ch,n);
118 if(flag==0){
119 for(int i=0;i<n;i++) printf("%c",ch[i]);
120 puts("");
121 return 0;
122 }
123 }
124 }
125 ch[0]='W';
126 if(str[0]=='o'){
127 memset(ch,0,sizeof(ch));
128 ch[0]='W';
129 ch[1]='S';
130 ch[n-1]='W';
131 flag=gh(str,ch,n);
132 if(flag==0){
133 for(int i=0;i<n;i++) printf("%c",ch[i]);
134 puts("");
135 return 0;
136 }
137 else{
138 ch[0]='W';
139 ch[1]='W';
140 ch[n-1]='S';
141 flag=gh(str,ch,n);
142 if(flag==0){
143 for(int i=0;i<n;i++) printf("%c",ch[i]);
144 puts("");
145 return 0;
146 }
147 }
148 }
149 else{
150 memset(ch,0,sizeof(ch));
151 ch[0]='W';
152 ch[1]='S';
153 ch[n-1]='S';
154 flag=gh(str,ch,n);
155 if(flag==0){
156 for(int i=0;i<n;i++) printf("%c",ch[i]);
157 puts("");
158 }
159 else{
160 ch[0]='W';
161 ch[1]='W';
162 ch[n-1]='W';
163 flag=gh(str,ch,n);
164 if(flag==0){
165 for(int i=0;i<n;i++) printf("%c",ch[i]);
166 puts("");
167 return 0;
168 }
169 }
170 }
171 puts("-1");
172 return 0;
173 }