Counterfeit
Dollar
該題ZOJ題號(hào)為1184， POJ題號(hào)為1013.
題目描述如下：
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. 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. 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. 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.
By choosing her weighings carefully, Sally
is able to ensure that she will find the counterfeit coin with exactly three
weighings.
Input
The first line of input is an integer n (n > 0) specifying the number of
cases to follow. Each case consists of three lines of input, one for each
weighing. Sally has identified each of the coins with the letters A-L.
Information on a weighing will be given by two strings of letters and then one
of the words ``up'', ``down'', or ``even''. 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.) The word in the third position will tell
whether the right side of the balance goes up, down, or remains even.
Output
For each case, the output will identify the counterfeit coin by its letter and
tell whether it is heavy or light. 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.
【分析】該題屬于枚舉范疇。沒有比較巧妙的可以一步到位求出結(jié)果的方法，可以一次枚舉這12枚錢幣，假設(shè)其為假，然后代入到3次稱量判斷中，如果使三次判斷都成立且判斷結(jié)果相同，那么毫無疑問這枚錢幣是假的。首先可以進(jìn)行預(yù)處理，比較結(jié)果為EVEN的可以判定兩邊的錢幣都是真的，不必參與到枚舉中來。對(duì)于上面的輸入用例，假設(shè)K是假的，代入判斷1，k不出現(xiàn)，那么兩邊重量應(yīng)相等，成立。繼續(xù)稱量2，k出現(xiàn)在右邊，結(jié)果是UP，亦成立，且據(jù)此知道k是較輕的，因此k在右邊，而天平右邊翹起。下面進(jìn)行判斷3
，k沒有出現(xiàn)在天平兩邊，而且結(jié)果為even成立。通過三次稱量判斷，且結(jié)果一致，可以肯定k就是假幣，且較輕。為了說明為題，對(duì)于上例假設(shè)L是假幣。代入稱量1，L不出現(xiàn)，結(jié)果even成立，稱量2，L不出現(xiàn)，結(jié)果為up不成立，因?yàn)橹挥幸幻都賻?，現(xiàn)假設(shè)L為假幣，而在L不出現(xiàn)的情況下天平不平衡，故L不是假幣。按照上述算法進(jìn)行枚舉，遇到可以肯定是假幣的貨幣時(shí)算法終止。
需要注意的是當(dāng)假設(shè)一枚硬幣為假且通過三次稱量時(shí)，需要判斷三次稱量k的輕重情況是否一致，如果一次推得該硬幣較輕，而另一次卻判斷該硬幣較重，那么該硬幣肯定不是假幣。在判斷是需要注意當(dāng)左右兩邊都不出現(xiàn)假設(shè)為假的硬幣時(shí)，需要特殊處理，不能簡單的比較3次硬幣輕重是否相同，在左右兩邊都不出現(xiàn)該硬幣的情況下，不應(yīng)該把這次測量納入比較的范疇。除此之外需要的就是細(xì)心了，本人因?yàn)榇蛴〉臅r(shí)候多打印了個(gè)the，WA了6次，檢查了半個(gè)多小時(shí)，有種欲哭無淚的感覺。
具體代碼如下：
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4
5 char left[3][7], right[3][7];
6 char result[3][6];
7 int a[15];
8 int w;
9
10 int judge(char ch)
11 {
12 int r1, r2;
13 int i;
14 int a[3];
/*對(duì)當(dāng)前假設(shè)的硬幣進(jìn)行判斷*/
15 for (i = 0; i < 3; ++i)
16 {
17 r1 = strcmp(result[i], "even");
18 r2 = strcmp(result[i], "up");
19 if (strchr(left[i], ch) != NULL)
20 {
21 if (r1 == 0)
22 return 0;
23 else if (r2 == 0)
24 a[i] = 1;
25 else
26 a[i] = -1;
27 }
28 else if (strchr(right[i], ch) != NULL)
29 {
30 if (r1 == 0)
31 return 0;
32 else if (r2 == 0)
33 a[i] = -1;
34 else
35 a[i] = 1;
36 }
37 else
38 {
39 if (r1 != 0)
40 return 0;
41 a[i] = 3;
42 }
43 }
/*判斷結(jié)果是否一致*/
44 if (a[0] != 3)
45 w = a[0];
46 else if (a[1] != 3)
47 w = a[1];
48 else if (a[2] != 3)
49 w = a[2];
50 for (i = 0; i < 3; ++i)
51 {
52 if (a[i] != 3 && a[i] != w)
53 {
54 return 0;
55 }
56 }
57 return 1;
58 }
59 int main(void)
60 {
61 int n;
62 int i;
63 char *p;
64 char ch;
65 int r;
66 scanf("%d%*c", &n);
67 while (n--)
68 {
69 memset(a, 0, sizeof(a));
70 for (i = 0; i < 3; ++i)
71 {
72 scanf("%s%s%s", left[i], right[i], result[i]);
73 if (strcmp (result[i], "even") == 0)
74 {
75 p = left[i];
76 while (*p != '\0')
77 {
78 a[*p-'A'] = 1;
79 ++p;
80 }
81 p = right[i];
82 while (*p != '\0')
83 {
84 a[*p-'A'] = 1;
85 ++p;
86 }
87 }
88 }
89 for (ch = 'A'; ch <= 'L'; ++ch)
90 {
91 if (a[ch-'A'] == 1)
92 continue;
93 r = judge(ch);
94 if (r == 1)
95 {
96 if (w > 0)
97 {
98 printf("%c is the counterfeit coin and it is heavy.\n", ch);
99 }
100 else
101 {
102 printf("%c is the counterfeit coin and it is light.\n", ch);
103 }
104 break;
105 }
106 }
107 }
108 return 0;
109 }