HDU 2177 取石子遊戲：威佐夫博弈與最優策略

HDU 2177 - 兩堆石子遊戲（威佐夫博弈）

經典的威佐夫博弈：有兩堆石子，數量分別為 a、b（a ≤ b）。雙方輪流操作，每次可選擇：

1. 從任意一堆取走任意數量石子；
2. 從兩堆中同時取走相同數量石子。

取走最後石子者獲勝。給定初始 (a, b)，先手是否必勝？若必勝，輸出第一步最優操作後的剩餘石子數 (x, y)（x ≤ y）；若同時有「取同量」與「取單堆」兩種獲勝策略，優先輸出取同量的方案。

數學解法：黃金分割點

威佐夫博弈的必敗態（P-position）為：

(⌊k·φ⌋, ⌊k·φ²⌋) 或對稱位置，其中 φ = (1+√5)/2 ≈ 1.618，k = 0,1,2…

等價判斷：令 a ≤ b，k = b - a。若 a = ⌊k·φ⌋，則為必敗態，先手輸（輸出 0）；否則先手贏（輸出 1）。

構造最優第一步

贏的情況下，需找到一步操作使對手進入必敗態。兩種操作類型：

• 同時取同量：嘗試減少兩堆相同數量 i (1 ≤ i ≤ a)，使 (a-i, b-i) 成為必敗態。即檢查 ⌊(b-a)·φ⌋ == a-i？優先輸出此類方案。
• 單堆取石：若無同量取法，嘗試從較大堆取石子，使 (a, b-i) 或 (a-i, b) 成為必敗態。遍歷可能的 i 並檢查條件。

參考代碼（C++）

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

int main() {
    long long a, b;
    const double phi = (sqrt(5.0) + 1) / 2.0;
    while (cin >> a >> b && (a || b)) {
        if (a > b) swap(a, b);
        long long k = b - a;
        if ((long long)(k * phi) == a) {
            cout << "0\n";
            continue;
        }
        cout << "1\n";
        // 優先嘗試同時取同量
        for (long long i = 1; i <= a; ++i) {
            if ((long long)(k * phi) == a - i) {
                cout << a - i << ' ' << b - i << '\n';
                break;
            }
        }
        // 再嘗試單堆取石
        for (long long i = b - 1; i >= 0; --i) {
            long long na = min(a, i), nb = max(a, i);
            long long nk = nb - na;
            if ((long long)(nk * phi) == na) {
                cout << na << ' ' << nb << '\n';
                break;
            }
        }
    }
    return 0;
}

複雜度分析

• 判斷勝負：O(1)
• 構造最優步：最壞 O(a) ≈ O(10⁶)，實際極快，因為必敗態稀疏，通常幾次循環即找到。

關鍵點

1. 威佐夫博弈的必敗態由黃金分割比決定，無需 DP 或遞歸。
2. 輸出要求：先輸出 0/1，贏時再輸出剩餘石子數；同量取法優先。
3. 注意 long long 防溢出，a,b ≤ 1,000,000。