[ZJ][博奕] a186. Three-Heap Wythoff's Game＠Morris' Blog

2012-12-01 12:13:40| 人氣503| 回應0 | 上一篇 | 下一篇

[ZJ][博奕] a186. Three-Heap Wythoff's Game

推薦 0 收藏 0 轉貼0 訂閱站台

內容：

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。

範例輸入：

(本題無須輸入)

範例輸出：

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;
}

我要檢舉

#a186#Three-Heap Wythoff's Game#博奕

台長： Morris

您可能對以下文章有興趣

d919. 最大面積

a191. 在世界遙遠的彼方

[ZJ][插頭DP] a228. 就少一個插座用很不方便

[ZJ][0/1背包] a587. 祖靈好孝順 ˋˇˊ

人氣(503) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: ZeroJudge |
此分類下一篇:[ZJ][2DST][zkw] d800. ST版区间MAX
此分類上一篇:[ZJ][Greedy、並查集] a567. 死線排程

回應(0)