POJ 1017 偽造鈔票：哈希表模擬天平稱重邏輯求解

問題建模

12 枚硬幣 A-L，其中 1 枚偽幣（輕或重）。3 次天平稱重，每次給出左右盤硬幣與結果（up/down/even）。唯一確定偽幣及輕重。

核心邏輯推導

關鍵觀察

1. Even 盤全真：若某次稱重平衡，參與稱重的所有硬幣必為真幣
2. 偽幣必導致傾斜：偽幣參與的稱重，天平必不平衡
3. 方向一致性：假設某幣為偽幣且輕/重，推導 3 次稱重的理論結果，與實際結果完全匹配則為答案

解法一：假設驗證法（最直觀）

建模每枚硬幣在 3 次稱重中的「理論貢獻」

• 第 i 次稱重：左盤硬幣貢獻 -1，右盤 +1，未參與 0
• 若硬幣為輕：天平傾向與其貢獻相反（左盤輕 → 右盤下沉 → down → 理論 -1）
• 若硬幣為重：天平傾向與其貢獻相同

驗證邏輯

// 實際結果編碼：even=0, up=1, down=-1
// 硬幣 c 假設為輕：預期結果 = -contribution[c][i]
// 硬幣 c 假設為重：預期結果 = +contribution[c][i]

for (int c = 0; c < 12; ++c) {
    // 假設輕
    bool ok_light = true;
    for (int i = 0; i < 3; ++i)
        if (actual[i] != -contrib[c][i]) { ok_light = false; break; }
    if (ok_light) { answer = c, "light"; break; }
    
    // 假設重
    bool ok_heavy = true;
    for (int i = 0; i < 3; ++i)
        if (actual[i] != contrib[c][i]) { ok_heavy = false; break; }
    if (ok_heavy) { answer = c, "heavy"; break; }
}

解法二：差值累積法（更巧妙，原文創新）

思路

• 初始化 12 枚硬幣分數 score[12] = {0}
• 每次稱重：
  • Even：參與硬幣 score = 10（標記為真幣，不再修改）
  • Up（左盤重/右盤輕）：左盤硬幣 ++，右盤 --
  • Down：左盤 --，右盤 ++
• 最終 |score| 最大且 ≠10 的硬幣為偽幣
  score > 0 → heavy, score < 0 → light

代碼實現

#include 
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int score[12] = {0};
        for (int w = 0; w < 3; ++w) {
            string left, right, result;
            cin >> left >> right >> result;
            if (result == "even") {
                for (char c : left) score[c-'A'] = 10;
                for (char c : right) score[c-'A'] = 10;
            } else if (result == "up") { // left down / right up
                for (char c : left) if (score[c-'A'] != 10) score[c-'A']++;
                for (char c : right) if (score[c-'A'] != 10) score[c-'A']--;
            } else { // down
                for (char c : left) if (score[c-'A'] != 10) score[c-'A']--;
                for (char c : right) if (score[c-'A'] != 10) score[c-'A']++;
            }
        }
        int idx = 0, max_diff = 0;
        for (int i = 0; i < 12; ++i) {
            if (score[i] != 10 && abs(score[i]) > max_diff) {
                max_diff = abs(score[i]);
                idx = i;
            }
        }
        cout << char('A'+idx) << " is the counterfeit coin and it is "
             << (score[idx] > 0 ? "heavy" : "light") << ".\n";
    }
    return 0;
}

兩種解法對比

關鍵細節總結

1. Even 處理優先級最高：標記真幣後，後續稱重不再修改其分數/貢獻
2. 輕/重判斷邏輯：Up = 左盤下沉 = 左重/右輕，Down 相反
3. 唯一解保證：題目保證輸入合法且唯一解，無需處理多解/無解
4. 字符處理：'A'-'L' 對應 0-11，用 c-'A' 索引

總結

POJ 1017 是邏輯推理與編程實現結合的經典題。假設驗證法邏輯嚴密、擴展性強，適合面試講解；差值累積法代碼極簡、工程效率高，適合競賽現場。掌握「Even 全真、偽幣必傾斜、方向一致性」三大核心規則，即可靈活構造解法。本題體現了「用數據結構（哈希/數組）模擬邏輯規則」的競賽編程核心思想。