青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

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是假幣。代入稱量1L不出現(xiàn),結(jié)果even成立,稱量2L不出現(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,WA6次,檢查了半個(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, 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 }


只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


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

Copyright © 李東亮

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            99国产精品久久久| 精品成人a区在线观看| 亚洲精品免费在线| 亚洲国产视频一区| 美女精品在线| 一区二区三区视频在线| 日韩一区二区免费高清| 国产美女一区二区| 蜜桃av一区二区三区| 欧美刺激午夜性久久久久久久| 99re8这里有精品热视频免费| 一本色道久久综合| 国产真实精品久久二三区| 欧美a级片网| 欧美色图天堂网| 久久久午夜电影| 欧美黄色免费网站| 欧美一区二区三区精品| 久久久久国产精品厨房| 99精品欧美一区二区蜜桃免费| 亚洲小说春色综合另类电影| 在线观看亚洲视频| 99热这里只有成人精品国产| 国产中文一区| 中文亚洲欧美| 亚洲黄页视频免费观看| 亚洲视频一二三| 亚洲国产成人av在线| 日韩系列欧美系列| 一区二区三区在线高清| 夜色激情一区二区| 在线观看日韩精品| 亚洲尤物视频在线| 99视频精品| 久久久午夜电影| 欧美一区二区视频在线| 欧美极品在线播放| 另类春色校园亚洲| 国产精品主播| 亚洲精品中文在线| 亚洲第一在线综合在线| 性高湖久久久久久久久| 亚洲天堂黄色| 欧美激情黄色片| 男女av一区三区二区色多| 国产精品亚洲精品| 99视频精品免费观看| 亚洲精品影院在线观看| 久久这里只有| 久久手机免费观看| 国产欧美 在线欧美| 亚洲视频一区二区在线观看 | 国产一区二区三区在线观看免费视频| 亚洲激情一区二区| 亚洲国产黄色片| 久久伊伊香蕉| 久久综合影视| 国产视频久久| 久久国产精品色婷婷| 欧美中文在线字幕| 国产视频亚洲| 久久福利资源站| 久久亚洲一区二区| 精品成人免费| 久久五月天婷婷| 免费在线亚洲| 亚洲国产黄色| 欧美精品电影在线| 日韩视频一区二区三区| 亚洲天堂av在线免费| 国产精品爱久久久久久久| 亚洲另类自拍| 午夜精品影院| 国产自产女人91一区在线观看| 久久动漫亚洲| 欧美丰满高潮xxxx喷水动漫| 亚洲国产精品日韩| 欧美另类在线观看| 一片黄亚洲嫩模| 欧美在线亚洲一区| 在线看片成人| 欧美日韩激情小视频| 亚洲无毛电影| 噜噜噜噜噜久久久久久91 | 欧美人成网站| 中文av一区特黄| 久久久久久久综合| 亚洲黄色天堂| 欧美性开放视频| 久久国产精品久久久久久久久久 | 中文欧美日韩| 国产婷婷色一区二区三区在线 | 午夜精品国产精品大乳美女| 久久视频一区二区| 日韩亚洲一区二区| 国产日韩欧美中文在线播放| 蜜臀av国产精品久久久久| 99re8这里有精品热视频免费| 欧美在线视频a| 最新日韩中文字幕| 国产欧美日本| 欧美国产三区| 久久精品国产一区二区三| 亚洲美女av网站| 美女91精品| 亚洲一级特黄| 亚洲欧洲精品一区二区三区 | 亚洲欧美久久| 亚洲欧洲在线一区| 国产日韩欧美高清| 欧美日韩免费| 美女被久久久| 欧美中文字幕精品| 亚洲午夜激情免费视频| 亚洲国产综合在线看不卡| 欧美一区二区啪啪| 亚洲桃色在线一区| 亚洲美女黄网| 亚洲国产精品成人精品| 国产欧美日韩一区二区三区在线观看| 欧美国内亚洲| 理论片一区二区在线| 欧美一区精品| 亚洲一区二三| 亚洲一区二区三区欧美| 99国产精品久久久久久久| 欧美成人国产| 免费在线亚洲欧美| 狼人天天伊人久久| 久久久久久穴| 久久精品一区二区国产| 午夜亚洲性色福利视频| 在线视频日韩| 亚洲视频网在线直播| 9i看片成人免费高清| 91久久嫩草影院一区二区| 激情综合久久| 在线免费日韩片| 在线国产精品播放| 亚洲福利视频专区| 在线观看精品视频| 在线欧美视频| 亚洲精品久久久蜜桃 | 欧美视频不卡中文| 欧美日韩中文字幕综合视频| 欧美精品亚洲二区| 欧美日韩精品免费在线观看视频| 欧美精品一区在线观看| 欧美日韩国产综合新一区| 欧美日韩在线精品| 国产精品www色诱视频| 国产精品久久久久久久久久直播| 国产精品男女猛烈高潮激情| 国产区欧美区日韩区| 韩国在线视频一区| 91久久久久久国产精品| 9人人澡人人爽人人精品| 亚洲午夜精品久久久久久浪潮| 亚洲制服av| 久久久精彩视频| 男人的天堂成人在线| 91久久精品一区| 亚洲午夜久久久| 久久精品国产免费观看| 欧美11—12娇小xxxx| 欧美日韩亚洲天堂| 国产拍揄自揄精品视频麻豆| 国内自拍一区| 夜夜躁日日躁狠狠久久88av| 亚洲欧美综合| 麻豆精品一区二区av白丝在线| 亚洲高清一二三区| 亚洲一区二区在线免费观看视频| 久久成人18免费观看| 欧美精品一区二区三区蜜桃| 国产欧美一级| 亚洲精品偷拍| 久久久国产91| 亚洲毛片一区二区| 久久久久国产一区二区三区四区| 欧美精品亚洲| 在线观看国产日韩| 午夜精品久久久久影视| 欧美a级大片| 亚洲综合日韩在线| 欧美电影打屁股sp| 国产一区二区福利| 亚洲午夜av在线| 欧美大片在线观看| 午夜精品99久久免费| 欧美日韩成人一区| 亚洲高清不卡av| 欧美在线观看视频在线| 日韩一级视频免费观看在线| 久久综合色综合88| 国产欧美欧美| 亚洲影院在线| 亚洲精品国产精品国产自| 久久色在线播放| 国内偷自视频区视频综合|