POJ 1478 - Island of Logic

http://poj.org/problem?id=1478

概要

A, B, C, D, E の5人の住人がいる。 各住人は

のいずれかの種族である。 住人との会話が \(n\) 個与えられるので、誰がどの種族かを推論して答える。 また、その会話が行われたのが昼か夜かも推論して答える。

各種族は以下のような性質をもつ。

会話は以下のいずれかの形式で与えられる。ここで X は A, B, C, D, E のいずれかである。

どの住人の種族も推論できず、昼か夜かも推論できない場合は「No facts are deducible.」と答える。 会話の内容に矛盾が生じている場合は「This is impossible.」と答える。 それ以外の場合は、推論できた事実をすべて答える。

制約

解法

種族と昼夜の割り当ては \(3 ^ 5 \times 2\) 通りしか存在しないので全探索。 実装ゲー。

  1 #include <iostream>
  2 #include <sstream>
  3 #include <vector>
  4 #include <algorithm>
  5 using namespace std;
  6 
  7 struct stmt
  8 {
  9   int speaker, target, info;
 10   bool is_not;
 11 };
 12 
 13 stmt parse(const string& line)
 14 {
 15   istringstream iss(line);
 16   string s;
 17   iss >> s;
 18   stmt t;
 19   t.speaker = s[0]-'A';
 20   t.is_not = false;
 21   iss >> s;
 22   if (s == "It") {
 23     t.target = -1;
 24     iss >> s;
 25     iss >> s;
 26     t.info = s == "day.";
 27   } else {
 28     t.target = s == "I" ? t.speaker : s[0]-'A';
 29     iss >> s;
 30     iss >> s;
 31     if (s == "not") {
 32       t.is_not = true;
 33       iss >> s;
 34     }
 35     if (s == "divine.") {
 36       t.info = 0;
 37     } else if (s == "human.") {
 38       t.info = 1;
 39     } else if (s == "evil.") {
 40       t.info = 2;
 41     } else {
 42       t.info = 3;
 43     }
 44   }
 45   return t;
 46 }
 47 
 48 bool say_true(int type, int day)
 49 {
 50   switch (type) {
 51     case 0: //divine
 52       return true;
 53     case 1: //human
 54       return day;
 55     case 2: //evil
 56       return false;
 57   }
 58   throw "say_true";
 59 }
 60 
 61 bool ok(const vector<stmt>& info, const int a[5], int f)
 62 {
 63   for (vector<stmt>::const_iterator it = info.begin(); it != info.end(); ++it) {
 64     const int speaker_type = a[it->speaker];
 65     const bool truthful_speaker = say_true(speaker_type, f);
 66     if (it->target == -1) {
 67       // day or night
 68       const bool correct_stmt = f == it->info;
 69       if (truthful_speaker != correct_stmt) {
 70         return false;
 71       }
 72     } else {
 73       const int target_type = a[it->target];
 74 
 75       bool r;
 76       if (it->info == 3) {
 77         const bool truthful_target = say_true(target_type, f);
 78         r = truthful_speaker == truthful_target;
 79       } else {
 80         bool correct_stmt = it->info == target_type;
 81         r = truthful_speaker != correct_stmt;
 82       }
 83       if (it->is_not) {
 84         r = !r;
 85       }
 86       if (r) {
 87         return false;
 88       }
 89     }
 90   }
 91   return true;
 92 }
 93 
 94 void answer(const int possible[5][3][2], int exists[5])
 95 {
 96   int day_or_night = -1;
 97   int result[5];
 98   int cnt = 0;
 99   for (int i = 0; i < 5; i++) {
100     result[i] = -1;
101     for (int j = 0; j < 3; j++) {
102       for (int k = 0; k < 2; k++) {
103         if (possible[i][j][k]) {
104           ++cnt;
105           if (result[i] == -1) {
106             result[i] = j;
107           } else if (result[i] == j) {
108             // ok
109           } else {
110             // not deducible
111             result[i] = -2;
112           }
113           if (day_or_night == -1) {
114             day_or_night = k;
115           } else if (day_or_night == k) {
116             // ok
117           } else {
118             // not deducible
119             day_or_night = -2;
120           }
121         }
122       }
123     }
124   }
125   if (cnt == 0) {
126     cout << "This is impossible." << endl;
127   } else {
128     cnt = 0;
129     for (int i = 0; i < 5; i++) {
130       if (exists[i] && result[i] >= 0) {
131         static const string tbl[] = {"divine", "human", "evil"};
132         cout << char(i+'A') << " is " << tbl[result[i]] << "." << endl;
133         ++cnt;
134       }
135     }
136     if (day_or_night >= 0) {
137       ++cnt;
138       static const string tbl[] = {"night", "day"};
139       cout << "It is " << tbl[day_or_night] << "." << endl;
140     }
141     if (cnt == 0) {
142       cout << "No facts are deducible." << endl;
143     }
144   }
145 }
146 
147 int main()
148 {
149   int N;
150   for (int Ti = 1; cin >> N && N != 0; Ti++) {
151     cin.ignore();
152     vector<stmt> info;
153     int exists[5] = {0};
154     for (int i = 0; i < N; i++) {
155       string line;
156       getline(cin, line);
157       const stmt r = parse(line);
158       info.push_back(r);
159       exists[r.speaker] = true;
160       if (r.target != -1) {
161         exists[r.target] = true;
162       }
163     }
164 
165     int possible[5][3][2];
166     for (int i = 0; i < 5; i++) {
167       for (int j = 0; j < 3; j++) {
168         for (int k = 0; k < 2; k++) {
169           possible[i][j][k] = false;
170         }
171       }
172     }
173     int a[5];
174     for (a[0] = 0; a[0] < 3; a[0]++) {
175       for (a[1] = 0; a[1] < 3; a[1]++) {
176         for (a[2] = 0; a[2] < 3; a[2]++) {
177           for (a[3] = 0; a[3] < 3; a[3]++) {
178             for (a[4] = 0; a[4] < 3; a[4]++) {
179               for (int f = 0; f < 2; f++) {
180                 if (ok(info, a, f)) {
181                   for (int i = 0; i < 5; i++) {
182                     possible[i][a[i]][f] = true;
183                   }
184                 }
185               }
186             }
187           }
188         }
189       }
190     }
191 
192     cout << "Conversation #" << Ti << endl;
193     answer(possible, exists);
194     cout << endl;
195   }
196   return 0;
197 }
poj/1478.cc