题目链接:http://poj.org/problem?id=1013
题目大意
有12枚硬币。其中有11枚真币和1枚假币。假币和真币重量不同,但不知道假币比真币轻还是重。现在,用一架天平称了这些币三次,告诉你称的结果,请你找出假币并且确定假币是轻是重(数据保证一定能找出来)。
输入第一行是测试数据组数。每组数据有三行,每行表示一次称量的结果。银币标号为A-L。每次称量的结果用三个以空格隔开的字符串表示:天平左边放置的硬币、天平右边放置的硬币、平衡状态。其中平衡状态用``up'', ``down'', 或 ``even''表示, 分别为右端高、右端低和平衡。天平左右的硬币数总是相等的。
输出输出哪一个标号的银币是假币,并说明它比真币轻还是重 。
输入样例1ABCD EFGH evenABCI EFJK upABIJ EFGH even输出样例K is the counterfeit coin and it is light.
解题思路
来源:北大郭炜老师
对于每一枚硬币先假设它是轻的,看这样是否符合称量结果。如果符合,问题即解决。如果不符合,就假设它是重的,看是否符合称量结果。
把所有硬币都试一遍,一定能找到特殊硬币。
1 #include2 #include 3 using namespace std; 4 char Left[3][7]; //天平左边硬币 5 char Right[3][7]; //天平右边硬币 6 char result[3][7]; //称量结果 7 bool IsFake(char c,bool light);//light为真表示假设假币为轻,否则表示假设假币为重 8 int main() 9 {10 int t;11 cin >> t;12 while(t--) 13 {14 for(int i = 0;i < 3; ++i) cin >> Left[i] >> Right[i] >> result[i];15 for(char c='A'; c<='L';c++)16 {17 if( IsFake(c,true) )//假设c这个硬币为假硬币而且它比真硬币轻18 {19 cout << c << " is the counterfeit coin and it is light.\n";20 break;21 }22 else if( IsFake(c,false) )//假设c这个硬币为假硬币而且它比真硬币重23 {24 cout << c << " is the counterfeit coin and it is heavy.\n";25 break;26 }27 }28 }29 return 0; 30 }31 bool IsFake(char c,bool light)//light 为真表示假设假币为轻,否则表示假设假币为重32 {33 for(int i = 0;i < 3; ++i) 34 {35 char * pLeft,*pRight; //指向天平两边的字符串36 if(light)37 {38 pLeft = Left[i];39 pRight = Right[i];40 }41 else42 {43 pLeft = Right[i];44 pRight = Left[i];45 }46 47 switch(result[i][0])48 {49 case 'u':50 if ( strchr(pRight,c) == NULL) return false;51 break;52 case 'e':53 if( strchr(pLeft,c) || strchr(pRight,c)) return false;54 break;55 case 'd':56 if ( strchr(pLeft,c) == NULL) return false;57 break;58 }59 }60 return true;61 }