【题解】ZOJ-3057 Beans Game

发表于 分类于 ， 本文字数： 537 阅读时长 ≈ 1 分钟
ZOJ-3057 Beans Game 类型 博弈论 三维Wythoff博弈

Beans Game(ZOJ-3057)

题面

There are three piles of beans. TT and DD pick any number of beans from any pile or the same number from any two piles by turns. Who get the last bean will win. TT and DD are very clever.

输入

Each test case contains of a single line containing 3 integers a b c, indicating the numbers of beans of these piles. It is assumed that 0 <= a,b,c <= 300 and a + b + c > 0.

输出

For each test case, output 1 if TT will win, ouput 0 if DD will win.

样例输入

1
2
3
1 0 0
1 1 1
2 3 6

样例输出

1
2
3
1
0
0

提示

无

思路

对于先手来说，如果数量分别为(a, a, b)或(a, b, a)，或(b, a, a)的形式，那么先手必赢，因为先手可以使其成为(a, a, a)的形式，那么不论后手怎么拿，都是先手最后使其成为(a, a, a)的形式直至(0, 0, 0)；如果(a, b, c)是必败态，那么将其中某个数加k，或将其中某两个数同时加k，就是必胜态。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
using namespace std;
bool SG[305][305][305];

void getSg(){
    for(int i=0; i<=300; i++)
    for(int j=0; j<=300; j++)
    for(int k=0; k<=300; k++){
        if(SG[i][j][k] == 0){
            for(int x=i+1; x<=300; x++) SG[x][j][k] = 1;
            for(int x=j+1; x<=300; x++) SG[i][x][k] = 1;
            for(int x=k+1; x<=300; x++) SG[i][j][x] = 1;
            for(int x=1; x+i<=300 && x+j<=300; x++) SG[x+i][x+j][k] = 1;
            for(int x=1; x+j<=300 && x+k<=300; x++) SG[i][x+j][x+k] = 1;
            for(int x=1; x+i<=300 && x+k<=300; x++) SG[x+i][j][x+k] = 1;
        }
    }

}

int main()
{
    getSg();

    int a, b, c;
    while(~scanf("%d %d %d", &a, &b, &c))
    {
        printf("%d\n", SG[a][b][c]);
    }
    return 0;
}