原題及翻譯

Counterfeit Dollar
假幣
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 52569 Accepted: 16434
時(shí)限：1000毫秒 內(nèi)存限制：10000K
提交總數(shù)：52569 接受：16434
Description
描述
Sally Jones has a dozen Voyageur silver dollars.
薩利·瓊斯有一打旅行銀元。
However, only eleven of the coins are true silver dollars; one coin is counterfeit even though its color and size make it indistinguishable from the real silver dollars.
然而，只有11個(gè)硬幣是真正的銀幣；一個(gè)硬幣是偽造的，盡管它的顏色和大小使它與真正的銀幣無法區(qū)分。
The counterfeit coin has a different weight from the other coins but Sally does not know if it is heavier or lighter than the real coins.
假幣的重量與其他硬幣的重量不同，但莎莉不知道它是否比真正的硬幣重或輕。
Happily, Sally has a friend who loans her a very accurate balance scale.
幸好，莎莉有個(gè)朋友借給她一個(gè)非常精確的天平。
The friend will permit Sally three weighings to find the counterfeit coin.
這位朋友將允許薩利三次稱重以找到假幣。
For instance, if Sally weighs two coins against each other and the scales balance then she knows these two coins are true.
例如，如果莎莉兩個(gè)硬幣相對(duì)重，天平平衡，那么她就知道這兩個(gè)硬幣是真的。
Now if Sally weighs
如果莎莉重了
one of the true coins against a third coin and the scales do not balance then Sally knows the third coin is counterfeit and she can tell whether it is light or heavy depending on whether the balance on which it is placed goes up or down, respectively.
一枚真正的硬幣與一枚第三枚硬幣和天平不平衡，那么莎莉就知道第三枚硬幣是偽造的，她可以根據(jù)放置它的天平是上下來判斷它是輕的還是重的。
By choosing her weighings carefully, Sally is able to ensure that she will find the counterfeit coin with exactly three weighings.
通過仔細(xì)選擇自己的重量，莎莉能夠確保她將找到準(zhǔn)確三個(gè)重量的假幣。

Input

輸入
The first line of input is an integer n (n > 0) specifying the number of cases to follow.
輸入的第一行是一個(gè)整數(shù)n（n>0），指定了要遵循的事例數(shù)。
Each case consists of three lines of input, one for each weighing.
每個(gè)情況由三條輸入線組成，每個(gè)稱重一條。
Sally has identified each of the coins with the letters A–L.
薩利已經(jīng)用字母A–L識(shí)別了每一枚硬幣。
Information on a weighing will be given by two strings of letters and then one of the words up'',down’’, or ``even’’.
關(guān)于稱重的信息將由兩個(gè)字母串給出，然后是單詞“向上”、“向下”或“偶數(shù)”中的一個(gè)。
The first string of letters will represent the coins on the left balance; the second string, the coins on the right balance.
第一串字母代表左邊天平上的硬幣；第二串字母代表右邊天平上的硬幣。
(Sally will always place the same number of coins on the right balance as on the left balance.)
（莎莉總是在右邊的天平上放相同數(shù)量的硬幣，就像在左邊的天平上一樣。）
The word in the third position will tell whether the right side of the balance goes up, down, or remains even.
第三個(gè)位置的單詞會(huì)告訴天平的右邊是上升、下降還是保持平衡。

Output

輸出
For each case, the output will identify the counterfeit coin by its letter and tell whether it is heavy or light.
對(duì)于每種情況，輸出將通過其字母識(shí)別假幣，并判斷它是重的還是輕的。
The solution will always be uniquely determined.
解決方案始終是唯一確定的。

Sample Input

1
ABCD EFGH even
ABCI EFJK up
ABIJ EFGH even

Sample Output

K is the counterfeit coin and it is light.
Source
East Central North America 1998

思路

對(duì)于每一枚硬幣先假設(shè)它是輕的，看這樣是否符合稱量結(jié)果。
如果符合，問題即解決。如果不符合，就假設(shè)它是重的，看是否符合稱量結(jié)果。
把所有硬幣都試一遍，一定能找到特殊硬幣。

代碼

#include <stdio.h> #include <string.h> char left[3][7]; //左邊的稱量硬幣 char right[3][7]; //右邊的稱量硬幣 char result[3][7]; //稱量結(jié)果 bool isfake(char c,bool light); int main () {int n;scanf("%d",&n);while(n--){for(int i=0;i<3;++i){scanf("%s%s%s",left[i],right[i],result[i]);}for(char c='A';c<='L';c++){if(isfake(c,true)){printf("%c is the counterfeit coin and it is light. \n",c);break;} else if(isfake(c,false)){printf("%c is the counterfeit coin and it is heavy. \n",c);break;}}}return 0; } bool isfake(char c,bool light) {for(int i=0;i<3;i++){char *pleft,*pright;if(light){pleft=left[i];pright=right[i];}else{pleft=right[i];pright=left[i];}switch(result[i][0]){//天平右邊的情況case 'u':if(strchr(pright,c)==NULL)return false;break;case 'e':if(strchr(pleft,c)||strchr(pright,c))return false;break;case 'd':if(strchr(pleft,c)==NULL)return false;break;}}return true; }

總結(jié)

以上是生活随笔為你收集整理的Counterfeit Dollar的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。