zoj 1827 The Game of 31

#include <iostream>#include <cstdio>#include <cstring>#define maxn 20000using namespace std;int dig[7],f[35][maxn];char s[50];int dfs(int tot,int cur){    if (f[tot][cur]!=0) return f[tot][cur];    for (int i=1; i<=6; i++)    {        if (tot+i>31) continue;        if ((cur/dig[i])%5==0) continue;        if (dfs(tot+i,cur-dig[i])==-1)        { return f[tot][cur]=1;        }    }    return f[tot][cur]=-1;}int main(){    int ans,cur,tot,tep;    dig[1]=1;    dig[0]=4;    for (int i=2; i<=6; i++) dig[i]=5*dig[i-1],dig[0]+=4*dig[i];    while (gets(s))    {        memset(f,0,sizeof f);        cur=dig[0],tot=0;        for (int i=0; s[i]; i++)        { tep=s[i]-'0'; tot+=tep; cur-=dig[tep];        }        if (strlen(s)&1) ans=-1; else ans=1;        ans*=dfs(tot,cur);        if (ans==-1) printf("%s Bn",s); else printf("%s An",s);    }    return 0;}