这是一个古老的题目，12枚硬币称3次，求出其中那枚轻或重的硬币。

    当然，这道题比求解法简单多了，只需求证明。而我们知道，证明一样物体的存在，只需要把与其对立面的物体从物理层面乃至精神层面完全地、不留遗迹地消灭，这点在人类文明史中得到了最有力的支持......因此，最简单的办法是枚举24种情况，然后一一搜索，不满足者剔除即可。但显然这比较笨拙。

    有没有简单一点的办法——假如不是12枚，而是12亿枚？好吧，同样是剔除，我们可以从判断语句入手。

    比如 ABCD EFGH even 我们知道了这八枚都是even的。

    又比如 ABCI EFJK up 我们知道了ABCI里必然有一枚是heavy的，而EFJK必然有一枚light。因此ABCI就是heavy的嫌疑对象，反之亦然。这是可能性。

    从上面的语句中，我们还能得到隐含的条件：DGHL必然是even的。这是必然性。

    所以，只要把不满足必然性的可能性剔除就OK了。

    至于这个问题的解法，大致是用到二分，具体怎么写还有待研究。

#include <iostream>
#include <cstring>
#include <string>
#include <vector>
using namespace std;

int n, b[12], l0, l1, c[12];
string s0, s1, s2;

void proc();
void print();

int main()
{
 //freopen("in.txt", "r", stdin);
 cin >> n;
 int i, k;
 for(i = 0; i < n; i ++)
 {
  memset(b, 0, sizeof(b));
  for(k = 0; k < 3; k ++)
  {
   cin >> s0 >> s1 >> s2;
   l0 = s0.size(), l1 = s1.size();
   proc();
  }
  print();
 }
 return 0;
}

void proc()
{
 int j, t;
 //cout << s0 << " " <<  s1 << " " <<  s2 << endl;
 memset(c, 0, sizeof(c));
 if(s2 == "even") //两边相等
 {
  for(j = 0; j < l0; j ++)
  {
   t = s0[j] - 'A'; 
   if(b[t] == 2) continue;
   b[t] = 2;  //2代表相等
  }
  for(j = 0; j < l1; j ++)
  {
   t = s1[j] - 'A';
   if(b[t] == 2) continue;
   b[t] = 2; 
  } 
 }
 else if(s2 == "up")  //左边重
 {
  for(j = 0; j < l0; j ++)
  {
   t = s0[j] - 'A';
   c[t] = 1;
   if(b[t] == 2) continue;
   if(b[t] == 1) b[t] = 2;  //有1存在说明这是标准重量
   if(!b[t]) b[t] = 3; //3代表重的可能性   
  }  
  for(j = 0; j < l1; j ++)
  {
   t = s1[j] - 'A';
   c[t] = 1;
   if(b[t] == 2) continue;
   if(b[t] == 3) b[t] = 2;  //有3存在说明这是标准重量
   if(!b[t]) b[t] = 1; //1代表轻的可能性   
  } 
  for(j = 0; j < 12; j ++)
  {
   if(!c[j])
   {
    t = j;
    if(b[t] == 2) continue;
    b[t] = 2;
   }
  }
 }
 else if(s2 == "down")  //右边重
 {
  for(j = 0; j < l0; j ++)
  {
   t = s0[j] - 'A';
   c[t] = 1;
   if(b[t] == 2) continue;
   if(b[t] == 3) b[t] = 2;  
   if(!b[t]) b[t] = 1;    
  }  
  for(j = 0; j < l1; j ++)
  {
   t = s1[j] - 'A';
   c[t] = 1;
   if(b[t] == 2) continue;
   if(b[t] == 1) b[t] = 2;  
   if(!b[t]) b[t] = 3;    
  } 
  for(j = 0; j < 12; j ++)
  {
   if(!c[j])
   {
    t = j;
    if(b[t] == 2) continue;
    b[t] = 2;
   }
  }
 }
 //print();
}

void print()
{
 int i;
 for(i = 0; i < 12; i ++)
 {
  if(b[i] == 2) continue;
  if(b[i] == 1)
  {
   printf("%c is the counterfeit coin and it is light.\n", i + 'A');
  }
  if(b[i] == 3)
  {
   printf("%c is the counterfeit coin and it is heavy.\n", i + 'A');
  }
 }
}

评论