OpenJudge NOI 2.1 15:Counterfeit Dollar
假币
莎莉琼斯有12枚航记银元，但是，只有其中的11个是真正的银元，有1枚是伪造的假币，尽管它的颜色和形状大小让它无法与真正的银元区分开来。这个假币与其他硬币的重量不同，但莎莉不知道它与其他硬币相比是更重还是更轻。
幸运的是，莎莉有一个朋友借给了她一个十分精确的天平，这个朋友给了莎莉三次称重的机会来找出那个假币。例如，如果莎莉称两枚硬币且天平平衡，那么她就知道这两枚硬币是真的。现在，如果莎莉将其中一枚真硬币与第三个硬币称重，天平不平衡，那么她就知道第三枚硬币是假币，并且她还能通过天平哪边向上、向下移动来判断那个假币是轻还是重。
通过仔细选择如何称重，莎莉可以保证，她只需要3次称重就可以找到那枚假币。
第一行输入是一个整数n (n>0) 指明有几组测试数据，每组数据由三行输入组成，一行代表一次称重。莎莉用字母A到L标记了所有硬币。每次称重的信息都包括两个字母字符串，与“up”、“down”、“even”三个单词中的一个词。第一个字母字符串表示天平左盘的硬币，第二个字母字符串则是天平右盘的硬币（莎莉总是在天平的左右两盘分别放入相同数量的银元）。第三个位置的单词是表明天平的右边是会向上移动、向下移动，还是保持平衡。
对于每组数据，输出字母来表明哪一个是假币，并判断它是更重还是更轻。解决方案始终唯一确定。
这句话第一个字母为假币对应的字母，最后一个单词为：light（更轻）或heavy（更重）。
East Central North America 1998
一共有A–L共十二枚硬币，其中一枚假币，假币可能更轻或更重。
所以可能的情况有：
0更轻，0更重，1更轻，1更重，…，11更轻，11更重。一共24种情况。
枚举这24种情况，看哪种情况下，输入指定的三次天平比较结果与实际的结果相同。
假设输入为：ABCI EFJK up
如果我假设A是更轻的假币，那么右端应该下沉，实际的结果是右端上翘，与实际结果不同。
如果我假设A是更重的假币，那么右端应该上翘，与实际结果相同。
如果在当前假币情况下，输入指定的三次天平比较的结果与实际结果都相同，那么此时假币的情况就是真实的，可行的。否则该假币情况不可行。
#include<bits/stdc++.h>
using namespace std;
#define N 15
bool hasCh(char s[], char c)//字符串s中是否包含字符c
{
int len = strlen(s);
for(int i = 0; i < len; ++i)
if(s[i] == c)
return true;
return false;
}
void check(bool ishev, bool hl, bool hr, char res[])//ishev表示假币是否更重，hl表示左侧是否有假币 ，hr表示右侧是否有假币，res保存结果字符串
{
if(!hl && !hr)
strcpy(res, "even");
else if(!ishev && !hl && hr || ishev && hl && !hr)//更轻的在右边，或更重的在左边
strcpy(res, "up");
else if(!ishev && hl && !hr || ishev && !hl && hr)//更轻的在左边，或更重的在右边
strcpy(res, "down");
}
int main()
{
char s[4][4][N], lh[2][N] = {"light", "heavy"}, res[N];//输入的字符串
int n;
scanf("%d", &n);
bool isMatch, isHeavy;
while(n--)
{
for(int i = 1; i <= 3; ++i)
scanf("%s %s %s", s[i][1], s[i][2], s[i][3]);
for(char c = 'A'; c <= 'L'; ++c)//假设假币为c
{
for(int k = 0; k < 2; ++k)//假设假币为lh[k]，可能的值为light更轻，或heavy更重
{
isMatch = true, isHeavy = strcmp(lh[k], "heavy") == 0;
for(int j = 1; j <= 3; ++j)//看比较规则j
{
bool hl = hasCh(s[j][1], c), hr = hasCh(s[j][2], c);
check(isHeavy, hl, hr, res);
if(strcmp(res, s[j][3]) != 0)//如果当前假币情况得到的结果与预设结果不同
{
isMatch = false;
break;
}
}
if(isMatch)
{
printf("%c is the counterfeit coin and it is %s.\n", c, lh[k]);
break;
}
}
if(isMatch)
break;
}
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
bool hasCh(string s, char c)//判断s中是否有c
{
for(int i = 0; i < s.length(); ++i)
if(s[i] == c)
return true;
return false;
}
string getRes(char f, string lh, string s1, string s2)//f是假币，lh:字符串 表示更重或更轻，天平两边是s1，s2，看能得到什么结果
{
bool h1 = hasCh(s1, f), h2 = hasCh(s2, f);//h1：s1中是否有f，h2：s2中是否有f
if(h1 == false && h2 == false)
return "even";
else if(h1 == true && h2 == false)
{
if(lh == "heavy")
return "up";
else
return "down";
}
else if(h1 == false && h2 == true)
{
if(lh == "heavy")
return "down";
else
return "up";
}
}
int main()
{
bool isMatch;
int n;
cin >> n;
string s[4][4];
string lh[2] = {"light", "heavy"};
while(n--)
{
for(int i = 1; i <= 3; ++i)
for(int j = 1; j <= 3; ++j)
cin >> s[i][j];
for(char c = 'A'; c <= 'L'; ++c)//假设假币为c
{
for(int k = 0; k < 2; ++k)//假设假币为lh[k]，可能的值为light更轻，或heavy更重
{
isMatch = true;//当前假币情况是否可以让3次天平的结果都是预设结果。
for(int i = 1; i <= 3; ++i)
{
if(getRes(c, lh[k], s[i][1], s[i][2]) != s[i][3])//如果当前假币情况得到的结果与预设结果不同
{
isMatch = false;
break;
}
}
if(isMatch)
{
cout << c << " is the counterfeit coin and it is " << lh[k] << '.' << endl;
break;
}
}
if(isMatch)//如果找到合适的假币，则跳出
break;
}
}
return 0;
}