题目来源：http://poj.org/problem?id=1013
题目大意：有12枚硬币，其中有一枚假币。所有钱币的外表都一样，所有真币的重量都一样，假币的重量与真币不同，但我们不知道假币的重量是比真币轻还是重。现在有一个很准确的天平，我们可以用这个天平称3次来找到那枚假币。只要仔细选择三次称的方式，总可以再三次之内找出那枚假币。
输入：第一行一个正整数n表示样例个数。接下来每三行为一个测试样例。每行为一次称的结果。每枚硬币被编号为A--L。称量的结果有三种，分别用“up”、“down”和“even”表示。第一个字符串表示天平左边的硬币，第二个字符串表示右边的硬币。左边和右边的硬笔数总是相等的。第三个字符串的单词表明天平右边的状态。
输出：对于每个测试用例，输出假币的编号和这枚假币是比真币重还是轻。格式依照Sample output.
Sample Input
1
ABCD EFGH even
ABCI EFJK up
ABIJ EFGH even
Sample Output
K is the counterfeit coin and it is light.
注意到以下几点：
1.某次称量天平平衡，说明天平两端都是真币.
2.某次天气不平衡，说明这次称量没有用到的都是真币.
3.如果假币比真币重，则假币只可能每次都出现在天平重的一端（轻则相反），所以若某硬币一次出现在重的一端另一次出现在轻了一端则为真币
给每枚硬币一个编码，表示其状态。-1表示没有出现，1表示是真币，0表示可能是假币，且比真币轻，2表示可能是假币，且比真币重。
依据上述观察，每称一次更新一次硬币状态。最终只有一枚硬币不为1。具体见代码。
//////////////////////////////////////////////////////////////////////////
// POJ1013 Counterfeit Dollar
// Memory: 268K Time: 16MS
// Language: C++ Result: Accepted
////////////////////////////////////////////////////////////////////////// #include <iostream>
#include <string>
using namespace std; int main() {
int n;
cin >> n;
for (int i = ; i < n; i++) {
string l[], r[], b[];
int result[];
bool light = false;
for (int i = ; i < ; i++) {
result[i] = -;//未出现
}
cin >> l[] >> r[] >> b[] >> l[] >> r[] >> b[] >> l[] >> r[] >> b[]; for(int i = ; i < ; i++) {
if (b[i].compare("even") == ) {
for (int j = ; j < l[i].size(); j++) {
result[l[i][j] - 'A'] = ;
}
for (int j = ; j < r[i].size(); j++) {
result[r[i][j] - 'A'] = ;
}
} else if (b[i].compare("up") == ) {
bool mark[] = {false, false, false, false, false, false,
false, false, false, false, false, false};
for (int j = ; j < l[i].size(); j++) {
if (result[l[i][j] - 'A'] == -) {
result[l[i][j] - 'A'] = ;
} else if (result[l[i][j] - 'A'] == ) {
result[l[i][j] - 'A'] = ;
}
mark[l[i][j] - 'A'] = true;
}
for (int j = ; j < r[i].size(); j++) {
if (result[r[i][j] - 'A'] == -) {
result[r[i][j] - 'A'] = ;
} else if (result[r[i][j] - 'A'] == ) {
result[r[i][j] - 'A'] = ;
}
mark[r[i][j] - 'A'] = true;
}
for (int t = ; t < ; t++) {
if (mark[t] == false) {
result[t] = ;
}
}
} else {
bool mark[] = {false, false, false, false, false, false,
false, false, false, false, false, false};
for (int j = ; j < l[i].size(); j++) {
if (result[l[i][j] - 'A'] == -) {
result[l[i][j] - 'A'] = ;
} else if (result[l[i][j] - 'A'] == ) {
result[l[i][j] - 'A'] = ;
}
mark[l[i][j] - 'A'] = true;
}
for (int j = ; j < r[i].size(); j++) {
if (result[r[i][j] - 'A'] == -) {
result[r[i][j] - 'A'] = ;
} else if (result[r[i][j] - 'A'] == ) {
result[r[i][j] - 'A'] = ;
}
mark[r[i][j] - 'A'] = true;
}
for (int t = ; t < ; t++) {
if (mark[t] == false) {
result[t] = ;
}
}
}
}
for (int i = ; i < ; i++) {
if (result[i] == ) {
cout << char(i + 'A') << " is the counterfeit coin and it is light." << endl;
break;
} else if (result[i] == ) {
cout << char(i + 'A') << " is the counterfeit coin and it is heavy." << endl;
break;
}
}
}
system("pause");
}
附Discuss里面的一些测试数据：
sample input ABCD EFGH even
ABCI EFJK up
ABIJ EFGH even
AGHL BDEC even
JKI ADE up
J K even
ABCDEF GHIJKL up
ABC DEF even
I J down
ABCDEF GHIJKL up
ABHLEF GDIJKC down
CD HA even
A B up
B A down
A C even
A B up
B C even
DEFG HIJL even
ABC DEJ down
ACH IEF down
AHK IDJ down
ABCD EFGH even
AB IJ even
A L down
EFA BGH down
EFC GHD even
BA EF down
A B up
A C up
L K even
ACEGIK BDFHJL up
ACEGIL BDFHJK down
ACEGLK BDFHJI down
ACEGIK BDFHJL up
ACEGIL BDFHJK down
ACEGLK BDFHJI up sample output
K is the counterfeit coin and it is light.
I is the counterfeit coin and it is heavy.
I is the counterfeit coin and it is light.
L is the counterfeit coin and it is light.
B is the counterfeit coin and it is light.
A is the counterfeit coin and it is heavy.
A is the counterfeit coin and it is light.
L is the counterfeit coin and it is heavy.
A is the counterfeit coin and it is light.
A is the counterfeit coin and it is heavy.
L is the counterfeit coin and it is light.
K is the counterfeit coin and it is heavy.
Test data & answer