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

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