假币问题(OpenJ_Bailian - 269)题解

àì夳堔傛蜴生んèń 2022-12-28 07:28 139阅读 0赞

### 文章目录 ###

*  题目描述
 *   *  输入要求
     *  输出要求
     *  样例输入
     *  样例输出
 *  算法分析
 *  算法标程

--------------------

# 题目描述 #

赛利有12枚银币。其中有11枚真币和1枚假币。假币看起来和真币没有区别，但是重量不同。但赛利不知道假币比真币轻还是重。于是他向朋友借了一架天平。朋友希望赛利称三次就能找出假币并且确定假币是轻是重。例如:如果赛利用天平称两枚硬币，发现天平平衡，说明两枚都是真的。如果赛利用一枚真币与另一枚银币比较，发现它比真币轻或重，说明它是假币。经过精心安排每次的称量，赛利保证在称三次后确定假币。

## 输入要求 ##

> 第一行有一个数字n，表示有n组测试用例。

> 对于每组测试用例：  
> 输入有三行，每行表示一次称量的结果。赛利事先将银币标号为A-L。每次称量的结果用三个以空格隔开的字符串表示：天平左边放置的硬币 天平右边放置的硬币 平衡状态。其中平衡状态用`up`, `down`, 或 `even`表示, 分别为右端高、右端低和平衡。天平左右的硬币数总是相等的。

## 输出要求 ##

> 输出哪一个标号的银币是假币，并说明它比真币轻还是重(`heavy`or `light`)。

## 样例输入 ##

1
    ABCD EFGH even 
    ABCI EFJK up 
    ABIJ EFGH even

## 样例输出 ##

K is the counterfeit coin and it is light.

# 算法分析 #

*  题目所述：12颗硬币中只有1颗为假币，并且假币是轻是重不确定
 *  那么每颗硬币都有可能是假币（一共12种情况），每颗假币可能轻可能重（一共12\*2=24种情况）
 *  因此用对于这24情况去模拟天平，**将每一种情况下天平的平衡结果与样例输入的结果进行对比，如果符合输入的预先结果，那么该硬币就一定是轻或重的假币**
 *  注意：用-1代表轻假币，1代表重假币，0代表真币

# 算法标程 #

#include <iostream>
    #include <map>
    #include <string>
    #include <cstdio>
    using namespace std;
    
    int t;
    map<char, int> m;
    string l[3],r[3],ret[3];
    
    void init()
    {
        
        for(int i=0;i<12;i++)
            m['A'+i]=0;
    }
    
    //平衡
    bool balance()
    {
        
        int ans=0;
        for(int i=0;i<3;i++){
        
            int lw=0,rw=0;
            for(int j=0;j<l[i].size();j++)
                lw+=m[l[i][j]];
            for(int j=0;j<r[i].size();j++)
                rw+=m[r[i][j]];
            
            if(lw==rw&&ret[i][0]=='e')
                ans++;
            if(lw<rw&&ret[i][0]=='d')
                ans++;
            if(lw>rw&&ret[i][0]=='u')
                ans++;
        }
        
        //三次重量比较和天平结果全都一致ans=3，那么这个情况下该币为假币
        if(ans==3)
            return true;
        else  //否则该情况就不成立
            return false;
    }
    
    int main()
    {
        
        cin >> t;
        
        int i;
        while(t--){
        
            for(i=0;i<3;i++)
                cin >> l[i] >> r[i] >> ret[i];
            
            init();
            for(i=0;i<12;i++){
        
                m['A'+i]=-1;  //假币较轻
                if(balance())
                    break;
                m['A'+i]=1;   //假币较重
                if(balance())
                    break;
                m['A'+i]=0;   //两种都不是那么就是真币
            }
            
            if(m['A'+i]==-1)
                printf("%c is the counterfeit coin and it is light.\n",'A'+i);
            else
                printf("%c is the counterfeit coin and it is heavy.\n",'A'+i);
        }
        
        return 0;
    }