OpenJudge NOI 2.1 15:Counterfeit Dollar

【 Topic link 】

OpenJudge NOI 2.1 15:Counterfeit Dollar

【 Topic test site 】

1. enumeration

【 Topic translation 】

subject

Counterfeit money

describe

Sally Jones has 12 Pieces of Hangji silver , however , Only one of them 11 One is a real silver dollar , Yes 1 Pieces of counterfeit money , Although its color, shape and size make it indistinguishable from the real silver dollar . This counterfeit coin is different in weight from other coins , But Sally did not know whether it was heavier or lighter than other coins .

Fortunately, , One of Sally's friends lent her a very accurate balance , The friend gave Sally three weighing opportunities to find out the counterfeit money . for example , If Sally weighs two coins and the balance is balanced , Then she knew that the two coins were real . Now? , If Sally weighs one of the real coins with the third , The balance is unbalanced , Then she knew that the third coin was counterfeit , And she can go up through the balance 、 Move down to judge whether the counterfeit coin is light or heavy .
By carefully choosing how to weigh , Sally can guarantee , She just needs 3 You can find the counterfeit coin by weighing it once .

Input

The first line of input is an integer n (n>0) Indicate how many sets of test data there are , Each set of data consists of three lines of input , One line represents one weighing . Sally uses letters A To L All coins are marked . Each weighing message consists of a two letter string , And “up”、“down”、“even” One of the three words . The first letter string represents the coin on the left side of the balance , The second letter string is the coin on the right plate of the balance （ Sally always puts the same amount of silver dollars into the left and right plates of the balance ）. The word in the third position indicates that the right side of the scale will move upward 、 Move down the , Keep your balance .

Output

For each set of data , Output letters to indicate which is counterfeit , And decide whether it is heavier or lighter . The solution is always uniquely identified .
The first letter of this sentence is the letter corresponding to the counterfeit currency , The last word is ：light（ Lighter ） or heavy（ Heavier ）.

source

East Central North America 1998

【 Their thinking 】

Altogether A–L There are twelve coins , One of the counterfeit coins , Counterfeit money may be lighter or heavier .
So the possible cases are ：
0 Lighter ,0 Heavier ,1 Lighter ,1 Heavier ,…,11 Lighter ,11 Heavier . altogether 24 In this case .
Enumerate this 24 In this case , In which case , Enter the specified three times of balance comparison, and the result is the same as the actual result .

Suppose the input is ：ABCI EFJK up
If I assume A It's lighter counterfeit money , Then the right end should sink , The actual result is that the right end is cocked up , Different from the actual results .
If I assume A It's a heavier counterfeit currency , Then the right end should be upturned , Same as the actual result .

If in the current case of counterfeit money , Input the results of the specified three balance comparisons are the same as the actual results , Then the situation of counterfeit money is real , feasible . Otherwise, the counterfeit money situation is not feasible .

【 Solution code 】

solution 1：

• C style

#include<bits/stdc++.h>
using namespace std;
#define N 15
bool hasCh(char s[], char c)// character string s Whether there are characters in c 
{
    
    int len = strlen(s);
    for(int i = 0; i < len; ++i)
        if(s[i] == c)
            return true;
    return false;
}
void check(bool ishev, bool hl, bool hr, char res[])//ishev Indicates whether the counterfeit currency is heavier ,hl Indicates whether there is counterfeit money on the left  ,hr Indicates whether there is counterfeit money on the right ,res Save the result string 
{
    
    if(!hl && !hr)
        strcpy(res, "even");
    else if(!ishev && !hl && hr || ishev && hl && !hr)// The lighter one is on the right , Or heavier on the left  
        strcpy(res, "up");
    else if(!ishev && hl && !hr || ishev && !hl && hr)// The lighter one is on the left , Or heavier on the right  
        strcpy(res, "down");
}
int main()
{
    
    char s[4][4][N], lh[2][N] = {
    "light", "heavy"}, res[N];// String entered  
    int n;
    scanf("%d", &n);
    bool isMatch, isHeavy;
    while(n--)
    {
    
        for(int i = 1; i <= 3; ++i)
            scanf("%s %s %s", s[i][1], s[i][2], s[i][3]);
        for(char c = 'A'; c <= 'L'; ++c)// Suppose the counterfeit currency is c 
        {
    
            for(int k = 0; k < 2; ++k)// Suppose the counterfeit currency is lh[k], The possible value is light Lighter , or heavy Heavier  
            {
    
                isMatch = true, isHeavy = strcmp(lh[k], "heavy") == 0; 
                for(int j = 1; j <= 3; ++j)// Look at the comparison rules j 
                {
    
                    bool hl = hasCh(s[j][1], c), hr = hasCh(s[j][2], c);
                    check(isHeavy, hl, hr, res);
                    if(strcmp(res, s[j][3]) != 0)// If the result of the current counterfeit money situation is different from the preset result  
                    {
    
                        isMatch = false;
                        break;
                    }
                }
                if(isMatch)
                {
    
                    printf("%c is the counterfeit coin and it is %s.\n", c, lh[k]);
                    break;
                }
            }
            if(isMatch)
                break;
        }
    }
    return 0;
}

• C++ style

#include<bits/stdc++.h>
using namespace std;
bool hasCh(string s, char c)// Judge s If there c 
{
    
    for(int i = 0; i < s.length(); ++i)
        if(s[i] == c)
            return true;
    return false;
}
string getRes(char f, string lh, string s1, string s2)//f It's counterfeit money ,lh: character string   Indicates heavier or lighter , On both sides of the scale are s1,s2, See what you can get  
{
    
    bool h1 = hasCh(s1, f), h2 = hasCh(s2, f);//h1：s1 If there f,h2：s2 If there f
    if(h1 == false && h2 == false)
        return "even";
    else if(h1 == true && h2 == false)
    {
    
        if(lh == "heavy")
            return "up";
        else
            return "down";
    }
    else if(h1 == false && h2 == true)
    {
    
        if(lh == "heavy")
            return "down";
        else
            return "up";
    }
}
int main()
{
    
    bool isMatch;
    int n;
    cin >> n;
    string s[4][4];
    string lh[2] = {
    "light", "heavy"};
    while(n--)
    {
    
        for(int i = 1; i <= 3; ++i)
            for(int j = 1; j <= 3; ++j) 
                cin >> s[i][j];
        for(char c = 'A'; c <= 'L'; ++c)// Suppose the counterfeit currency is c 
        {
    
            for(int k = 0; k < 2; ++k)// Suppose the counterfeit currency is lh[k], The possible value is light Lighter , or heavy Heavier  
            {
    
                isMatch = true;// Whether the current counterfeit money situation can make 3 The results of the secondary balance are the preset results . 
                for(int i = 1; i <= 3; ++i)
                {
    
                    if(getRes(c, lh[k], s[i][1], s[i][2]) != s[i][3])// If the result of the current counterfeit money situation is different from the preset result  
                    {
     
                        isMatch = false;            
                        break;
                    }
                }
                if(isMatch)
                {
    
                    cout << c << " is the counterfeit coin and it is " << lh[k] << '.' << endl;
                    break;
                }
            }
            if(isMatch)// If you find the right counterfeit money , Is out of  
                break;
        }
    }
    return 0;
}