PersonalCorpus 版 (精华区)

41720 2002-10-15 04:54:57 Accepted
1039 C++ 00:00.09 896K Big Guava

int res[20],len;
char used[1<<19];

int encode(bool *mark)
{
    int i,k=0;
    for (i=2;i<21;i++) {
        k<<=1;
        if (mark[i]) k++;
    }
    return k;
}

bool win(bool *mark, int pos)
{
    int i,j,k;
    bool newm[21],ok;

    memcpy(newm,mark,sizeof(newm));
    for (k=pos;k<21;k+=pos) {
        for (i=2;i<21-k;i++) if (mark[i]) newm[i+k]=true;
        newm[k]=true;
    }
    j=encode(newm);
    k=used[j];
    if (k>0) {
        if (k==1) return false; else return true;
    }
    for (i=2;i<21;i++) if ((!newm[i])&&(win(newm,i))) {
        used[j]=1;
        return false;
    }
    used[j]=2;
    return true;
}


int main()
{
#ifndef ONLINE_JUDGE
    freopen("c:\\0acm\\zju\\i1039","r",stdin);
    freopen("c:\\0acm\\zju\\o1039","w",stdout);
#endif

    int i,j,k,n,t=0;
    bool mark[21];

    memset(used,0,sizeof(used));  used[(1<<19)-1]=2;

    scanf("%d\n",&n);
    for (t=1;t<=n;t++) {
        scanf("%d\n",&k);
        memset(mark,1,sizeof(mark));
        for (i=0;i<k;i++) {
            scanf("%d",&j);
            mark[j]=false;
        }
        len=0;
        for (i=2;i<21;i++) if (!mark[i]) if (win(mark,i)) res[len++]=i;

        printf("Scenario #%d:\n",t);
        if (len>0) {
            printf("The winning moves are:");
            for (i=0;i<len;i++) printf(" %d",res[i]);
            printf(".\n\n");
        } else printf("There is no winning move.\n\n");
    }
}