【ACM】杭电 hdu 1482 Counterfeit Dollar

 

/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
    Copyright (c) 2011 panyanyany All rights reserved.

    URL   : http://acm.hdu.edu.cn/showproblem.php?pid=1482
    Name  : 1482 Counterfeit Dollar

    Date  : Sunday, January 22, 2012
    Time Stage : 2 hours

    Result: 
5285719	2012-01-22 11:47:15	Accepted	1482
0MS	236K	2462 B
C++	pyy


Test Data :

Review :
不是什么难题，慢慢推敲一下就出来了。
首先，基本原理是，把全部倾斜的天平摆成一个方向，设为左低右高，
那么假币肯定在任意一边。设它在左边，则左边3组中必然都存在假币，
所以只要枚举左边所有倾斜组，得到共有的那个硬币，便是假币。如果左边
找不到所有组共有的硬币，则在右边找。

如果遇到平衡的天平，那么此天平两边的硬币都是真币，就可以在枚举的时候过滤
掉这些真币了，同时也要减少枚举的组数。比如示例中，有两组真币，那么只枚举
一组就行了。
//----------------------------------------------------------------------------*/

#include <cstdio>
#include <cstring>
#include <cstdlib>

#include <iostream>
#include <string>

using namespace std ;

#define INF        (-1)
#define MAXN       ('L'-'A'+2)

int evenCnt ;

int getsum (bool side[MAXN][3], bool even[MAXN])
{
	int i, j, sum ;
	for (i = 0 ; i < 12 ; ++i)
	{
		sum = 0 ;
		if (even[i])	// 不枚举真币
			continue ;
		for (j = 0 ; j < 3 ; ++j)
			sum += side[i][j] ;
		if (sum == 3 - evenCnt)	// 只枚举倾斜的天平
			break ;
	}
	return i ;
}

int main ()
{
	int i, j ;
	int tcase, k, id ;

	string a, b, c, lf, rh ;
	char *pWei ;

	bool even[MAXN], left[MAXN][3], right[MAXN][3] ;
	while (scanf ("%d", &tcase) != EOF)
	{
		k = 0 ;
		while (k++ < tcase)
		{
			MEM (even, 0) ;
			MEM (left, 0) ;
			MEM (right, 0) ;
			evenCnt = 0 ;

			for (i = 0 ; i < 3 ; ++i)
			{
				cin >> a >> b >> c ;
				if (c[0] == 'e')	// 记录真币
				{
					++evenCnt ;
					for (j = 0 ; j < a.size() ; ++j)
					{
						even[a[j]-'A'] = true ;
					}
					for (j = 0 ; j < b.size() ; ++j)
					{
						even[b[j]-'A'] = true ;
					}
					continue ;
				}
				else if (c[0] == 'u')
					lf = a, rh = b ;
				else
					lf = b, rh = a ;

				for (j = 0 ; j < lf.size() ; ++j)
					left[lf[j]-'A'][i] = true ;
				for (j = 0 ; j < rh.size() ; ++j)
					right[rh[j]-'A'][i] = true ;
			}
			id = getsum (left, even) ;
			pWei = "heavy" ;
			if (id == 12)
			{
				id = getsum (right, even) ;
				pWei = "light" ;
			}
			printf ("%c is the counterfeit coin and it is %s.\n", id+'A', pWei) ;
		}
	}
	return 0 ;
}