HDU1029 False coin

Description

Input

Output

Sample Input

5 3
2 1 2 3 4
<
1 1 4
=
1 2 5
=

Sample Output

3

Source

解题思路：本题为模拟逻辑题，只要想通怎么确定硬币真假即可解得。

在称量中，有3种情况，>,< =,其实，总体的情况只有两种，天平平行还是不平行。

（1）若天平是平行的，毫无疑问，所有参与本次称量的硬币都是真硬币。因为题目说了，假硬币只有一个，且真硬币的质量都相等。

（2）若天平不平行，就要分两边讨论了。若硬币在重的一边且尚未确定真假，如果该硬币在以前的称量中曾经出现在轻的一边，则该硬币可以确定为真硬币（状态置为102）。因为同一个硬币的重量是不变的，曾出现在轻的一边，后面又出现在重的一边，只能说，致使天平倾斜的硬币不是它，所以，该硬币是真的。否则记录它曾经出现在重的一边（状态++，置为正值）。对于在本次称量中处于轻的一边的硬币，同理处理即可。

注意：如果出现情况（2），有一个隐秘的信息一定要挖出来，银行说了，假硬币只有1个。若出现情况（2），表示，那个质量和真硬币不同的假硬币，已经出现在称量中了。也就是说，所有没有参与本次称量的硬币，都能确定是真的。

最后，逐个检索硬币的状态值，若值为102，即该硬币已确定为真硬币。否则，表示该硬币尚未确定真假。若未确定真假的硬币只有一个，则说明该硬币就是假硬币，输出该硬币的编号。否则，无法确定假硬币，输出“0”；

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
    int co[1005];    //记录硬币情况，在称量后记录称量结果，
    int n,k,i,j,x,bl[203];
    char a[3];  //用于读入符号
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        int no=0;
        memset(co,sizeof(co));   //状态记录数组置零
        for(j=0;j<k;j++)
        {
            scanf("%d",&x);  //读入天平两遍硬币的个数
            x*=2;
            for(i=0;i<x;i++)
                scanf("%d",&bl[i]);   //读入所有参加称量的硬币号码
            scanf("%s",a);   //读入符号，a[0]处存储的就是所读入夫人符号
            if(a[0]=='=')   //若天平是平的，所有参与称量的硬币都是真的
                for(i=0;i<x;i++)
                    co[bl[i]]=102;    //状态标记置为102，表示该硬币i已经检测过关，为真硬币
            else if(a[0]=='<')  //若天平是右倾的
            {
                no++;
                x/=2;
                for(i=0;i<x;i++)   //天平左边的硬币相对比较轻
                {
                    if(co[bl[i]]!=102)   //如果该硬币为确定为真硬币
                    {
                        if(co[bl[i]]>0)   //若该硬币在前面的称量中曾经重过，则它是真的硬币（同一个硬币质量是不会变的）
                            co[bl[i]]=102;
                        else co[bl[i]]--;   //否则，记录为有有一次称量中，硬币在轻的一方
                    }
                }
                x=2*x;
                for(i=x/2;i<x;i++)        //天平右边的硬币相对比较重
                {
                    if(co[bl[i]]!=102)//如果该硬币为确定为真硬币
                    {
                        if(co[bl[i]]<0) //若该硬币在前面的称量中曾经轻过，则它是真的硬币（同一个硬币质量是不会变的）
                            co[bl[i]]=102;
                        else
                            co[bl[i]]++;//否则，记录为有有一次称量中，硬币在重的一方
                    }
                }
                int u;
                for(i=1;i<=n;i++)//由于假硬币只有一枚，出现了天平不平衡的情况，所有未参与本次称量的硬币都是真硬币
                {
                    for(u=0;u<x;u++)
                    {
                        if(i==bl[u])
                        break;
                    }
                    if(u==x)
                        co[i]=102;
                }
            }
            else if(a[0]=='>')
            {
                no++;
                for(i=x/2;i<x;i++)
                {
                    if(co[bl[i]]!=102)
                    {
                        if(co[bl[i]]>0)
                            co[bl[i]]=102;
                        else co[bl[i]]--;
                    }
                }
                x/=2;
                for(i=0;i<x;i++)
                {
                    if(co[bl[i]]!=102)
                    {
                        if(co[bl[i]]<0)
                            co[bl[i]]=102;
                        else
                            co[bl[i]]++;
                    }
                }
                x*=2;
                int u;
                for(i=1;i<=n;i++)
                {
                    for(u=0;u<x;u++)
                    {
                        if(i==bl[u])
                        break;
                    }
                    if(u==x)
                        co[i]=102;
                }
            }
        }
        int j=0;
        for(i=1;i<=n;i++)
        {
            if(co[i]!=102)    //若硬币i不能确定为真硬币，则它可能是假的
            {
                if(j==0) 
                    j=i;
                else     //若在这个不能确定真假的硬币之前，有硬币是不能确定真假的，则无法确定哪个是假硬币
                {
                    j=0;
                    break;
                }
            }
        }
        printf("%dn",j);
    }
    return 0;
}