这是 meelo 原创的 IEEEXtreme极限编程大赛题解
Xtreme 10.0 – Playing 20 Questions with an Unreliable Friend
题目来源 第10届IEEE极限编程大赛
https://www.hackerrank.com/contests/ieeextreme-challenges/challenges/playing-20-questions-with-an-unreliable-friend
To celebrate the 10th anniversary of Xtreme, your friend has arranged 10 balloons in a row in the next room, and has challenged you to guess the sequence of the colors in the row of balloons. The balloons can be red, blue, or green. Your friend will answer a series of yes/no questions about the colors of the balloons. Unfortunately, your friend will tell a certain number of lies when answering your questions.
The questions can be in one of the following forms:
-
You may ask if a particular balloon is a particular color, e.g.:
-
“Is the second balloon red?”
-
“Is the 10th balloon blue?”
-
-
You may ask about the count of balloons of a particular color, e.g.:
-
“Are there 3 red balloons?”
-
“Are there 0 blue balloons?”
-
-
The previous types of questions can be subquestions that are combined together into a larger question with or‘s or and‘s. When combined with an or, only one of the answers to the subquestions must be
yesfor the answer to the entire question to beyes, and when combined with and, all of the answers to the subquestions must beyesin order to the answer to the larger question to beyes.-
“Is the third balloon green or the fourth balloon red?”
-
“Is the tenth balloon red and are there three red balloons and is the first balloon blue?”
-
Note that subquestions in a particular question will be combined either with or‘s or and‘s, but not both. You are not allowed to ask a question like “Is the tenth balloon red or are there three red balloons and is the first balloon blue?”
At the beginning of the game, your friend will tell you how many answers to your questions will be lies. Your friend will be honest when telling you the number of lies he is about to tell. Your task is to determine what colors each of the balloons could be, given the answers to your questions and the number of lies that were told.
Input Format
The input begins an integer t, 1 ≤ t ≤ 20, which gives the number of testcases in the input.
There will be a blank line preceding each testcase. Each testcase begins a line containing two space-separated integers q and n, where q is the number of questions that you asked, and n is the number of lies that your friend told when answering your questions. Note: 1 ≤ q ≤ 20, 0 ≤ n ≤ q
The next 2 q lines represent the questions and answers. A question will be made up of between 1 and 10, inclusive, subquestions in one of the following forms:
color i c count c j
The first type of subquestion is asking if the ith balloon is the color c. i will be an integer, 1 ≤ i ≤ 10, and c will be one of the following characters: r, g, or b.
The second type of subquestion is asking if the number of balloons of color c is equal to j. c will again be one of the following characters: r, g, or b. j will be an integer, 0 ≤ j ≤ 10.
When there are multiple subquestions in a question, they will be separated by or or and.
The answer to each question will appear on the line immediately following the question, and it will be either yes or no.
Output Format
For each test case, you should output a single line containing ten space separated values, where the ith value in the line corresponds to what you conclude about the color of the ith balloon. Each of the values will be one of the following strings:
-
r, if you know that the balloon is red. -
g, if you know that the balloon is green. -
b, if you know that the balloon is blue. -
rg, if you know that the balloon must be either red or green. -
rb, if you know that the balloon must be either red or blue. -
gb, if you know that the balloon must be either blue or green. -
rgb, if you know that the balloon could be any of the possible colors.
Note that there should not be a space after the last value in the line.
Sample Input
32 2
color 1 b
yes
color 2 r
no3 1
count r 4 and count g 7
yes
color 1 b and color 2 r and color 3 b
yes
color 1 g or color 4 g
yes2 0
count r 1
yes
color 6 b or color 1 r
yes
Sample Output
rg r rgb rgb rgb rgb rgb rgb rgb rgb
b r b g rgb rgb rgb rgb rgb rgb
rgb rgb rgb rgb rgb gb rgb rgb rgb rgb
Explanation
First Testcase
In the first testcase, you ask two questions, and your friend lies about both of the answers.
Your first question is “Is the first balloon blue?” Since your friend lied when he said “yes”, you know that it must be red or green.
Your second question is “Is the second balloon red?” Since your friend lied when he said “no”, you know, in fact, that it must be red.
Second Testcase
For the second test case, you ask three questions and your friend lies in one of the answers.
In the first question, you ask “Are there 4 red balloons and 7 green balloons?” Your friend answers “yes”, but since there are only 10 balloons, this must be a lie. You can then conclude that the remaining answers are truthful.
In your second question, you ask “Is the first balloon blue, the second balloon red, and the third balloon blue?” Since your friend is telling the truth when he answers “yes”, you now know the colors of the first three balloons.
In your final question, you ask “Is the first balloon green or the fourth balloon green?” Your friend truthfully answers “yes”. Thus you can conclude that one of the following must be true:
-
Both the first and the fourth balloons are green.
-
The first balloon is green, but the fourth is not.
-
The fourth balloon is green, but the first one is not.
However, since you already know that the first balloon is blue, you know that it is the third case that must be true, so you conclude that the fourth balloon is green.
Third Testcase
For the final testcase, your friend did not lie in any of the answers. You know that:
-
There is one red balloon.
-
Either the sixth balloon is blue or the first balloon is red, or both.
Note that if the first balloon is red, then no other balloons can be red, because of the first answer. If the first balloon is not red, then the sixth balloon must be blue, because of the second answer. Therefore, there is no scenario in which the sixth balloon can be red.
题目解析
这题就是一个暴力搜索。
- 10个气球，每个气球3种颜色，总共也只有种情况。
- 遍历的时候借助从0~59049的整数的遍历。
- 一个问题比如
count r 4用结构体Question表示；一行问题加上回答用结构体Questions表示。 - 由于问题的连接要么为and，要么为or。and连接问题有一个为假则为假，or的连接的问题有一个为真则为真。必须使用这一规则进行优化，否则会超时。
- 输入也有点小麻烦，问题中需要根据问题的类型是count还是color来，修改接下来的输入方式；判断是否为yes或no可以断定一个问题是否结束。
程序
C++
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;const int num_balloon = ;
const int num_color = ;/**
* Covnver number representation of ballons to vector representation
* number: a base-3 number, each bit represent a ballons'color
* colors: a vector of char('r', 'g', 'b')
*/
void number2Colors(int number, vector<char> &colors) {
for(int i=; i<num_balloon; i++) {
int color = number % num_color;
number /= num_color;
if(color == ) colors[i] = 'r';
else if(color == ) colors[i] = 'g';
else if(color == ) colors[i] = 'b';
}
}struct Question {
int type; // 1:color, 2:count
int count, index;
char color; // possible values: 'r', 'g', 'b' bool isTrue(vector<char> colors) {
bool truth;
if(type == ) {
truth = colors[index] == color;
}
else if(type == ) {
int c = ;
for(int i=; i<num_balloon; i++) {
if(colors[i] == color) {
c++;
}
}
truth = c == count;
}
return truth;
}
};struct Questions {
int combine; // 1: and, 2: or
bool truth;
vector<Question> questions; Questions() {
combine = ;
} bool isTrue(vector<char> &colors) {
bool result;
if(combine == ) {
result = true;
}
else if(combine == ) {
result = false;
} for(int i=; i<questions.size(); i++) {
if(combine == ) {
result &= questions[i].isTrue(colors);
if(!result) break;
}
else if(combine == ){
result |= questions[i].isTrue(colors);
if(result) break;
}
} return result;
} bool satisfy(vector<char> &colors) {
return isTrue(colors) == truth;
}
};int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int T;
cin >> T; for(int t=; t<T; t++) {
int Q, L;
cin >> Q >> L;
Questions lines[]; // read q line questions
for(int q=; q<Q; q++) {
while(true) {
Question question;
string type, answer, color;
int index, count;
cin >> type;
if(type == "color") {
cin >> index >> color;
question.type = ;
question.color = color[];
question.index = index-; }
else if(type == "count") {
cin >> color >> count;
question.type = ;
question.color = color[];
question.count = count;
} lines[q].questions.push_back(question); cin >> answer;
if(answer == "yes") {
lines[q].truth = true;
break;
}
else if(answer == "no") {
lines[q].truth = false;
break;
}
else if(answer == "and") {
lines[q].combine = ;
}
else if(answer == "or") {
lines[q].combine = ;
}
}
} // whether index-th ballon could be color
vector<vector<bool> > answer(num_balloon, vector<bool>(num_color, ));
// iterate all configuration of colors of balloon
int maxNumber = pow(num_color,num_balloon)-0.5;//59049;
for(int c=; c<maxNumber; c++) {
//cout << c << endl;
vector<char> colors(num_balloon);
number2Colors(c, colors);
int numLies = ;
for(int q=; q<Q; q++) {
numLies += lines[q].satisfy(colors) == false;
}
if(numLies == L) {
for(int i=; i<num_balloon; i++) {
if(colors[i]=='r') answer[i][] = true;
else if(colors[i]=='g') answer[i][] = true;
else if(colors[i]=='b') answer[i][] = true;
}
}
} // print result
for(int i=; i<num_balloon; i++) {
if(answer[i][]) cout << 'r';
if(answer[i][]) cout << 'g';
if(answer[i][]) cout << 'b';
if(i != num_balloon-) cout << ' ';
}
cout << endl;
}
return ;
}
