ACM 1013 Counterfeit Dollar

问题描述:
        Sally有12枚银币,其中有11枚是真的,1枚是假的。假的这枚在外形、色泽上与真的无异,但是质量上有差距。可能比真的重,也可能比真的轻。幸运的是Sally借到了一个天平,有3次机会来称量决出其中的假币。规定每次放到天平两端的银币数目是一样的,最终还需要找出假币的质量是轻,还是重。

分析:
        这道题其实是很简单的,没有什么算法的东西在里面,就是个模拟题。但是有几点是需要注意的:
      (1)不要被样例输入所影响,每次放到天平上的物品数最多有6个,最少有1个,不一定是4个。
      (2)3次称量,每次放上去的数目也不一定是相同的。

我的思路是:
         
开辟一个数组来存放已经确定为真币的银币,初始化为0,然后逐行读取数据,根据称得的结果来确定真币。对于天平平衡的情况来说,比较简单,两边的银币肯定都是真的,数组中对应的数值为1,表示确定是真币了。但是对于左边重或者右边重的就不好说了,要分两种情况,一种是假币比真币轻,一种是假币比真币重,根据情况修改数组元素,2表示可能比真币重,3表示可能比真币轻。但是里面其实还有一些小细节需要考虑。具体看代码。
  1#include<stdio.h>
  2#include<string.h>
  3
  4int i=0,j=0;
  5int rec[12]={0};
  6int doubt[12]={0};//加上怀疑次数
  7char left[3][7]; //左边的数组
  8char right[3][7];  //右边的数组
  9char were[3][5];//比较结果
 10//寻找轻球
 11int light()
 12{
 13    for(i=0;i<3;i++)
 14      {
 15         switch(were[i][0])
 16         {
 17             case 'e':
 18                 for(j=0;j<strlen(left[i]);j++)
 19                 {
 20                     int l=left[i][j]-65;int r=right[i][j]-65;
 21                      rec[l]=1;//表示它是确定了真的
 22                      rec[r]=1;//表示它是确定了真的
 23                    }

 24                 break;
 25             case 'u':
 26                   for(j=0;j<strlen(left[i]);j++)
 27                  {
 28                     int l=left[i][j]-65;int r=right[i][j]-65;
 29                      rec[l]=1;//表示它是真的
 30                    if(rec[r]!=1)//表示对它进行的两次判断是矛盾的
 31                    { rec[r]=3; doubt[r]++;}
 32                  }

 33                 break;
 34             case 'd':
 35                  for(j=0;j<strlen(left[i]);j++)
 36                  {
 37                     int l=left[i][j]-65;int r=right[i][j]-65;
 38                        rec[r]=1;//表示它是真的
 39                     if(rec[l]!=1)//就表示这个地方已经被确定过了,有矛盾了
 40                     {rec[l]=3;doubt[l]++;}
 41                  }

 42                 break;
 43             }

 44        }

 45       int maxdoubt0=-1,k=-1,num=0;
 46        for(i=0;i<12;i++)
 47        {
 48         switch(rec[i])
 49         {
 50             case 3:if(doubt[i]>maxdoubt0)
 51                   { num=0;maxdoubt0=doubt[i];k=i;}
 52                   if(doubt[i]==maxdoubt0&&i!=k)
 53                      num++;
 54                     break;
 55             case 1:break;
 56             case 0:break;
 57            }

 58          }

 59         if(num==0return k;
 60        else return -1;
 61    }

 62//寻找重球
 63int heavy()
 64{
 65    for(i=0;i<3;i++)
 66      {
 67         switch(were[i][0])
 68         {
 69             case 'e'for(j=0;j<strlen(left[i]);j++)
 70                    {
 71                     int l=left[i][j]-65;int r=right[i][j]-65;
 72                      rec[l]=1;//表示它是确定了真的
 73                      rec[r]=1;//表示它是确定了真的
 74                     }

 75                      break;
 76             case 'u'for(j=0;j<strlen(left[i]);j++)
 77                    {
 78                     int l=left[i][j]-65;int r=right[i][j]-65;
 79                      rec[r]=1;//表示它是真的
 80                    if(rec[l]!=1)
 81                    {rec[l]=2;doubt[l]++;}
 82                    }

 83                      break;
 84             case 'd'for(j=0;j<strlen(left[i]);j++)
 85                    {
 86                      int l=left[i][j]-65;int r=right[i][j]-65;
 87                         rec[l]=1;//表示它是真的
 88                     if(rec[r]!=1)
 89                     {rec[r]=2;doubt[r]++;}
 90                     }

 91                 break;
 92             }

 93        }

 94       int maxdoubt0=-1,k=-1;
 95        for(i=0;i<12;i++)
 96        {
 97         switch(rec[i])
 98         {
 99             case 2:if(doubt[i]>maxdoubt0)
100                  { maxdoubt0=doubt[i];k=i;}
101                     break;
102             case 1break;
103             case 0break;
104            }

105         }

106        return k;
107}

108int main()
109{
110    int n;
111    char c;
112    freopen("1013test.txt","r",stdin);
113    scanf("%d",&n);
114    c=getchar();
115     while(n--)
116      {
117        //3表示它被怀疑是轻的,1表示确定了是真的,2表示它被怀疑是重的,0表示不确定。
118         memset(rec,0,12*sizeof(int));
119         memset(doubt,0,12*sizeof(int));
120         //初始化
121         for(i=0;i<3;i++)
122         {
123           memset(left+i,'\0',7*sizeof(char));
124           memset(right+i,'\0',7*sizeof(char));
125           memset(were+i,'\0',4*sizeof(char));
126             }

127
128        for(i=0;i<3;i++)
129        {
130             for(j=0;j<7;j++)
131               {
132                  scanf("%c",&c);
133                   if(c==' 'break;
134                   else left[i][j]=c;}

135             for(j=0;j<7;j++)
136               {
137                 scanf("%c",&c);
138                   if(c==' 'break;
139                   else right[i][j]=c;}

140            for(j=0;j<5;j++)
141               {
142                scanf("%c",&c);
143                   if(c=='\n'break;
144                   else were[i][j]=c;}

145            }

146      //测试思路是这样的:这个要分成两种情况,假设里面有个轻球和假设里面有个重球
147       int k=light();//假设里面有个轻球
148       if(k==-1)//轻球失败
149        {
150            memset(rec,0,12*sizeof(int));
151            memset(doubt,0,12*sizeof(int));
152            k=heavy();//假设里面是个重球
153            k=k+65;
154            printf("%c is the counterfeit coin and it is heavy.\n",k);
155        }

156       else
157        {
158          k=k+65;
159           printf("%c is the counterfeit coin and it is light.\n",k);
160        }

161    }

162    return 0;
163}

164

   汗!!代码好长啊,关键是自己对字符输入方面有点不精通。
      

posted on 2010-12-19 16:42 Bamboo 阅读(391) 评论(0)  编辑 收藏 引用 所属分类: ACM题目解析


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

导航

统计

常用链接

留言簿

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜