// Spring 2012 game // On each turn, player may select 1..maxPickup pebbles, // but no more than the remaining number. Loser is the player // stuck with an empty pile. #include #include int cache[1001]; int test(int pileSize,int maxPickup) { // Returns 1 if there is a winning play. int i; if (cache[pileSize]!=(-1)) return cache[pileSize]; if (pileSize==0) { cache[pileSize]=0; return 0; } for (i=1; i<=pileSize && i<=maxPickup && test(pileSize-i,maxPickup); i++) ; if (i>pileSize || i>maxPickup) { cache[pileSize]=0; return 0; } cache[pileSize]=1; return 1; } main() { int pileSize,maxPickup; int i; scanf("%d %d",&pileSize,&maxPickup); while (pileSize && maxPickup) { for (i=0;i<=pileSize;i++) cache[i]=(-1); for (i=1; i<=pileSize && i<=maxPickup && test(pileSize-i,maxPickup); i++) ; if (i>pileSize || i>maxPickup) printf("Can't win\n"); else printf("Win by taking %d\n",i); scanf("%d %d",&pileSize,&maxPickup); } }