coreBugZJ

此 blog 已棄。

POJ 1067 取石子游戲

/*
2

POJ 1067 取石子游戲
3

----問題描述：
6

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

----輸入：
11

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

----輸出：
16

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

----樣例輸入：
21

2 1
23

8 4
24

4 7
25

----樣例輸出：
28

0
30

1
31

0
32

----分析：
35

（轉自網上，略有修正）
37

大致看完題目，想當然就知道這是一道博弈論的問題，最容易想的就是直接用博弈論的必敗、必勝態進行動態規劃求解。但是樸素的動態規劃是 O(N * M) 的，如果做一些優化可能可以過掉 RQNOJ 的題目，但是對于 POJ 1067 來說就完全無能為力。所以我們嘗試分析數據，看看有沒有什么規律（以下用 (a, b) 表示兩堆石子的個數，即游戲中的一個狀態）。
39

列舉了幾個狀態之后容易發現，必勝態的數目比必敗態要多很多，所以我們先手工求出前幾個必敗態：
41

(1, 2)、(2, 1)、(3, 5)、(5, 3)、(4, 7)、(7, 4)、（6, 10）、（10, 6）……
43

首先回顧必勝態和必敗態的樸素求法：
45

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

證明略去。
49

容易發現下面的定理：
51

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

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

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

證明：
59

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

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

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

證明：
67

與定理 2 類似。
69

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

證明：
73

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

1 2
77

3 5
79

4 7
81

6 10
83

……
85

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

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

證明：
91

由定理 4，矩陣中每個數字恰巧出現一次，而按照這個矩陣的定義，第二列的數總比同行第一列大，第一列又按照升序排列，所以每一行的第一個數正好為前面每一行中沒有出現過的最小正整數。
93

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

證明：
97

用數學歸納法。
99

100

1) 對于第一行顯然成立
101

102

2) 若對于前 i - 1 行均成立，則所有的 (a[p], a[p] + p) (a[p] 為第 p 行第一個數，p < i) 均為必敗態，那么考察第 i 行的狀態 (a[i], a[i] + delta)。容易看出 delta >= i，因為如果 delta < i，一定可以通過一次操作變為前面出現過的必敗態，那么這個狀態就是必勝態。下面由 delta >= i，我們來說明 delta = i。
103

104

首先，我們考慮從第一堆中取出 p 個石子，得到狀態 (a[i] - p, a[i] + delta)，由定理 5，比 a[i] 小的數都在之前出現過，若 a[i] - p 出現在某一行的第一列，由于存在必敗態 (a[i] - p, a[i] - p + d) (d < delta)，故 (a[i] - p, a[i] + delta) 一定為必勝態（定理 2）；若 a[i] - p 出現在某一行的第二列，由于第一列是單增的，因而其對應的第一列數必小于 a[i] + delta，故而也可推出其狀態為必勝態。
105

106

對于從兩堆石子中取出相同數目的情況與之類似，容易看出一定為必勝態。
107

108

于是，(a[i], a[i] + delta) 狀態的勝負性只與狀態 (a[i], a[i] + d) (d < delta) 有關。不難看出，delta = i 時恰為必敗態，因為不論從第二堆中取出多少個石子，作為另一堆的第一堆石子并沒有在之前出現過，所以得到的一定是一個必勝態，因而 (a[i], a[i] + delta) 為必敗態，由定理 2 及定理 4 可得，原命題成立。即矩陣中第 i 行第二列的數等于同行第一列的數加上 i。
109

110

111

這時，我們所有的問題都轉化到了矩陣上，只要能通過合適的方法表示出這個矩陣，我們就可以很好地解決原問題。
112

113

下面的過程可能需要比較高的數學技巧，首先給出我們需要的一個重要定理（[x] 表示 x 的整數部分，{x} 表示 x 的小數部分，即 {x} = x - [x]）：
114

115

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

117

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

119

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

121

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

123

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

125

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

127

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

129

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

131

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

133

134

135

有了定理 8，代碼的實現就十分簡單了，由于是數學算法，總復雜度為 O(1)。至此，本題完美解決。
136

137

138

總結：遇到這樣困難的題目時，我們不應該輕言放棄。而應該仔細分析題目隱含的信息，學會分析和轉化問題，從而找到問題的突破口，一舉殲滅問題。
139

140

141

*/
142

143

144

#include <iostream>
145

#include <cstdio>
146

#include <cmath>
147

148

using namespace std;
149

150

int main() {
151

int a, b, d, t;
152

while ( 2 == scanf( "%d%d", &a, &b ) ) {
153

if ( a > b ) {
154

t = a;
155

a = b;
156

b = t;
157

}
158

d = b - a;
159

t = floor( d * ( sqrt(5.0) + 1 ) / 2 );
160

puts( (t == a) ? "0" : "1" );
161

}
162

return 0;
163

}
164

posted on 2012-06-04 16:05 coreBugZJ 閱讀(5488) 評論(0) 編輯收藏引用所屬分類: ACM 、Algorithm 、Mathematics 、課內作業

只有注冊用戶登錄后才能發表評論。


相關文章: 微軟2014實習生及秋令營技術類職位在線測試 TopCoder SRM 593 DIV2 第三題生成全排列的非回溯方法（TopCoder SRM 591 DIV 2） A* 算法求解八數碼問題，POJ 1077 Eight POJ 1067 取石子游戲 POJ 2068 Nim POJ 2975 Nim POJ 3696 The Luckiest number POJ 3604 Professor Ben EOJ 1117 剩余定理

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

coreBugZJ

My Links

Blog Stats

常用鏈接

留言簿(10)

隨筆分類(458)

隨筆檔案(268)

相冊

ACM

AI

LaTeX

安全

編程語言

好有道理

技術

開源

科學

數學

圖形圖像

文化

問題（練習＆有趣）

資源

最新隨筆

搜索

最新評論

閱讀排行榜

評論排行榜

POJ 1067 取石子游戲