2012-12-01 12:13:40Morris
[ZJ][博奕] a186. Three-Heap Wythoff's Game
內容 ：
Alice和Bob兩個人又在玩遊戲了。
他們決定玩一種遊戲，準備三堆石頭，數量分別是A, B, C。其中0≤A≤B≤C且皆為整數。
兩人輪流取，每個人每次可以從一些堆中同時拿走一樣數量的石頭，
例如A=2, B=4, C=4時，可能可以從A和B同時拿走2顆，會剩下(0,2,4)，
但不能同時拿走三顆，因為A堆會不夠拿。也不能從A堆拿1顆C堆拿2顆之類。
當然更不能不拿。
當有一方把最後的石頭拿走，造成A=B=C=0時，他就贏了
Alice先手、Bob後手。他們都是頂尖的玩家，絕對不會做出錯誤的抉擇。
玩過許多不同的起始數量後，他們發現能造成Bob獲勝的起始盤面其實不多。
請你寫一個程式，輸出所有0≤A≤B≤C≤200且Bob必勝的盤面。
按照字典順序由小到大輸出。
輸入說明
：
本題無須輸入。
輸出說明
：
輸出包含許多行，每行包含三個以空白間隔的數字，表示一個Bob必勝的盤面。
輸出請依照字典序由小到大，亦即先輸出A較小的盤面，A一樣就比較B的大小，B一樣就比較C。
輸出請依照字典序由小到大，亦即先輸出A較小的盤面，A一樣就比較B的大小，B一樣就比較C。
範例輸入 ：
(本題無須輸入)
範例輸出 ：
0 0 0 0 1 2 0 3 5 ... (約五千行)
提示
：
兩堆的Wythoff's Game可以數學解，三堆呢？
O(N^4)當然過不了。
出處
：
(管理：poao899)
/**********************************************************************************/
/* Problem: a186 "Three-Heap Wythoff's Game" from */
/* Language: CPP (1606 Bytes) */
/* Result: TLE(2s) judge by this@ZeroJudge */
/* Author: morris1028 at 2012-12-01 11:16:51 */
/**********************************************************************************/
#include <stdio.h>
#include <algorithm>
using namespace std;
char dp[201][201][201] = {};
char done[201][201][201] = {};
int dfs(int a, int b, int c) {
if(a == 0 && b == 0 && c == 0)
return 0;
int i, j;
if(a > b) i = a, a = b, b = i;
if(b > c) i = b, b = c, c = i;
if(a > c) i = a, a = c, c = i;
if(done[a][b][c])
return dp[a][b][c];
done[a][b][c] = 1;
for(i = 1; i <= a; i++)
dp[a][b][c] |= !dfs(a-i, b, c);
if(dp[a][b][c]) return 1;
for(i = 1; i <= b; i++)
dp[a][b][c] |= !dfs(a, b-i, c);
if(dp[a][b][c]) return 1;
for(i = 1; i <= c; i++)
dp[a][b][c] |= !dfs(a, b, c-i);
if(dp[a][b][c]) return 1;
j = min(a, b);
for(i = 1; i <= j; i++)
dp[a][b][c] |= !dfs(a-i, b-i, c);
if(dp[a][b][c]) return 1;
j = min(a, c);
for(i = 1; i <= j; i++)
dp[a][b][c] |= !dfs(a-i, b, c-i);
if(dp[a][b][c]) return 1;
j = min(b, c);
for(i = 1; i <= j; i++)
dp[a][b][c] |= !dfs(a, b-i, c-i);
if(dp[a][b][c]) return 1;
j = min(min(a, b), c);
for(i = 1; i <= j; i++)
dp[a][b][c] |= !dfs(a-i, b-i, c-i);
if(dp[a][b][c]) return 1;
return dp[a][b][c];
}
int main() {
int i, j, k;
int cnt = 0;
for(i = 0; i <= 200; i++)
for(j = i; j <= 200; j++)
for(k = j; k <= 200; k++)
if(!dfs(i, j, k)) {
printf("%d %d %d\n", i, j, k);
cnt++;
if(cnt > 3000) return 0;
}
return 0;
}
以上是 TLE 的版本，同時這題也是 2012 高雄站的測機題
以下才是真正通過的，他都已經告訴我答案個數約為 5000，反向更新就好，
O(5000*200 + 200*200*200)
/**********************************************************************************/
/* Problem: a186 "Three-Heap Wythoff's Game" from */
/* Language: C (940 Bytes) */
/* Result: AC(36ms, 5MB) judge by this@ZeroJudge */
/* Author: morris1028 at 2012-12-01 12:09:18 */
/**********************************************************************************/
#include <stdio.h>
char dp[201][201][201] = {};
void update(int a, int b, int c) {
int i, j;
if(a > c) i = a, a = c, c = i;
if(b > c) i = b, b = c, c = i;
if(a > b) i = a, a = b, b = i;
if(c > 200) return;
dp[a][b][c] = 1;
}
int main() {
int i, j, k, a;
int cnt = 0;
for(i = 0; i <= 200; i++)
for(j = i; j <= 200; j++)
for(k = j; k <= 200; k++)
if(!dp[i][j][k]) {
printf("%d %d %d\n", i, j, k);
for(a = 1; a <= 200; a++) {
update(i+a, j, k);
update(i, j+a, k);
update(i, j, k+a);
update(i+a, j+a, k);
update(i+a, j, k+a);
update(i, j+a, k+a);
update(i+a, j+a, k+a);
}
}
return 0;
}
/**********************************************************************************/
/* Problem: a186 "Three-Heap Wythoff's Game" from */
/* Language: CPP (1606 Bytes) */
/* Result: TLE(2s) judge by this@ZeroJudge */
/* Author: morris1028 at 2012-12-01 11:16:51 */
/**********************************************************************************/
#include <stdio.h>
#include <algorithm>
using namespace std;
char dp[201][201][201] = {};
char done[201][201][201] = {};
int dfs(int a, int b, int c) {
if(a == 0 && b == 0 && c == 0)
return 0;
int i, j;
if(a > b) i = a, a = b, b = i;
if(b > c) i = b, b = c, c = i;
if(a > c) i = a, a = c, c = i;
if(done[a][b][c])
return dp[a][b][c];
done[a][b][c] = 1;
for(i = 1; i <= a; i++)
dp[a][b][c] |= !dfs(a-i, b, c);
if(dp[a][b][c]) return 1;
for(i = 1; i <= b; i++)
dp[a][b][c] |= !dfs(a, b-i, c);
if(dp[a][b][c]) return 1;
for(i = 1; i <= c; i++)
dp[a][b][c] |= !dfs(a, b, c-i);
if(dp[a][b][c]) return 1;
j = min(a, b);
for(i = 1; i <= j; i++)
dp[a][b][c] |= !dfs(a-i, b-i, c);
if(dp[a][b][c]) return 1;
j = min(a, c);
for(i = 1; i <= j; i++)
dp[a][b][c] |= !dfs(a-i, b, c-i);
if(dp[a][b][c]) return 1;
j = min(b, c);
for(i = 1; i <= j; i++)
dp[a][b][c] |= !dfs(a, b-i, c-i);
if(dp[a][b][c]) return 1;
j = min(min(a, b), c);
for(i = 1; i <= j; i++)
dp[a][b][c] |= !dfs(a-i, b-i, c-i);
if(dp[a][b][c]) return 1;
return dp[a][b][c];
}
int main() {
int i, j, k;
int cnt = 0;
for(i = 0; i <= 200; i++)
for(j = i; j <= 200; j++)
for(k = j; k <= 200; k++)
if(!dfs(i, j, k)) {
printf("%d %d %d\n", i, j, k);
cnt++;
if(cnt > 3000) return 0;
}
return 0;
}
以上是 TLE 的版本，同時這題也是 2012 高雄站的測機題
以下才是真正通過的，他都已經告訴我答案個數約為 5000，反向更新就好，
O(5000*200 + 200*200*200)
/**********************************************************************************/
/* Problem: a186 "Three-Heap Wythoff's Game" from */
/* Language: C (940 Bytes) */
/* Result: AC(36ms, 5MB) judge by this@ZeroJudge */
/* Author: morris1028 at 2012-12-01 12:09:18 */
/**********************************************************************************/
#include <stdio.h>
char dp[201][201][201] = {};
void update(int a, int b, int c) {
int i, j;
if(a > c) i = a, a = c, c = i;
if(b > c) i = b, b = c, c = i;
if(a > b) i = a, a = b, b = i;
if(c > 200) return;
dp[a][b][c] = 1;
}
int main() {
int i, j, k, a;
int cnt = 0;
for(i = 0; i <= 200; i++)
for(j = i; j <= 200; j++)
for(k = j; k <= 200; k++)
if(!dp[i][j][k]) {
printf("%d %d %d\n", i, j, k);
for(a = 1; a <= 200; a++) {
update(i+a, j, k);
update(i, j+a, k);
update(i, j, k+a);
update(i+a, j+a, k);
update(i+a, j, k+a);
update(i, j+a, k+a);
update(i+a, j+a, k+a);
}
}
return 0;
}