首页 > 其他 > 详细

POJ 1013：Counterfeit Dollar

时间：2015-07-30 11:30:12      阅读：253      评论：0      收藏：0      [点我收藏+]

Counterfeit Dollar
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 42028   Accepted: 13369

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.

题意是从A到L的dollar，其中有一个跟他们其它的不同，可能是轻了也可能是重了。给了三个在秤上的关系，要你判断出哪一个是伪造的dollar，是轻是重。

做的时候还WA了几次，但AC之后觉得这个题真是水啊。。。不知道为什么只要自己好不容易A完之后就觉得这个题真的很水，为什么当时没有想到呢？就是这种感觉。

咳咳，因为这个题就A到L之中有问题嘛，数据量太小，导致枚举就OK了。所以从A开始就一个一个试吧，如果在even中的语句里出现了，那就排除它的嫌疑。在up语句中出现了，它的flag加3，代表可能是轻的标记。在down语句中出现了，它自己的flag加4，代表可能是重的标记。

然后对12个砝码标记完之后，有标记为1的排除，标记为7 10 11这样的排除，因为不可能出现一个砝码既轻又重的情况，然后找最独特的那一个就是伪造的砝码了。输出即可。

代码：

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
using namespace std;

int num[15];
int Test,i,j,flag[15],sum=0;
string left_s[5],right_s[5],bala[5];
char temp_c;


void solve()
{
	if(bala[1]=="up")
	{
		for(j=0;j<left_s[1].length();j++)
		{
			if(left_s[1][j]==temp_c)
			{
				sum=1;
				cout<<temp_c<<" is the counterfeit coin and it is ";
				cout<<"heavy."<<endl;
				return ;
			}
		}
		for(j=0;j<right_s[1].length();j++)
		{
			if(right_s[1][j]==temp_c)
			{
				sum=1;
				cout<<temp_c<<" is the counterfeit coin and it is ";
				cout<<"light."<<endl;
				return;
			}
		}
	}
	if(bala[2]=="up")
	{
		for(j=0;j<left_s[2].length();j++)
		{
			if(left_s[2][j]==temp_c)
			{
				sum=1;
				cout<<temp_c<<" is the counterfeit coin and it is ";
				cout<<"heavy."<<endl;
				return;
			}
		}
		for(j=0;j<right_s[2].length();j++)
		{
			if(right_s[2][j]==temp_c)
			{
				sum=1;
				cout<<temp_c<<" is the counterfeit coin and it is ";
				cout<<"light."<<endl;
				return;
			}
		}
	}
	if(bala[3]=="up")
	{
		for(j=0;j<left_s[3].length();j++)
		{
			if(left_s[3][j]==temp_c)
			{
				sum=1;
				cout<<temp_c<<" is the counterfeit coin and it is ";
				cout<<"heavy."<<endl;
				return ;
			}
		}
		for(j=0;j<right_s[3].length();j++)
		{
			if(right_s[3][j]==temp_c)
			{
				sum=1;
				cout<<temp_c<<" is the counterfeit coin and it is ";
				cout<<"light."<<endl;
				return ;
			}
		}
	}

	if(bala[1]=="down")
	{
		for(j=0;j<left_s[1].length();j++)
		{
			if(left_s[1][j]==temp_c)
			{
				sum=1;
				cout<<temp_c<<" is the counterfeit coin and it is ";
				cout<<"light."<<endl;
				return;
			}
		}
		for(j=0;j<right_s[1].length();j++)
		{
			if(right_s[1][j]==temp_c)
			{
				sum=1;
				cout<<temp_c<<" is the counterfeit coin and it is ";
				cout<<"heavy."<<endl;
				return ;
			}
		}
	}
	if(bala[2]=="down")
	{
		for(j=0;j<left_s[2].length();j++)
		{
			if(left_s[2][j]==temp_c)
			{
				sum=1;
				cout<<temp_c<<" is the counterfeit coin and it is ";
				cout<<"light."<<endl;
				return;
			}
		}
		for(j=0;j<right_s[2].length();j++)
		{
			if(right_s[2][j]==temp_c)
			{
				sum=1;
				cout<<temp_c<<" is the counterfeit coin and it is ";
				cout<<"heavy."<<endl;
				return ;
			}
		}
	}
	if(bala[3]=="down")
	{
		for(j=0;j<left_s[3].length();j++)
		{
			if(left_s[3][j]==temp_c)
			{
				sum=1;
				cout<<temp_c<<" is the counterfeit coin and it is ";
				cout<<"light."<<endl;
				return;
			}
		}
		for(j=0;j<right_s[3].length();j++)
		{
			if(right_s[3][j]==temp_c)
			{
				sum=1;
				cout<<temp_c<<" is the counterfeit coin and it is ";
				cout<<"heavy."<<endl;
				return ;
			}
		}
	}
}

bool pend()
{
	int pend_flag=0;
	if(bala[1]=="up")
	{
		for(j=0;j<left_s[1].length();j++)
		{
			if(left_s[1][j]==temp_c)
			{
				pend_flag=1;
			}
		}
		for(j=0;j<right_s[1].length();j++)
		{
			if(right_s[1][j]==temp_c)
			{
				pend_flag=1;
			}
		}
		if(pend_flag==0)
			return false;
	}
	if(bala[2]=="up")
	{
		for(j=0;j<left_s[2].length();j++)
		{
			if(left_s[2][j]==temp_c)
			{
				pend_flag=1;
			}
		}
		for(j=0;j<right_s[2].length();j++)
		{
			if(right_s[2][j]==temp_c)
			{
				pend_flag=1;
			}
		}
		if(pend_flag==0)
			return false;
	}
	if(bala[3]=="up")
	{
		for(j=0;j<left_s[3].length();j++)
		{
			if(left_s[3][j]==temp_c)
			{
				pend_flag=1;
			}
		}
		for(j=0;j<right_s[3].length();j++)
		{
			if(right_s[3][j]==temp_c)
			{
				pend_flag=1;
			}
		}
		if(pend_flag==0)
			return false;
	}

	if(bala[1]=="down")
	{
		for(j=0;j<left_s[1].length();j++)
		{
			if(left_s[1][j]==temp_c)
			{
				pend_flag=1;
			}
		}
		for(j=0;j<right_s[1].length();j++)
		{
			if(right_s[1][j]==temp_c)
			{
				pend_flag=1;
			}
		}
		if(pend_flag==0)
			return false;
	}
	if(bala[2]=="down")
	{
		for(j=0;j<left_s[2].length();j++)
		{
			if(left_s[2][j]==temp_c)
			{
				pend_flag=1;
			}
		}
		for(j=0;j<right_s[2].length();j++)
		{
			if(right_s[2][j]==temp_c)
			{
				pend_flag=1;
			}
		}
		if(pend_flag==0)
			return false;
	}
	if(bala[3]=="down")
	{
		for(j=0;j<left_s[3].length();j++)
		{
			if(left_s[3][j]==temp_c)
			{
				pend_flag=1;
			}
		}
		for(j=0;j<right_s[3].length();j++)
		{
			if(right_s[3][j]==temp_c)
			{
				pend_flag=1;
			}
		}
		if(pend_flag==0)
			return false;
	}
	return true;
}
int main()
{
	cin>>Test;

	while(Test--)
	{
		memset(flag,0,sizeof(flag));
		memset(num,0,sizeof(num));
		sum=0;

		for(i=1;i<=3;i++)
		{
			cin>>left_s[i]>>right_s[i]>>bala[i];
		}
		for(temp_c='A';temp_c<='L';temp_c++)
		{
			if(bala[1]=="even")
			{
				for(j=0;j<left_s[1].length();j++)
				{
					if(left_s[1][j]==temp_c)
					{
						flag[temp_c-'A']=1;
						break;
					}
				}
				for(j=0;j<right_s[1].length();j++)
				{
					if(right_s[1][j]==temp_c)
					{
						flag[temp_c-'A']=1;
						break;
					}
				}
			}
			if(bala[2]=="even")
			{
				for(j=0;j<left_s[2].length();j++)
				{
					if(left_s[2][j]==temp_c)
					{
						flag[temp_c-'A']=1;
						break;
					}
				}
				for(j=0;j<right_s[2].length();j++)
				{
					if(right_s[2][j]==temp_c)
					{
						flag[temp_c-'A']=1;
						break;
					}
				}
			}
			if(bala[3]=="even")
			{
				for(j=0;j<left_s[3].length();j++)
				{
					if(left_s[3][j]==temp_c)
					{
						flag[temp_c-'A']=1;
						break;
					}
				}
				for(j=0;j<right_s[3].length();j++)
				{
					if(right_s[3][j]==temp_c)
					{
						flag[temp_c-'A']=1;
						break;
					}
				}
			}

			if(bala[1]=="up")
			{
				for(j=0;j<left_s[1].length();j++)
				{
					if(left_s[1][j]==temp_c)
					{
						if(flag[temp_c-'A']==1)
							continue;
						else
							flag[temp_c-'A'] += 4;
					}
				}
				for(j=0;j<right_s[1].length();j++)
				{
					if(right_s[1][j]==temp_c)
					{
						if(flag[temp_c-'A']==1)
							continue;
						else
							flag[temp_c-'A'] += 3;
					}
				}
			}
			if(bala[2]=="up")
			{
				for(j=0;j<left_s[2].length();j++)
				{
					if(left_s[2][j]==temp_c)
					{
						if(flag[temp_c-'A']==1)
							continue;
						else
							flag[temp_c-'A'] += 4;
					}
				}
				for(j=0;j<right_s[2].length();j++)
				{
					if(right_s[2][j]==temp_c)
					{
						if(flag[temp_c-'A']==1)
							continue;
						else
							flag[temp_c-'A'] += 3;
					}
				}
			}
			if(bala[3]=="up")
			{
				for(j=0;j<left_s[3].length();j++)
				{
					if(left_s[3][j]==temp_c)
					{
						if(flag[temp_c-'A']==1)
							continue;
						else
							flag[temp_c-'A'] +=4;
					}
				}
				for(j=0;j<right_s[3].length();j++)
				{
					if(right_s[3][j]==temp_c)
					{
						if(flag[temp_c-'A']==1)
							continue;
						else
							flag[temp_c-'A'] +=3;
					}
				}
			}

			if(bala[1]=="down")
			{
				for(j=0;j<left_s[1].length();j++)
				{
					if(left_s[1][j]==temp_c)
					{
						if(flag[temp_c-'A']==1)
							continue;
						else
							flag[temp_c-'A'] +=3;
					}
				}
				for(j=0;j<right_s[1].length();j++)
				{
					if(right_s[1][j]==temp_c)
					{
						if(flag[temp_c-'A']==1)
							continue;
						else
							flag[temp_c-'A'] +=4;
					}
				}
			}
			if(bala[2]=="down")
			{
				for(j=0;j<left_s[2].length();j++)
				{
					if(left_s[2][j]==temp_c)
					{
						if(flag[temp_c-'A']==1)
							continue;
						else
							flag[temp_c-'A'] +=3;
					}
				}
				for(j=0;j<right_s[2].length();j++)
				{
					if(right_s[2][j]==temp_c)
					{
						if(flag[temp_c-'A']==1)
							continue;
						else
							flag[temp_c-'A'] +=4;
					}
				}
			}
			if(bala[3]=="down")
			{
				for(j=0;j<left_s[3].length();j++)
				{
					if(left_s[3][j]==temp_c)
					{
						if(flag[temp_c-'A']==1)
							continue;
						else
							flag[temp_c-'A'] +=3;
					}
				}
				for(j=0;j<right_s[3].length();j++)
				{
					if(right_s[3][j]==temp_c)
					{
						if(flag[temp_c-'A']==1)
							continue;
						else
							flag[temp_c-'A'] +=4;
					}
				}
			}
		}
		for(temp_c='A';temp_c<='L';temp_c++)
		{
			num[flag[temp_c-'A']]++;
		}
        for(i=0;i<=12;i++)
		{
			if(num[i]==1 && i!=7 && i!=10 && i!=11)
			{
				for(temp_c='A';temp_c<='L';temp_c++)
				{
					if(flag[temp_c-'A']==i)
					{
						if(pend())
						{
							solve();
						}
					}
				}
			}
		}
	}
	
	return 0;
}


版权声明：本文为博主原创文章，未经博主允许不得转载。

POJ 1013：Counterfeit Dollar

原文：http://blog.csdn.net/u010885899/article/details/47144115
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！