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:

- The Lucas theorem of luogu3807 [template]
- The Lucas theorem of luogu3807 [template]
- How to replace this with variables?
- Median Weight Bead (shortest path Floyed transitive closure)
- Median Weight Bead (shortest path Floyed transitive closure)
- Python-event event – imitating the traffic light
- Python-event event – imitating the traffic light
- CF930E Coins Exhibition
- CF930E Coins Exhibition
- [NOI Guide 2009 popularize (6)] the lightest balance (GCD)

Link of this Article: POJ1013 Counterfeit Dollar