poj 1013 Counterfeit Dollar

本文主要是介绍poj 1013 Counterfeit Dollar，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

首先我们用coin[]数组来记录，具体的对应关系的话，我们将A-L分别对应数字0-11，所以对于每个char，我们减一个‘A’就行了，这样可以对应到int coin[]上去。
首先我们明确一下：
1.如果是even的话，每一个硬币都是真的
2.如果不是的话，它有可能是真的，或者是假的。因为我先遍历了一次三个string ，遇到even的话，就把对应的coin数组中的编号给置为1了，代表这个硬币是真的，而且程序开始的时候我又memset了一下coin数组，全部置零，代表不知道是真的还是假的。有一点很关键，就是12个硬币中只有一个是假的，所以我们输出的一定不是“不知道是真的还是假的”的那枚硬币，而且一个可以确定是假的硬币，同时硬币有轻重之分，我们用一个较大的正数代表是重的硬币，一个较大的负数代表是轻的硬币，这里我取得是100.

再接着说程序的思路，遍历完string确定好even代表的真的硬币后，我们来找假硬币。我们先假设除了真的其余都是假的，再重新遍历一次刚才没有遍历的up或者down的string类型。
先确定这是up还是down类型的，再把空格找到，如果是up类型的，又是在左边找到一个假硬币，那么它一定是重的，我们把对应的位置+100，反之找到轻的硬币我们就把对应位置-100.

这样的结果是，因为我们假设除了真的硬币外其余都是假币，除非题目中有两个even并且如样例一样都已经说明了10个是真的，另外一个没出现，下面解释一下样例，k是假的，也就是只找到一个假的，那么L因为没出现就是0，k会变成-100，其余都是1.我的核心思想就是“输出的一定是假币而不是不知道是真的还是假的硬币”。因为假币只有一个，所以既然不知道L是不是假币，而K是假币了，那么就把K输出就行了。
同样的，思路，因为赋值是按照除了确定的真币外其余都是假币来赋值的，而出现，比如
1
ABCDEF GHIJKL up
ABC DEF even
I J down
的情况的时候，我先尝试的分析一下第一句，首先ABCDEF都是真的我们不管它，然后假设G是假币，置为-100，同理，后头每一个都置为-100，大家也发现了这样是矛盾的是吧？因为假币只有一个啊，怎么可能这么多假币呢？是的，我们要做的就是找出矛盾的根源，就是找出最假的那枚硬币。
接着我们在看最后一句，假设I是假的，再－100，这样就变成了-200，而假设J是假的，+100，反而变成0了，这说明假设J是假的推出了矛盾，所以J是真的。但这不重要，我们又不是找真的，我们是找那唯一的一个假的，现在不难发现I就是最假的那一个，因为假设I是假的话，这个假设并没有推出矛盾，反而I减的更多了，证明假设是成立的，I确实是假的。而其他的呢，那些GHKL之类的，它们的值为-100，这个也没有推出矛盾，我们不知道它们是真的还是假的，但有一点I必须是假的，所以我们输出I就行了。
我的做法也就是最后再遍历一次coin[]，找到里头的正负最大值，看谁的绝对值更大，就输出谁，正的就表示是超重，负的表示太轻了。Description

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.

#include<stdio.h>
#include<string.h>
int main()
{int m,n,i,j,d[13];char a[20],b[20],c[20];scanf("%d",&m);while(m--){memset(d,0,sizeof(d));for(j=0; j<3; j++){scanf("%s %s %s",a,b,c);if(strcmp(c,"even")==0){for(i=0; a[i]!='\0'; i++)d[a[i]-'A']=1;for(i=0; b[i]!='\0'; i++)d[b[i]-'A']=1;}else if(strcmp(c,"up")==0){for(i=0; a[i]!='\0'; i++){if(d[a[i]-'A']==2)d[a[i]-'A']=1;else if(d[a[i]-'A']!=1)d[a[i]-'A']=-1;}for(i=0; b[i]!='\0'; i++){if(d[b[i]-'A']==-1)d[a[i]-'A']=1;else if(d[b[i]-'A']!=1)d[b[i]-'A']=2;}}else if(strcmp(c,"down")==0){for(i=0; a[i]!='\0'; i++){if(d[a[i]-'A']!=1)d[a[i]-'A']=2;else if(d[a[i]-'A']==-1)d[a[i]-'A']=1;}for(i=0; b[i]!='\0'; i++){if(d[b[i]-'A']!=1)d[b[i]-'A']=-1;if(d[b[i]-'A']==2)d[b[i]-'A']=1;}}}for(i=0; i<12; i++){if(d[i]==-1){printf("%c is the counterfeit coin and it is heavy.\n",i+'A');break;}if(d[i]==2){printf("%c is the counterfeit coin and it is light.\n",i+'A');break;}}}
}

下面是正确的，被题目坑了，题目说一定有答案后来就敲了上面的程序结果总是错误，上网看了一下别人的才知道

<pre code_snippet_id="252235" snippet_file_name="blog_20140323_3_9948556" class="html" name="code">#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
int main()
{int m,i,j,n,d[13],Max,e;char a[20],b[20],c[20];scanf("%d",&m);while(m--){memset(d,0,sizeof(d));for(j=0; j<3; j++){scanf("%s %s %s",a,b,c);n=strlen(a);if(strcmp(c,"even")==0){for(i=0; i<n; i++)d[a[i]-'A']=10;for(i=0; i<n; i++)d[b[i]-'A']=10;}else if(strcmp(c,"up")==0){for(i=0; i<n; i++)if( d[a[i]-'A']!=10)d[a[i]-'A']++;for(i=0;i<n; i++)if( d[b[i]-'A']!=10)d[b[i]-'A']--;}else if(strcmp(c,"down")==0){for(i=0; i<n; i++)if( d[a[i]-'A']!=10)d[a[i]-'A']--;for(i=0; i<n; i++)if( d[b[i]-'A']!=10)d[b[i]-'A']++;}}Max = 0;e= 0;for (i = 0; i < 12; i++){if (d[i] != 10 && abs(d[i]) >Max){Max = abs(d[i]);e = i;}}if (d[e] > 0){printf("%c is the counterfeit coin and it is heavy.\n", e+'A');}else{printf("%c is the counterfeit coin and it is light.\n", e+'A');}}return 0;
}

这篇关于poj 1013 Counterfeit Dollar的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！