1057: 有假幣 - 邏輯推理與分支限界求解

問題描述

有 12 枚硬幣，其中 1 枚是假幣 (輕或重未知)。給定 3 次天平稱重結果，每次給出左盤、右盤硬幣編碼及結果 (Up/Down/Even)。找出假幣編號及輕重。

核心邏輯

• 每次稱重產生約束：假幣在左/右/未參與
• 結果 Even：左右兩盤所有幣均為真幣
• 結果 Up：左盤輕 / 右盤重 → 假幣在左(輕)或右(重)
• 結果 Down：左盤重 / 右盤輕 → 假幣在左(重)或右(輕)
• 枚舉 12 枚幣 × 2 種可能 (輕/重) = 24 種假設，驗證是否滿足所有 3 次稱重

完整 C 代碼

#include <stdio.h>
#include <string.h>

int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        char left[3][7], right[3][7], result[3][7];
        for(int i = 0; i < 3; i++)
            scanf("%s %s %s", left[i], right[i], result[i]);
        
        // 枚舉假幣: A-L (0-11), 假設輕/重
        for(int coin = 0; coin < 12; coin++) {
            for(int type = 0; type < 2; type++) {  // 0=輕, 1=重
                char c = 'A' + coin;
                int ok = 1;
                
                for(int w = 0; w < 3; w++) {
                    int in_left = strchr(left[w], c) != NULL;
                    int in_right = strchr(right[w], c) != NULL;
                    
                    if(result[w][0] == 'E') {  // Even
                        if(in_left || in_right) { ok = 0; break; }
                    } else if(result[w][0] == 'U') {  // Up: 左輕/右重
                        if(in_left && type == 1) { ok = 0; break; }  // 假幣在左且重 → 左重 (Down)
                        if(in_right && type == 0) { ok = 0; break; } // 假幣在右且輕 → 右輕 (Down)
                        if(!in_left && !in_right) { ok = 0; break; } // 假幣未參與 → 應 Even
                    } else {  // Down: 左重/右輕
                        if(in_left && type == 0) { ok = 0; break; }  // 假幣在左且輕 → 左輕 (Up)
                        if(in_right && type == 1) { ok = 0; break; } // 假幣在右且重 → 右重 (Up)
                        if(!in_left && !in_right) { ok = 0; break; }
                    }
                }
                
                if(ok) {
                    printf("%c is the counterfeit coin and it is %s.\n", 
                           c, type == 0 ? "light" : "heavy");
                    goto next_case;
                }
            }
        }
        next_case: ;
    }
    return 0;
}

關鍵邏輯表

複雜度分析

• 時間：O(T × 12 × 2 × 3) = O(T)，常數極小
• 空間：O(1)

測試案例

輸入:
1
ABCD EFGH Even
ABCI EFJK Up
ABIJ EFGH Even

分析:
1. Even → A,B,C,D,E,F,G,H 全真
2. Up → I 在左輕 或 J/K 在右重
3. Even → A,B,I,J,E,F,G,H 全真 → I,J 真
綜合: K 重
輸出: K is the counterfeit coin and it is heavy.

擴展：N 枚硬幣、M 次稱重

通用解法：建立約束滿足問題 (CSP)，用回溯 + 剪枝或 SAT 求解器。3 次稱重最多區分 3³ = 27 種情況，理論上可處理 13 枚硬幣 (13×2=26<27)，12 枚是經典上限。

總結

「有假幣」是邏輯推理與枚舉驗證的經典題目。核心在於將稱重結果轉化為對假幣位置與輕重的**布林約束**，然後窮舉驗證。代碼簡潔、邏輯清晰、擴展性強，是競技程式設計中「暴力枚舉 + 約束檢查」模式的典型應用。