ACM 1005 Jugs - 水壺倒水問題解題報告

ZOJ 1005 Jugs 題解：雙水壺倒水操作序列構造

經典「死神來了 3」同款倒水謎題推廣。給定兩壺容量 Ca, Cb 及目標量 N (目標態為 B 壺含 N 加侖)，輸出任一合法操作序列。允許操作：fill A/B, empty A/B, pour A B / B A, success。

核心觀察：輾轉相減 / 擴展歐幾里得

本質上求解 Ca * x + Cb * y = N 的整數解。但題目不要求最優步數，只需任一可行序列。採用固定策略：始終對 A 壺灌滿，倒入 B 壺；B 滿則倒空；循環直到 B 達到 N。

算法流程

1. 初始 sA = 0, sB = 0
2. 循環：
   1. 若 sA == 0：fill A, sA = Ca
   2. 否則：pour A B
      • sB += sA
      • 若 sB >= Cb：
        • 若 Cb != N：empty B, sA = sB - Cb, sB = 0
        • 否則 (B 已達目標) sB = Cb (保持滿狀態)
      • 否則 (B 未滿)：sA = 0
   3. 檢查 sB == N：是 → success，結束

完整 C 代碼

#include 

int main() {
    int Ca, Cb, N, sA, sB;
    while (scanf("%d %d %d", &Ca, &Cb, &N) == 3) {
        sA = sB = 0;
        while (1) {
            if (sA == 0) {
                printf("fill A\n");
                sA = Ca;
            } else {
                printf("pour A B\n");
                sB += sA;
                if (sB >= Cb) {
                    if (Cb != N) {
                        printf("empty B\n");
                        sA = sB - Cb;
                        sB = 0;
                    } else {
                        sB = Cb;
                    }
                } else {
                    sA = 0;
                }
            }
            if (sB == N) {
                printf("success\n");
                break;
            }
        }
    }
    return 0;
}

正確性論證

• 不變量：sA + sB (模 Cb) 遍歷 Ca 的倍數模 Cb 的剩餘類
• 因題目保證有解，即 gcd(Ca, Cb) | N，上述過程必能達到 sB = N
• 操作序列合法：每步均符合六種允許操作定義

複雜度

• 時間：O(Cb / gcd(Ca, Cb)) 步，極小
• 空間：O(1)

常見變體與擴展

1. 求最少步數：BFS 狀態空間搜索，狀態 (sA, sB) 共 (Ca+1)*(Cb+1) 個
2. 三壺/多壺：狀態維度升高，同樣 BFS 或 A*
3. 輸出到 A 壺：對稱策略，或交換 A/B 角色

測試樣例

輸入: 3 5 4
輸出:
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
success

對應經典 3/5 加侖得 4 加侖解法。