Morris' Blog

2011-06-30 18:08:47Morris

c093. Counterfeit Dollar

留言 0 收藏 0 推薦 0

內容：

Sally 有一打銀幣（十二個），可是只有11個是真的，有一個是假的（但是它的顏色和大小都和真的一樣）。還好那個假幣的重量和真的不一樣，不過 sally 不知道它到底是比真的輕還是重。

可喜的是， sally 有個朋友借他一個非常精準的天平，那個朋友同意讓 Sally 秤三次來找出假幣。例如，秤2個硬幣，結果天平平衡，那麼這2個都是真的。如果用其中的一個真的和第三個硬幣去秤，如果天平不平衡，那麼 sally就知道第三個硬幣是假的。同時他也可以根據天平來判斷那個假的到底是比真的輕還是重。Sally 會小心的選擇秤重的方法，這樣他才能用剛好秤三次找出那個硬幣是假的。

輸入說明：

輸入的第一列有一個整數 n，代表以下有幾組測試資料。

每組測試資料三列，每列代表一次秤重。Sally 把他的硬幣編號為A～L。每次秤重左右兩邊的硬幣用2個字串表示（Sally 總是在左右兩邊放相同數目的硬幣），秤重的結果用 up, down, even 來表示，代表天平的右邊是往上，往下，還是平衡。請參考Sample Input。

輸出說明：

對每一組測試資料輸出哪一個硬幣是假的，並且是較輕還是較重。請注意：答案一定是唯一的。輸出格式請參考Sample Output。

範例輸入：

2
ABCD EFGH even
ABCI EFJK up
ABIJ EFGH even
ABC DEF up
GHI JKL even
EF DA up

範例輸出：

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

提示：

* 中文翻譯：Lucky 貓英中

出處：

ACM 608

作法 : 窮舉
舉出哪個硬幣是錯誤的，看是light or heavy
看三個條件，有沒有都符合就好哩
我以為是很繁複的做法，我真是被嚇到了，一嚇三年不敢寫

/**********************************************************************************/
/* Problem: c093 "Counterfeit Dollar" from ACM 608                               */
/* Language: C                                                                   */
/* Result: AC (2ms, 262KB) on ZeroJudge                                          */
/* Author: morris1028 at 2011-06-30 17:27:59                                     */
/**********************************************************************************/

#include<stdio.h>
#include<string.h>
struct record {
   char l[13], r[13], st[4];
}D[3];
main() {
   int t, a, b, c, suml, sumr;
   scanf("%d", &t);
   while(t--) {
       for(a = 0; a < 3; a++)
           scanf("%s %s %s", &D[a].l, &D[a].r, &D[a].st);
       /*light*/
       for(a = 0; a < 12; a++) {
           for(b = 0; b < 3; b++) {
               suml = 0, sumr = 0;
               for(c = 0; D[b].l[c]; c++)
                   suml += (D[b].l[c] - 'A' != a);
               for(c = 0; D[b].r[c]; c++)
                   sumr += (D[b].r[c] - 'A' != a);
               if(suml == sumr && D[b].st[0] == 'e') continue;
               if(suml < sumr && D[b].st[0] == 'd') continue;
               if(suml > sumr && D[b].st[0] == 'u') continue;
               break;
           }
           if(b == 3)   break;
       }
       if(a != 12)
           printf("%c is the counterfeit coin and it is light.\n", a + 'A');
       /*heavy*/
       for(a = 0; a < 12; a++) {
           for(b = 0; b < 3; b++) {
               suml = 0, sumr = 0;
               for(c = 0; D[b].l[c]; c++)
                   suml += (D[b].l[c] - 'A' == a);
               for(c = 0; D[b].r[c]; c++)
                   sumr += (D[b].r[c] - 'A' == a);
               if(suml == sumr && D[b].st[0] == 'e') continue;
               if(suml < sumr && D[b].st[0] == 'd') continue;
               if(suml > sumr && D[b].st[0] == 'u') continue;
               break;
           }
           if(b == 3)   break;
       }
       if(a != 12)
           printf("%c is the counterfeit coin and it is heavy.\n", a + 'A');
   }
   return 0;
}

上一篇：c100. Unidirectional TSP

下一篇：c095. False coin

Morris' Blog

c093. Counterfeit Dollar

你可能感興趣的文章

【珠海慘案後】中國遍地「獻忠」，有救嗎？

Artigo

12款中西家常菜 / 甜點

實踐第23天

感恩