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