菜鸟题解 POJ-1013 Counterfeit Dollar

原题直达

https://vjudge.net/contest/582185#problem/C

题干

原题面
参考翻译

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.

莎莉·琼斯有一打航海银元。然而，只有11枚硬币是真正的银元;一枚硬币是伪造的，尽管它的颜色和大小使它与真正的银元无法区分。这枚假币的重量与其他硬币不同，但莎莉不知道它是比真硬币重还是轻。幸运的是，Sally有一个朋友借给她一个非常精确的天平。这位朋友将允许莎莉称三次以找到那枚假币。例如，如果Sally将两枚硬币放在一起称重，天平平衡，那么她就知道这两枚硬币是真的。如果莎莉的体重是一枚真硬币和第三枚硬币的天平不平衡，那么莎莉就知道第三枚硬币是假的，她可以根据放置硬币的天平是上升还是下降来判断它是轻还是重。通过仔细选择重量，莎莉能够确保她找到的假币正好有三个重量。

Input

输入的第一行是一个整数n (n >0)指定要遵循的案例数。每个案例由三行输入组成，每一行用于称重。莎莉把每一枚硬币都标上了字母A- L。称重信息将由两串字母和一个单词“上”、“下”或“平”组成。第一串字母代表左边天平上的硬币;第二串，硬币在正确的平衡上。(Sally总是会把相同数量的硬币放在右边的天平和左边的天平上。)第三个位置的单词将告诉我们天平的右侧是上升、下降还是保持平衡。

Output

对于每种情况，输出将根据字母识别假币，并告诉它是重还是轻。解决方案总是唯一确定的。

测试案例

Input

1 
ABCD EFGH even 
ABCI EFJK up 
ABIJ EFGH even

Output

1	K is the counterfeit coin and it is light.

题意与思路

题目给出的条件为：

共有12枚硬币，分别用 ABCDEFGHIJKL 表示
12枚硬币中，有11枚完全一样的真币和1枚假币
假币的重量与真币不同，但暂时不知道它是更轻还是更重

在此基础上，使用一个天平称量三次：

每次称量时，天平两端的硬币数量相等，但不一定为4
题目确保一定可以通过三次称量找到这枚假币

由于有且仅有一枚假币的重量与其他硬币不同，因此：

只要天平出现倾斜，就表明假币一定出现在了天平的某一侧，且假币出现的那一侧总是较轻/较重
如果天平平衡，说明假币一定没有出现在天平上，也就是说当前天平上的所有硬币都是真币

据此，我们制定策略——给每个硬币假定一个初始重量 0：

当某一硬币出现在较轻一侧时，令其重量 -1
当某一硬币出现在较重一侧时，令其重量 +1
当某一硬币出现在平衡的比较轮次中，将其排除

void calculate(string sl, string sr, string e){
    // sl - 天平左侧字符串
    // sr - 天平右侧字符串
    // e  - 天平比较结果
    
    if(e == "even"){  // 天平平衡->左右两侧硬币为真，排除
        for(int i = 0;i < sl.size();i++){
            isTrue[sl[i]] = true;
            isTrue[sr[i]] = true;
        }
    }
    else if(e == "up"){  // 天平右侧较轻->右侧重量--，左侧重量++
        for(int i = 0;i < sl.size();i++){
            score[sl[i]] ++;
            score[sr[i]] --;
        }
    }
    else {  // 天平右侧较重->右侧重量++，左侧重量--
        for(int i = 0;i < sl.size();i++){
            score[sl[i]] --;
            score[sr[i]] ++;
        }
    }
}

分析三次称量可能出现的情况，我们可以将结果分为三类：

三次倾斜

此时，假币必然出现在每一次称量结果中的同一侧，那么它的重量将经过三次 +1 或 -1，由于题目确保一定能找到假币，说明重量绝对值为 3 的硬币必然有且仅有 1 枚，成功找到假币；
三次平衡

此时，三次平衡可以排除若干真币，由于题目确保一定能找到假币，说明必然仅剩一枚假币，成功找到假币；
若干次平衡、若干次倾斜

此时，假币必然出现在倾斜的那几组中，经过重量的判别调整，可能会有若干个重量绝对值相等且最大的硬币，由于题目确保一定能找到假币，必然可以通过平衡的结果，对这些硬币进行排除，最后仅留下一枚硬币，成功找到假币；

最后，只要考察重量绝对值最大的硬币的重量是负数还是正数，即可得出该硬币是较重还是较轻。

题解

#include <iostream>
#include <string>
#include <cstring>
#include <cmath>

using namespace std;

int score[200];
bool isTrue[200];

void calculate(string sl, string sr, string e){
    // sl - 天平左侧字符串
    // sr - 天平右侧字符串
    // e  - 天平比较结果
    
    if(e == "even"){  // 天平平衡->左右两侧硬币为真，排除
        for(int i = 0;i < sl.size();i++){
            isTrue[sl[i]] = true;
            isTrue[sr[i]] = true;
        }
    }
    else if(e == "up"){  // 天平右侧较轻->右侧重量--，左侧重量++
        for(int i = 0;i < sl.size();i++){
            score[sl[i]] ++;
            score[sr[i]] --;
        }
    }
    else {  // 天平右侧较重->右侧重量++，左侧重量--
        for(int i = 0;i < sl.size();i++){
            score[sl[i]] --;
            score[sr[i]] ++;
        }
    }
}

int main(){
    string s1l, s1r, e1;
    string s2l, s2r, e2;
    string s3l, s3r, e3;

    int n;
    cin>>n;
    while(n--){
        memset(score, 0, sizeof(score));
        memset(isTrue, 0, sizeof(isTrue));

        cin>>s1l>>s1r>>e1;
        cin>>s2l>>s2r>>e2;
        cin>>s3l>>s3r>>e3;
        
        calculate(s1l, s1r, e1);
        calculate(s2l, s2r, e2);
        calculate(s3l, s3r, e3);

        int maxAbsScore = 0;
        int maxScore = 0;

        char counterfeit;

        for(int i = 'A';i <= 'L';i++){
            if(isTrue[i]) continue;
            if(abs(score[i]) > maxAbsScore){
                maxAbsScore = abs(score[i]);
                maxScore = score[i];
                counterfeit = i;
            }
        }

        cout<<counterfeit<<" is the counterfeit coin and it is ";
        if(maxScore < 0)
            cout<<"light."<<endl;
        else
            cout<<"heavy."<<endl;

    }

    return 0;
}