The Game of 31

Problem Description
The game of 31 was a favourite of con artists who rode the railroads in days of yore. The game is played with a deck of 24 cards: four labelled each of 1, 2, 3, 4, 5, 6. The cards in the deck are visible to both players, who alternately withdraw one card from the deck and place it on a pile. The object of the game is to be the last player to lay a card such that the sum of the cards in the pile does not exceed 31. Your task is to determine the eventual winner of a partially played game, assuming each player plays the remainder of the game using a perfect strategy.
For example, in the following game player B wins:
Player A plays 3
Player B plays 5
Player A plays 6
Player B plays 6
Player A plays 5
Player B plays 6

Input
The input will consist of several lines; each line consists of a sequence of zero or more digits representing a partially completed game. The first digit is player A's move; the second player B's move; and so on. You are to complete the game using a perfect strategy for both players and to determine who wins.

Output
For each game, print a line consisting of the input, followed by a space, followed by A or B to indicate the eventual winner of the game.

Sample Input
356656
35665
3566
111126666
552525

Sample Output
356656 B
35665 B
3566 A
111126666 A
552525 A

对象

2个回答

按赞数排序 
 #include<iostream>
#include<cstdlib>
#include<stdio.h>
#include<string.h>
#include<string.h>
#include<memory.h>
using namespace std;
int sg[50];
int num[7];
bool dfs(int sum)
{
    if(sum>=31) return 0;
    for(int i=1;i<=6;i++)
    {
        if(num[i]&&sum+i<=31)
        {
            --num[i];
            if(dfs(sum+i)==0) {++num[i];return 1;}
             ++num[i];//回溯
        }
    }
    return 0;
}
int main()
{
    char str[35];
    while(scanf("%s",str)!=EOF)
    {
        int sum=0;
        int l=strlen(str);
        for(int i=1;i<=6;i++)
        num[i]=4;
        for(int i=0;i<l;i++)
        {
            sum+=str[i]-'0';
            num[str[i]-'0']--;
        }
        if(sum>=31)
        {
            printf("%s ",str);
            if(l&1) puts("A");
            else puts("B");
            continue;
        }
        printf("%s ",str);
        if(dfs(sum))
        {
            if(l&1)  puts("B");
            else puts("A");
        }
        else
        {
         if(l&1)  puts("A");
         else puts("B");
       }
    }
}
/*
356656
35665
3566
111126666
552525
*/
Csdn user default icon
插入链接
本地上传 网络图片
上传中...
上传图片
插入图片
抄袭、复制答案，以达到刷声望分或其他目的的行为，在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了！
我要提问
立即提问
相关内容推荐