取石子游戲

Time Limit:?1000MS	?	Memory Limit:?10000K
Total Submissions:?29959	?	Accepted:?9818

Description

有兩堆石子，數量任意，可以不同。游戲開始由兩個人輪流取石子。游戲規定，每次有兩種不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在兩堆中同時取走相同數量的石子。最后把石子全部取完者為勝者。現在給出初始的兩堆石子的數目，如果輪到你先取，假設雙方都采取最好的策略，問最后你是勝者還是敗者。

Input

輸入包含若干行，表示若干種石子的初始情況，其中每一行包含兩個非負整數a和b，表示兩堆石子的數目，a和b都不大于1,000,000,000。

Output

輸出對應也有若干行，每行包含一個數字1或0，如果最后你是勝者，則為1，反之，則為0。

Sample Input

2 1 8 4 4 7

Sample Output

0 1 0

Source

NOI

思路：

定理 0：一個狀態是必敗態，當且僅當它的所有后繼狀態都是必勝態；而一個狀態是必勝態，只要它的后繼狀態有一個以上的必敗態即可。

證明略去。

容易發現下面的定理：

定理 1：(a，b) 和 (b, a)?的勝負性是相同的（a <> b）。

證明：如果 (a, b) 是必勝態，那么將必勝策略中所有的操作，對第一堆的變為第二堆，對第二堆的變為第一堆，就構成 (b, a) 的必勝策略

定理 2：若 (a, b) 是必敗態，則對于所有的 x?<> a 和 y?<> b，(x, b) 和 (a, y)?是必勝態。

證明：

對于 x > a 和 y > b，不管是哪一種情況，總可以從 x 堆或 y 堆中取出一定量的石子使當前狀態變為必敗態 (a, b)，由定理 1，(x, b) 和 (a, y) 為必勝態。

對于 x < a 和 y < b，不管是哪一種情況，如果 (x, b) 或 (a, y) 是必敗態的話，由上述可得 (a, b) 是必勝態，矛盾。故 (x, b)?和 (a, y) 均為為必勝態。

定理 3: 若 (a, b) 是必敗態，則對于所有的 d > 0，(a + d, b + d) 是必勝態。

證明：

與定理 2 類似。

定理 4：在所有的必敗態中，每個數字恰巧出現一次。

證明：

?

有了定理 1，對于對稱的狀態我們只需要處理其中一個，而兩個數不會相同（相同的狀態必然是必勝態），于是我們把每個狀態中較小的數字放在前面，每行寫一個狀態，去掉括號并按照升序排列每行的第一個數，就構成了如下的矩陣：

1??2

3??5

4??7

6??10

……

觀察這個矩陣，我們又可以得到新的定理：

定理 5：矩陣中每行第一個數恰巧是前面每一行中沒有出現過的最小正整數。

定理 6：矩陣第 i 行的第二個數正好為第一個數加上 i

定理 7（Betty 定理）：如果存在正無理數 A, B 滿足 1/A + 1/B = 1，那么集合 P = { [At], t?∈?Z⁺}、Q = { [Bt],?t?∈?Z⁺} 恰為集合 Z⁺?的一個劃分，即：P?∪?Q = Z⁺，P?∩?Q = 空。

證明：暫時略去，將來補充。

考慮到 Betty 定理中“恰為?Z⁺?的劃分”這一說，這意味著，Z⁺?中的每個數都恰好出現一次，這與上述矩陣的性質十分吻合。于是我們猜想每一行第一列的數滿足 [Φi] 的形式。

于是我們得到每一行第二列的數為 [Φi] + i = [Φi + i] = [(Φ?+ 1)i]

我們的目的是要讓?Z⁺?中每個數都在這個矩陣中出現，于是考慮到 Betty 定理的條件，Φ?和 (Φ?+ 1) 應滿足 1/Φ?+ 1/(Φ?+?1) = 1。解這個方程，我們得到?Φ?= (sqrt(5) + 1) / 2，于是?Φ?+ 1 = (sqrt(5) + 3) / 2。

Φ?恰為黃金分割比，這是多么令人驚奇的結論！

于是應用 Betty 定理，我們得到最終我們需要的定理：

定理 8：上述矩陣中每一行第一列的數為 [Φi]，第二列的數為 [(Φ?+ 1)i]，其中?Φ?= (sqrt(5) + 1) / 2 為黃金分割比。

證明：由 Betty 定理顯然得證。

#include<iostream> #include<cmath> using namespace std; int a,b; int main() {while(cin>>a>>b){if(a>b)a^=b,b^=a,a^=b;b-=a;b=(int)b*((sqrt(5.0)+1.0)/2.0);if(b==a)cout<<0<<"\n";else cout<<1<<"\n";} }

轉載于:https://www.cnblogs.com/nealgavin/archive/2013/02/26/3205966.html

總結

以上是生活随笔為你收集整理的poj 1067 取石子游戏(博弈+威佐夫博奕(Wythoff Game))的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。