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

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是假的,代入判斷1,k不出現,那么兩邊重量應相等,成立。繼續稱量2k出現在右邊,結果是UP,亦成立,且據此知道k是較輕的,因此k在右邊,而天平右邊翹起。下面進行判斷3

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

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

具體代碼如下:

  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 © 李東亮

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            亚洲视频国产视频| 亚洲日本成人| 亚洲在线观看| 99pao成人国产永久免费视频| 欧美国产视频在线| 在线中文字幕不卡| 亚洲小视频在线观看| 国产欧美一区二区精品忘忧草| 欧美在线一二三四区| 久久av最新网址| 在线日韩av片| 国产精品综合久久久| 一区二区三区**美女毛片| 在线播放中文一区| 欧美福利视频网站| 欧美日韩免费在线观看| 午夜激情亚洲| 美玉足脚交一区二区三区图片| 日韩视频中文字幕| 香蕉久久一区二区不卡无毒影院 | 欧美激情亚洲自拍| 亚洲欧美另类在线| 久久久久成人精品免费播放动漫| 欧美r片在线| 亚洲电影激情视频网站| 亚洲电影在线看| 欧美成人嫩草网站| 欧美亚洲一区在线| 免费在线成人av| 午夜精品亚洲| 欧美成人免费一级人片100| 亚洲图片欧美午夜| 久久久精品2019中文字幕神马| 亚洲三级免费| 欧美一区二区三区婷婷月色| 亚洲日本一区二区| 欧美亚洲系列| 一区二区三区免费观看| 久久国产夜色精品鲁鲁99| 亚洲精品精选| 久久精品成人| 亚洲免费视频成人| 欧美精品观看| 99在线热播精品免费| 亚洲午夜精品在线| 亚洲精品亚洲人成人网| 午夜精品亚洲一区二区三区嫩草| 亚洲国产美女| 久久久99免费视频| 欧美一区二区高清| 欧美视频精品在线观看| 欧美激情一区在线| 黑丝一区二区| 欧美亚洲一区二区在线| 亚洲尤物在线| 欧美日韩中文另类| 亚洲日本成人| 亚洲九九爱视频| 免费观看成人www动漫视频| 久久综合久久久| 国语自产精品视频在线看| 亚洲在线一区二区| 亚洲欧美日韩国产精品| 欧美三级视频| 亚洲卡通欧美制服中文| 欧美午夜片在线免费观看| 亚洲国产精品电影| 亚洲国产精品女人久久久| 久久精品国产91精品亚洲| 欧美一区二区三区另类| 欧美午夜精品久久久久久久 | 亚洲国产欧美一区二区三区同亚洲| 欧美一级久久久久久久大片| 久久国产精品久久久| 国产亚洲精品久久久久动| 欧美一区免费视频| 另类酷文…触手系列精品集v1小说| 国产午夜精品视频| 久久免费观看视频| 欧美国产精品人人做人人爱| 亚洲日本激情| 欧美丝袜一区二区三区| 亚洲在线视频一区| 嫩模写真一区二区三区三州| 亚洲国产精品ⅴa在线观看 | 狠狠色狠狠色综合人人| 性色av一区二区怡红| 乱码第一页成人| 亚洲三级电影全部在线观看高清| 欧美日韩成人综合在线一区二区| 一区二区三区成人| 久久久亚洲精品一区二区三区 | 国产日韩欧美精品一区| 久久全国免费视频| 亚洲精品激情| 欧美在线综合| 亚洲精品久久在线| 国产精品美女诱惑| 久久久精品一区| 99亚洲一区二区| 久久综合婷婷| 99国产精品久久久| 韩日精品视频| 欧美日韩一区视频| 久久国产精品免费一区| 亚洲精品人人| 久久人91精品久久久久久不卡| 国产精品久久9| 日韩一区二区精品| 久久综合激情| 亚洲欧美日韩中文视频| 影音先锋亚洲精品| 国产精品久久久久9999吃药| 久久九九99| 一本高清dvd不卡在线观看| 猛干欧美女孩| 欧美亚洲专区| 亚洲一本视频| 亚洲人久久久| 伊人狠狠色j香婷婷综合| 国产精品高潮在线| 欧美久久久久久久久| 久久久久免费观看| 香蕉成人伊视频在线观看| 99精品欧美一区二区蜜桃免费| 裸体歌舞表演一区二区| 欧美制服丝袜| 香蕉精品999视频一区二区| 99国产精品久久久久久久久久| 亚洲国产成人在线| 国产综合18久久久久久| 欧美激情精品久久久久久蜜臀 | 亚洲欧美精品| 亚洲精品欧洲精品| 亚洲国产影院| 欧美激情a∨在线视频播放| 久久精品免费| 久久精品网址| 久久久.com| 久久久91精品国产| 欧美在线视频一区| 亚欧美中日韩视频| 欧美一区二区在线免费播放| 亚洲一线二线三线久久久| 在线中文字幕日韩| 亚洲天堂av图片| 亚洲一区二区视频| 亚洲欧美色一区| 西瓜成人精品人成网站| 欧美一二三区在线观看| 午夜精品久久久久久久99水蜜桃| 亚洲一区国产精品| 亚洲欧美制服中文字幕| 亚洲欧美色婷婷| 久久青草欧美一区二区三区| 久久这里有精品15一区二区三区| 久久免费国产精品| 欧美大片免费观看| 欧美一区二区三区四区在线| 欧美综合国产| 久久一日本道色综合久久| 欧美不卡视频一区发布| 欧美激情精品久久久久久久变态| 欧美日韩国产影片| 国产精品久久久一区二区三区| 国产免费观看久久黄| 今天的高清视频免费播放成人| 亚洲高清不卡一区| 一本色道久久88综合亚洲精品ⅰ | 久久综合色天天久久综合图片| 嫩草伊人久久精品少妇av杨幂| 亚洲激情社区| 亚洲视频免费观看| 久久久久久久国产| 欧美日韩成人综合| 激情欧美一区二区三区| 亚洲毛片av| 久久精品一区二区三区四区| 国内精品久久久久久影视8| 欧美久久影院| 国产精品无码专区在线观看| 韩国精品主播一区二区在线观看| 亚洲电影av| 亚洲一区在线播放| 毛片av中文字幕一区二区| 亚洲美女黄网| 欧美一区二区三区男人的天堂| 欧美国产免费| 国产在线日韩| 亚洲综合欧美日韩| 91久久久久久国产精品| 午夜影视日本亚洲欧洲精品| 牛人盗摄一区二区三区视频| 国产美女扒开尿口久久久| 亚洲免费观看在线视频| 久久久99精品免费观看不卡| 日韩视频不卡中文| 裸体一区二区三区| 国产综合一区二区| 亚洲欧美日韩综合|