// 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 test[1001]; main() { int pileSize,maxPickup; int i,j; scanf("%d %d",&pileSize,&maxPickup); while (pileSize && maxPickup) { // Fill in the obvious cases test[0]=0; for (i=1;i<=maxPickup;i++) test[i]=i; // Fill in the interesting cases for (i=maxPickup+1;i<=pileSize;i++) { // Try all possibilities looking for move where opponent loses for (j=1; j<=maxPickup && test[i-j]; j++) ; test[i] = (j>maxPickup) ? 0 : j; } if (test[pileSize]) printf("Win by taking %d\n",test[pileSize]); else printf("Can't win\n"); scanf("%d %d",&pileSize,&maxPickup); } }