Counterfeit Dollar (UVa 1012)：天平推理找假幣

題目大意

12 枚硬幣 A~L，一枚假幣（輕或重）。3 次天平稱量，每次給出左右盤硬幣集合及結果：`up`（右輕）、`down`（右重）、`even`（平衡）。保證有唯一解。輸出假幣字母及輕/重。

解法：枚舉驗證

• 假設每枚硬幣分別為假幣且為輕/重，共 24 種假設。
• 對每種假設，模擬 3 次稱量，檢查結果是否與輸入一致。
• 唯一通過的假設即為答案。

模擬邏輯

對一次稱量 `(left, right, result)`：
- 計算左盤權重和、右盤權重和（真幣重 1，假幣重 0 或 2）。
- `even`：左和 == 右和。
- `up`：右輕 → 左和 > 右和。
- `down`：右重 → 左和 < 右和。
（或直接用差值符號判斷）

代碼

#include 
#include 
using namespace std;

int main() {
    int T; cin >> T;
    while (T--) {
        string L[3], R[3], res[3];
        for (int i = 0; i < 3; ++i) cin >> L[i] >> R[i] >> res[i];
        for (char c = 'A'; c <= 'L'; ++c) {
            for (int type = 0; type < 2; ++type) { // 0=light, 1=heavy
                bool ok = true;
                for (int i = 0; i < 3; ++i) {
                    int sumL = 0, sumR = 0;
                    for (char ch : L[i]) {
                        if (ch == c) sumL += (type ? 2 : 0);
                        else sumL += 1;
                    }
                    for (char ch : R[i]) {
                        if (ch == c) sumR += (type ? 2 : 0);
                        else sumR += 1;
                    }
                    if (res[i] == "even" && sumL != sumR) { ok = false; break; }
                    if (res[i] == "up" && sumL <= sumR) { ok = false; break; } // 右輕 => 左重
                    if (res[i] == "down" && sumL >= sumR) { ok = false; break; } // 右重 => 左輕
                }
                if (ok) {
                    cout << c << " is the counterfeit coin and it is " << (type ? "heavy" : "light") << ".\n";
                    goto NEXT_CASE;
                }
            }
        }
        NEXT_CASE: ;
    }
    return 0;
}

複雜度

• 24 假設 × 3 稱量 × 12 字符 = O(1)，極快。

總結

Counterfeit Dollar 是經典的「枚舉驗證」邏輯推理題。數據規模極小（12 枚硬幣，3 次稱量），暴力枚舉所有可能並模擬驗證是最直觀、最不易出錯的方法。代碼簡潔清晰，無需複雜推導。