UVa 10578 - The Game of 31

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址
中文網址

兩人輪流把數字往上加,可以加的數字為 1~6 ,並且各數字只能出現 4 次,看誰讓數字大於 31 ,就輸了。

Solution

長度為偶數,現在就是輪到 B,反之為 A。(ABAB…)
只要此時(假設是輪到 A ),在下一輪中有一種走法能讓 B 贏,A 就會輸。
每一輪都有 6 個選擇 1~6 ,除非某數字已經出現 4 次。
利用 DFS 去跑每種選擇:

for (int i = 0; i < 6; i++)
{
    if (num[i] < 4)
    {
        num[i]++;
        if (dfs(next) == next)//如果下一個有會贏的,代表現在這個會輸
        {
            now = next;
            num[i]--;
            break;
        }
        num[i]--;
    }
} 

邊紀錄下每種狀況(都只會有一個贏家),可供重複查找。

Code

UVa 10578UVa 10578 - The Game of 31
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int dp[6][6][6][6][6][6];
int num[6];
int dfs(int now);
int main()
{
char str[25];
int *p = dp[0][0][0][0][0];
//init
for (int i = 0; i < 46656; i++)
*(p++) = -1;

while (gets(str))
{
fill(num, num + 6, 0);
int len = strlen(str);
for (int i = 0; i < len; i++)
num[str[i] - '1']++;

//now is A , if len is odd.Otherwise,is B
printf("%s %c\n", str, dfs(len % 2) ? 'A' : 'B');
}

return 0;
}
int dfs(int now)
{
if (num[0] * 1 + num[1] * 2 + num[2] * 3 + num[3] * 4 + num[4] * 5 + num[5] * 6 > 31)//現在超過 31 ,也就是另一位玩家會贏
return now ^ 1;
else if (dp[num[0]][num[1]][num[2]][num[3]][num[4]][num[5]] != -1)
return dp[num[0]][num[1]][num[2]][num[3]][num[4]][num[5]];

int next = now ^ 1;//下一個輪到的人
for (int i = 0; i < 6; i++)
{
if (num[i] < 4)
{
num[i]++;
if (dfs(next) == next)//如果下一個有會贏的,代表現在這個會輸
{
now = next;
num[i]--;
break;
}
num[i]--;
}
}

return dp[num[0]][num[1]][num[2]][num[3]][num[4]][num[5]] = now;//return winner
}