alan23273850 的刷題筆記
c095: 00665 - False coin
Tags: puzzle
出處：https://zerojudge.tw/ShowProblem?problemid=c095
提交：https://zerojudge.tw/Submissions?problemid=c095&account=allllllan123456
問題：給定 $N\in[1,100]$ 個硬幣以及 $K\in[1,100]$ 次秤重，每次秤重的天平左右兩邊硬幣數量均等，而且可以知道結果是左傾、平衡，或者是右傾。已知秤重的結果必定符合恰好有一個硬幣為假幣的情況，請找出假幣為何？如果有多種可能的答案皆滿足這組秤重結果，請輸出 0。
解法：先掌握排除答案的條件。出現在平衡結果左右兩邊的硬幣都必須是真幣。如果有一個硬幣在某次秤重是出現在較輕的那一邊，但是在另一次秤重是出現在較重的那一邊，那它也必須是真幣。那剩下來的硬幣要嘛從來沒被拿來比過，要嘛都是出現在輕或重的其中一邊，前者必須在所有的秤重都是平衡狀態的前提之下才可以是假幣，後者則必須出現在所有不平衡狀態的秤重結果才可以是假幣。此篩選程序已經實作在程式碼之中。
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
5 int M; cin >> M;
6 while (M--) {
7 int N, K; cin >> N >> K;
8 int ineqCnt=0, ineq[101], c[101], w[101];
9 for (int i=1; i<=N; i++) ineq[i] = 0, w[i] = INT_MAX;
10 while (K--) {
11 int Pi; cin >> Pi;
12 for (int i=0; i<Pi*2; i++) cin >> c[i];
13 char ch; cin >> ch; if (ch != '=') ineqCnt++;
14 for (int i=0; i<Pi*2; i++)
15 if (ch == '=') w[c[i]] = 0;
16 else if (ch=='<'&&i<Pi || ch=='>'&&i>=Pi) {
17 ineq[c[i]]++;
18 if (w[c[i]] == INT_MAX) w[c[i]] = -1;
19 else if (w[c[i]] == 1) w[c[i]] = 0;
20 }
21 else if (ch=='>'&&i<Pi || ch=='<'&&i>=Pi) {
22 ineq[c[i]]++;
23 if (w[c[i]] == INT_MAX) w[c[i]] = 1;
24 else if (w[c[i]] == -1) w[c[i]] = 0;
25 }
26 }
27 int ans = 0;
28 for (int i=1; i<=N; i++)
29 if (!ineq && w[i] == INT_MAX || w[i] && ineq[i]==ineqCnt)
30 if (!ans) ans = i;
31 else { ans = 0; break; }
32 cout << ans << "\n\n";
33 }
34 return 0;
35}