• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            Counterfeit Dollar

            該題ZOJ題號為1184 POJ題號為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.

            【分析】該題屬于枚舉范疇。沒有比較巧妙的可以一步到位求出結果的方法,可以一次枚舉這12枚錢幣,假設其為假,然后代入到3次稱量判斷中,如果使三次判斷都成立且判斷結果相同,那么毫無疑問這枚錢幣是假的。首先可以進行預處理,比較結果為EVEN的可以判定兩邊的錢幣都是真的,不必參與到枚舉中來。對于上面的輸入用例,假設K是假的,代入判斷1k不出現,那么兩邊重量應相等,成立。繼續稱量2k出現在右邊,結果是UP,亦成立,且據此知道k是較輕的,因此k在右邊,而天平右邊翹起。下面進行判斷3

            k沒有出現在天平兩邊,而且結果為even成立。通過三次稱量判斷,且結果一致,可以肯定k就是假幣,且較輕。為了說明為題,對于上例假設L是假幣。代入稱量1L不出現,結果even成立,稱量2L不出現,結果為up不成立,因為只有一枚假幣,現假設L為假幣,而在L不出現的情況下天平不平衡,故L不是假幣。按照上述算法進行枚舉,遇到可以肯定是假幣的貨幣時算法終止。

                   需要注意的是當假設一枚硬幣為假且通過三次稱量時,需要判斷三次稱量k的輕重情況是否一致,如果一次推得該硬幣較輕,而另一次卻判斷該硬幣較重,那么該硬幣肯定不是假幣。在判斷是需要注意當左右兩邊都不出現假設為假的硬幣時,需要特殊處理,不能簡單的比較3次硬幣輕重是否相同,在左右兩邊都不出現該硬幣的情況下,不應該把這次測量納入比較的范疇。除此之外需要的就是細心了,本人因為打印的時候多打印了個theWA6次,檢查了半個多小時,有種欲哭無淚的感覺。

            具體代碼如下:

              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];
                    /*對當前假設的硬幣進行判斷*/
             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     }
                    /*判斷結果是否一致*/
             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, 0sizeof(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 (*!= '\0')
             77                 {
             78                     a[*p-'A'= 1;
             79                     ++p;
             80                 }
             81                 p = right[i];
             82                 while (*!= '\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 }

            posts - 12, comments - 1, trackbacks - 0, articles - 1

            Copyright © 李東亮

            久久久久亚洲av综合波多野结衣| 久久久久亚洲Av无码专| 久久免费的精品国产V∧| 亚洲国产精品无码久久青草| 国产日韩久久久精品影院首页 | 亚洲精品无码久久久影院相关影片| 激情五月综合综合久久69| 99久久精品国产一区二区三区| 久久精品九九亚洲精品天堂| 久久久九九有精品国产| 亚洲一区中文字幕久久| 久久久久久国产精品无码下载 | 国产精品日韩深夜福利久久| 97久久精品人人澡人人爽| 精品无码久久久久久国产| 婷婷久久精品国产| 久久精品国产清自在天天线 | 久久美女人爽女人爽| 久久精品?ⅴ无码中文字幕| 色诱久久av| 久久精品中文闷骚内射| 久久久91精品国产一区二区三区| 国内精品久久久久久久亚洲| 色天使久久综合网天天| 伊人久久大香线蕉综合Av| 久久精品视频网| 久久亚洲熟女cc98cm| 国产精品视频久久久| 色播久久人人爽人人爽人人片aV| 三上悠亚久久精品| 日韩美女18网站久久精品| 亚洲精品高清国产一线久久| 久久综合狠狠综合久久激情 | 久久久久99这里有精品10| 91精品国产91久久综合| 亚洲欧美国产日韩综合久久| 久久美女人爽女人爽| 久久精品夜夜夜夜夜久久| 久久久久99精品成人片牛牛影视| 久久99久久99精品免视看动漫| 欧美亚洲国产精品久久|