POJ 1013 — Counterfeit Dollar – 关浩博的博客

浏览量： 14

题目大意

12枚硬币中只有1枚假币，假币比真币轻或者比真币重。用天平称了硬币三次，每次天平左边的硬币数都和右边的硬币数相等。问哪一枚硬币是假币并且确定假币是轻是重。

题目链接

http://poj.org/problem?id=1013

输入

第一行是测试数据组数n。每组数据有三行，分别表示三次称量的结果。硬币分别用A-L表示。每次称量的结果用三个字符串表示：天平左边的硬币天平右边的硬币天平状态。天平状态用”up”, “down”, “even”分别表示右端高、右端低和平衡。

输出

对于每组数据，输出一行，假币的英文编号以及假币的轻重。heavy表示假币比真币重，light表示假币比真币轻。具体参见样例输出。

样例输入

1
ABCD EFGH even
ABCI EFJK up
ABIJ EFGH even

样例输出

K is the counterfeit coin and it is light.

问题分析

这个问题的思路很简单，但实现起来并不是很容易。硬币的编号是A-L，所以我们只要枚举硬币A-L，判断编号为ans的硬币是不是假币即可。实际上，对于任意一个硬币，在三次称量中，有可能出现0、1、2、3次。因此，我们需要根据天平状态怀疑硬币ans是不是假币以及它的轻重，最后判断所有ans出现的时候得出的结论是否一致。

例如，在样例中，枚举到ans=’K’时，K只出现一次，根据第二次称量会得到K是假币的结论。但要注意，这时不能直接断定K是假币，还需要保证所有K不出现的时候天平状态为”even”，即剩余两次称量天平均为”even”，这一点很重要。只出现两次的也要进行类似判断。

AC代码

#include <iostream>
#include <string>
using namespace std;
string s1[3], s2[3], s3[3];

int f(char ans, int i) //返回值为1代表重，0代表不是假币，-1代表轻,-2表示没找到
{
    int result = 0, t1 = 0, t2 = 0;
    if (s1[i].rfind(ans) != -1)
    {
        if (s3[i] == "up")
            result = 1;
        else if (s3[i] == "down")
            result = -1;
        else
            result = 0;
        t1 = 1;
    }
    if (s2[i].rfind(ans) != -1)
    {
        if (s3[i] == "up")
            result = -1;
        else if (s3[i] == "down")
            result = 1;
        else
            result = 0;
        t2 = 1;
    }
    if (t1 == t2)
    {
        if (t1 == 1)
            return 0;
        return -2;
    }
    return result;
}

int main()
{
    int n, i, j, k, temp, sum;
    char ans;
    cin >> n;
    while (n--)
    {
        for (i = 0; i < 3; i++)
            cin >> s1[i] >> s2[i] >> s3[i];
        for (ans = 'A'; ans <= 'L'; ans++)
        {
            temp = 0, sum = 0;
            if ((f(ans, 0) == f(ans, 1) || f(ans, 0) == -2 || f(ans, 1) == -2) && (f(ans, 1) == f(ans, 2) || f(ans, 1) == -2 || f(ans, 2) == -2) && (f(ans, 0) == f(ans, 2) || f(ans, 0) == -2 || f(ans, 2) == -2))
            {
                for (j = 0; j <= 2; j++)
                    if (f(ans, j) != -2)
                    {
                        sum++;
                        temp = f(ans, j);
                    }
                if (sum == 1) //这两个判断sum的非常重要
                {
                    int a1 = 0;
                    for (j = 0; j <= 2; j++)
                        if (s3[j] == "even")
                            a1++;
                    if (a1 != 2)
                        continue;
                }
                else if (sum == 2)
                {
                    int a1 = 0;
                    for (j = 0; j <= 2; j++)
                        if (s3[j] == "even")
                            a1++;
                    if (a1 != 1)
                        continue;
                }
                if (temp == -1)
                {
                    cout << ans << " is the counterfeit coin and it is light." << endl;
                    break;
                }
                if (temp == 1)
                {
                    cout << ans << " is the counterfeit coin and it is heavy." << endl;
                    break;
                }
            }
        }
    }
    return 0;
}

注意事项

若用枚举做此题，情况要考虑全面，先在本地多测试几种数据（自己编数据），不要局限于题目所给的一个样例。