Counterfeit Dollar
Time Limit:1000MS |
|
Memory Limit:10000K |
Total Submissions:36491 |
|
Accepted:11667 |
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<iostream>
using namespace std;
#define COINSNUM 12
int main(){
char str[COINSNUM+1]="ABCDEFGHIJKL";
int value[COINSNUM],n,i=0,j=0,k=0;
char letters[3][COINSNUM];
bool flags[COINSNUM];
cin>>n;
for(i=0;i<n;i++){
for(j=0;j<COINSNUM;j++){
flags[j]=true;
value[j]=0;
}
for(j=0;j<3;j++){
for(k=0;k<3;k++)
cin>>letters[k];
int len1=strlen(letters[0]);
int len2=strlen(letters[1]);
if(strcmp(letters[2],"even")==0){
for(k=0;k<len1;k++){
flags[letters[0][k]-'A']=false;
value[letters[0][k]-'A']=0;
}
for(k=0;k<len2;k++){
flags[letters[1][k]-'A']=false;
value[letters[1][k]-'A']=0;
}
}else if(strcmp(letters[2],"up")==0){
for(k=0;k<len1;k++){
if(flags[letters[0][k]-'A']==true){
value[letters[0][k]-'A']++;
}
}
for(k=0;k<len2;k++){
if(flags[letters[1][k]-'A']==true){
value[letters[1][k]-'A']--;
}
}
}else if(strcmp(letters[2],"down")==0){
for(k=0;k<len1;k++){
if(flags[letters[0][k]-'A']==true){
value[letters[0][k]-'A']--;
}
}
for(k=0;k<len2;k++){
if(flags[letters[1][k]-'A']==true){
value[letters[1][k]-'A']++;
}
}
}
}
int max=0,maxIndex=0;
for(j=0;j<COINSNUM;j++){
if(abs(value[j])>max){
max=abs(value[j]);
maxIndex=j;
}
}
cout<<str[maxIndex]<<" is the counterfeit coin and it is ";
if(value[maxIndex]>0)
cout<<"heavy."<<endl;
else if(value[maxIndex]<0)
cout<<"light."<<endl;
}
}
分享到:
相关推荐
北大POJ1013-Counterfeit Dollar 解题报告+AC代码
北大POJ2002-Squares 解题报告+AC代码
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码
poj 1000 - 2000 部分题目 官方分类 poj 1000 - 2000 部分题目 官方分类
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ3020-Antenna Placement 解题报告+AC代码
这是魔兽世界终极版POJ的-测试数据,找了好久才找到的。 本来想设置为0积分,但是它居然自动收费(o_ _)ノ。 看传送门:https://pan.baidu.com/s/1cCIwW8psGDASu2JdZawG3Q
北大poj1012-Joseph【经典约瑟夫问题】 poj1012-Joseph【经典约瑟夫问题】
北大POJ3414-Pots 解题报告+AC代码
POJ3211--Washing Clothes
北大POJ2305-Basic remains POJ2305-Basic remains
北大POJ1321-Chess Problem POJ1321-Chess Problem
北大POJ1080-Human Gene Functions POJ1080-Human Gene Functions
北大POJ1159-Palindrome 解题报告+AC代码
poj 1000-3000部分代码 网上收集
POJ---1456.Supermarket测试数据及答案,题目描述:A supermarket has a set Prod of products on sale. It earns a profit px for each product x∈Prod sold by a deadline dx that is measured as an integral ...
北大POJ1004-Financial Management 解题报告+AC代码
POJ 1038--Bugs Integrated
POJ3036--Honeycomb Walk
北大POJ1258-Agri-Net【Prim】 解题报告+AC代码