c093: 00608 - Counterfeit Dollar

2021-06-06 17:03:05 +0800 CST Tags: puzzle

出處：https://zerojudge.tw/ShowProblem?problemid=c093
提交：https://zerojudge.tw/Submissions?problemid=c093&account=allllllan123456

問題：給定 12 個硬幣以及 3 次秤重，每次秤重的天平左右兩邊硬幣數量均等，而且可以知道結果是左傾、平衡，或者是右傾。已知秤重結果必定符合恰好有一個硬幣為假幣的情況，而且一定判斷得出來，請找出假幣為何？

解法：這題其實就是 c095 的弱化版，可以直接參考那一題的作法。

 1#include <bits/stdc++.h>
 2using namespace std;
 3
 4int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
 5    int n; cin >> n;
 6    while (n--) {
 7        int ineqCnt=0, ineq[12], w[12];
 8        for (int i=0; i<12; i++) { ineq[i] = 0; w[i] = INT_MAX; }
 9        for (int k=0; k<3; k++) { string s1, s2, op;
10            cin >> s1 >> s2 >> op; int Pi = s1.length();
11            if (op != "even") ineqCnt++;
12            for (int i=0; i<Pi*2; i++) {
13                int id = (i < Pi ? s1[i] : s2[i-Pi]) - 'A';
14                if (op == "even") w[id] = 0;
15                else if (op=="down"&&i<Pi || op=="up"&&i>=Pi) {
16                    ineq[id]++;
17                    if (w[id] == INT_MAX) w[id] = -1;
18                    else if (w[id] == 1) w[id] = 0;
19                }
20                else if (op=="up"&&i<Pi || op=="down"&&i>=Pi) {
21                    ineq[id]++;
22                    if (w[id] == INT_MAX) w[id] = 1;
23                    else if (w[id] == -1) w[id] = 0;
24                }
25            }
26        }
27        for (int i=0; i<12; i++)
28            if (w[i] && ineq[i]==ineqCnt) {
29                cout << char{'A' + i} << " is the counterfeit coin and it is " << (w[i] < 0 ? "light" : "heavy") << ".\n";
30                break;
31            }
32    }
33    return 0;
34}

no image