http://acm.pku.edu.cn/JudgeOnline/problem?id=1143
Код:
#include <cstdio>
#include <cstring>
const int size=24;
int list[524292];
inline int map(bool seq[]){
int index=0,i;
for(i=2;i<=20;i++,index<<=1)
if(seq[i])index|=1;
return index>>1;
}
bool dfs(bool source[],int op){
int i,j;
bool judge[24];
memcpy(judge,source,size);
for(judge[op]=false,i=2;op+i<=20;i++)
if(!judge[i])
judge[op+i]=false;
int id=map(judge);
if(list[id]!=0){
if(list[id]>0)return true;
else return false;}
for(i=2,j=0;i<=20;i++){
if(judge[i]&&!dfs(judge,i)){
list[id]=1;
return true;}
}
list[id]=-1;
return false;
}
int main(){
int i,j,n,c,x;
bool source[24];
int ans[16],sum,id;
for(c=1;scanf("%d",&n),n;c++){
memset(source,false,sizeof(source));
sum=0;
for(i=0;i<n;i++){
scanf("%d",&x);
source[x]=true;}
id=map(source);
for(i=2;i<=20;i++){
if(source[i]&&!dfs(source,i))
ans[sum++]=i;}
printf("Test Case #%d\n",c);
if(sum==0){
list[id]=-1;
printf("There's no winning move.\n\n");
}
else{
printf("The winning moves are:");
for(i=0;i<sum;i++)
printf(" %d",ans[i]);
printf("\n\n");}
}
return 0;
}