总时间限制: 1000ms 内存限制: 65536kB

描述

赛利有12枚银币。其中有11枚真币和1枚假币。假币看起来和真币没有区别，但是重量不同。但赛利不知道假币比真币轻还是重。于是他向朋友借了一架天平。朋友希望赛利称三次就能找出假币并且确定假币是轻是重。例如:如果赛利用天平称两枚硬币，发现天平平衡，说明两枚都是真的。如果赛利用一枚真币与另一枚银币比较，发现它比真币轻或重，说明它是假币。经过精心安排每次的称量，赛利保证在称三次后确定假币。

输入

第一行有一个数字n，表示有n组测试用例。
对于每组测试用例：
输入有三行，每行表示一次称量的结果。赛利事先将银币标号为A-L。每次称量的结果用三个以空格隔开的字符串表示：天平左边放置的硬币 天平右边放置的硬币 平衡状态。其中平衡状态用 “up’’, “down’’, 或 “even’’表示, 分别为右端高、右端低和平衡。天平左右的硬币数总是相等的。

输出

输出哪一个标号的银币是假币，并说明它比真币轻还是重(heavy or light)。

样例输入

  1. 1 
  2. ABCD EFGH even 
  3. ABCI EFJK up 
  4. ABIJ EFGH even

样例输出

  1. K is the counterfeit coin and it is light.

思路

由于没有一个通用的数学公式来证明哪个硬币是假币, 所以我们采用枚举每一枚硬币的做法来找到假币.

我们可以这样假设:

假设硬币 c 是假币, 并且它是轻的. 如果 c 出现在天平的右边, 那么天平右边就会翘起来(up); 如果 c 出现在天平左边, 那么天平右边就会沉下去(down). 我们用C语言函数 strchr() 来查找一个 c 是否在字符串中.

我们用一个二维数组来存硬币的集合. 因为我们的样本容量只有12个, 所以天平一边最多可以放6个.

我们写一个函数 isFake(char coin, bool light) 来帮我们检测传入的 coin 是不是假币. 第二个参数如果是 true, 则我们假设 coin 是轻的假币; 如果是 false, 则假设 coin 是重的假币.

代码

  1. #include<iostream>
  2. #include<cstring>
  3. using namespace std;
  5. char LEFT[3][7];    /* 天平一边最多放6个硬币 */
  6. char RIGHT[3][7];
  7. char RESULT[3][7];
  9. bool isFake(char coin, bool light) { /* light 为真表示假设假币为轻, 否则为重 */
  10.     for(int i = 0; i < 3; i++) {
  11.         char *pLEFT, *pRIGHT;   /* 指向天平两边的字符串 */
  12.         if(light) {
  13.             pLEFT = LEFT[i];
  14.             pRIGHT = RIGHT[i];
  15.         }
  16.         else {  /* 如果假币是重的, 则把称量结果左右对换 */
  17.             pLEFT = RIGHT[i];
  18.             pRIGHT = LEFT[i];
  19.         }
  21.         switch(RESULT[i][0]) {  /* 天平右边的情况 */
  22.             case 'u':
  23.                 if(strchr(pRIGHT, coin) == NULL)  return false;
  24.                 break;
  25.             case 'e': 
  26.                if(strchr(pLEFT, coin) || strchr(pRIGHT, coin))  return false;
  27.                break;
  28.             case 'd':
  29.                if(strchr(pLEFT, coin) == NULL)  return false;
  30.                break;
  31.         }
  32.     }
  33.     return true;
  34. }
  36. int main() {
  37.     int number;
  38.     cin >> number;
  39.     while(number--) {
  40.         for(int i = 0; i < 3; i++)
  41.             cin >> LEFT[i] >> RIGHT[i] >> RESULT[i];
  42.         for(char coin = 'A'; coin <= 'L'; coin++) {
  43.             if(isFake(coin, true)) {
  44.                 printf("%c is the counterfeit coin and it is light.\n", coin);
  45.                 break;
  46.             }
  47.             else if(isFake(coin, false)) {
  48.                 printf("%c is the counterfeit coin and it is heavy.\n", coin);
  49.                 break;
  50.             }
  51.         }
  52.     }
  53.     return 0;
  54. }