Article From:https://www.cnblogs.com/headboy2002/p/9127641.html

Subject matter

12One silver coin, one heavier or lighter, the other weight is the same. Now put two equal amounts of silver on the balance, and say what silver and weighing results are known. Which is heavier or lighter, which is heavier or lighter?

thinking

How does the investigator systematically analyze the problem? The way of thinking is to reduce the scope and use the exclusion method.

The integer compression state indicates which silver may be lighter and which may be heavier. When the balance is balanced, all the silver on both sides can not be false silver; when the balance is unbalance, the light silver may only be in the silver on the lower side of the silver.

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cassert>
using namespace std;

int main()
{
#ifdef _DEBUG
	freopen("c:\\noi\\source\\input.txt", "r", stdin);
#endif
	int caseCnt;
	cin >> caseCnt;
	while (caseCnt--)
	{
		int light = (1 << 12) - 1, heavy = (1 << 12) - 1;
		string a, b, condition;
		for (int i = 0; i < 3; i++)
		{
			cin >> a >> b >> condition;
			int left = 0, right = 0;
			for (int i = 0; i < a.size(); i++)
				left |= (1 << a[i] - 'A');
			for (int i = 0; i < b.size(); i++)
				right |= (1 << b[i] - 'A');
			if (condition == "even")
			{
				light = light & (~left) & (~right);
				heavy = heavy & (~left) & (~right);
			}
			else
			{
				if (condition == "up")
					swap(left, right);
				light &= left;
				heavy &= right;
			}
		}
		int lightAns = -1;
		for(int i = 0; i < 12; i++)
			if ((1 << i) & light)
			{
				if (light - (1 << i) == 0)
					lightAns = i;
				break;
			}
		int heavyAns = -1;
		for(int i=0; i<12; i++)
			if ((1 << i) & heavy)
			{
				if (heavy - (1 << i) == 0)
					heavyAns = i;
				break;
			}
		assert(lightAns == -1 && heavyAns >= 0 || heavyAns == -1 && lightAns >= 0);
		if (lightAns >= 0)
			printf("%c is the counterfeit coin and it is light.\n", lightAns + 'A');
		else
			printf("%c is the counterfeit coin and it is heavy.\n", heavyAns + 'A');
	}

	return 0;
}

  

Similar Posts:

Link of this Article: POJ1013 Counterfeit Dollar

Leave a Reply

Your email address will not be published. Required fields are marked *