POJ 1219 - L-I-N-G-O: LINGO

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

概要

読解ゲー，あるいはエスパーゲー．

まず答えとなる5文字の大文字のアルファベットが与えられるので，それに対して最初の文字と4つの . からなる文字列を答える．

次にいくつかの文字列が与えられるので，それぞれに対して「どれくらい答えの文字列にマッチしているか」を答える． ただし，この入力は不正である可能性がある．つまり，5文字でなかったり大文字のアルファベット以外が含まれているかもしれない．そのときは直前に出力した答えを再び出力する．

「どれくらいマッチしたか」は次のようなフォーマットで答える．

以下はサンプルに含まれている応答例

以下はサンプルには含まれていないが重要と思われる応答例

答えと一致する入力があったときは，答えをそのまま出力して次のケースへ行く． このとき，今処理しているケースの余計な入力は単に無視する．

また，1つのケースに対して6回までしか答えてはならない． 最初に必ず1回答えているので，つまりマッチの状況を答えるのは5回までとなる． 答えと一致する入力がこなかった場合，答えを小文字にしたものを出力して次のケースへ行く． このときも余計な入力があった場合には単に無視する．

制約

とくになし

解法

やるだけだが，Sample Input / Sample Output に罠がある．

実は入力の最初の行は必ず空行がくる． 「A blank line marks the beginning of the next dataset (game). The line after the blank line contains the secret word.」とあり，ここから最初の行も空行であることが読み取れる，かもしれない．

同様に出力も最初の行に空行が入る． 問題文には「Each game's output should be preceded by a single blank line」とある．

 1 #include <iostream>
 2 #include <vector>
 3 #include <cctype>
 4 using namespace std;
 5 
 6 bool valid(const string& s)
 7 {
 8   if (s.size() != 5) {
 9     return false;
10   }
11   for (string::const_iterator it = s.begin(); it != s.end(); ++it) {
12     if (!isupper(*it)) {
13       return false;
14     }
15   }
16   return true;
17 }
18 
19 void solve(const vector<string>& lines)
20 {
21   const string& ans = lines[0];
22   string prev = ".....";
23   prev[0] = ans[0];
24   cout << prev << endl;
25   vector<int> cnt(128, 0);
26   for (string::const_iterator it = ans.begin(); it != ans.end(); ++it) {
27     ++cnt[*it];
28   }
29 
30   const int N = min(lines.size(), 6U);
31   for (int i = 1; i < N; i++) {
32     vector<int> c(cnt);
33     if (!valid(lines[i])) {
34       cout << prev << endl;
35     } else {
36       prev = "@@@@@";
37       for (int j = 0; j < 5; j++) {
38         const char x = lines[i][j];
39         if (c[x] == 0) {
40           prev[j] = '.';
41         } else if (ans[j] == x) {
42           --c[x];
43           prev[j] = x;
44         }
45       }
46       for (int j = 0; j < 5; j++) {
47         const char x = lines[i][j];
48         if (prev[j] == '@') {
49           if (c[x] != 0) {
50             prev[j] = tolower(x);
51             --c[x];
52           } else {
53             prev[j] = '.';
54           }
55         }
56       }
57       cout << prev << endl;
58       if (lines[i] == prev) {
59         return;
60       }
61     }
62   }
63 
64   for (string::const_iterator it = ans.begin(); it != ans.end(); ++it) {
65     cout << char(tolower(*it));
66   }
67   cout << endl;
68 }
69 
70 int main()
71 {
72   string s;
73   vector<string> lines;
74   while (getline(cin, s) && s != "LINGO") {
75     if (s.empty()) {
76       if (!lines.empty()) {
77         cout << endl;
78         solve(lines);
79         lines.clear();
80       }
81     } else {
82       lines.push_back(s);
83     }
84   }
85   return 0;
86 }
poj/1219.cc