- Problem Statement.
- A
**main()**with the examples compiled in. - A skeleton that compiles with
**main.cpp**. -
**Problem Given in Topcoder**: January, 2009 -
**Competitors who opened the problem**: 233 -
**Competitors who submitted a solution**: 163 -
**Number of correct solutions**: 104 -
**Accuracy (percentage correct vs those who opened)**: 44.64% -
**Average Correct Time**: 22 minutes, 11 seconds.

I'm going to save you some time. (Maybe). Don't think about how to win the game. Instead, think about dynamic programming. You can solve this with recursion:

- The base case is when you can win the game in one move. Return the answer.
- Otherwise, for each value of
**i**from 1 to**maxAdd**, call the method recursively on**(next+i)**. If the answer is -1, then your opponent has lost, so**i**is your answer. If the answer is anything but -1, then you need to try another value of**i**. - If you can't find a value of
**i**that lets you win the game, then you lose. Return -1.

/* Topcoder SRM 183, D2, 350-pointer. CountGame James S. Plank Wed Mar 1 20:35:06 EST 2017 */ #include <vector> #include <iostream> #include <cstdio> #include <cstdlib> using namespace std; /* I've added a cache for dynamic programming to the class. */ class CountGame { public: int howMany(int maxAdd, int goal, int next); vector <int> cache; }; int CountGame::howMany(int maxAdd, int goal, int next) { int i; /* The first time that this is called, I initialize the cache. My "empty" value is -2. This is because -1 is a valid answer. */ if (cache.size() == 0) cache.resize(goal+1, -2); /* Check the cache and return if I've already solved this value of next. */ if (cache[next] != -2) return cache[next]; /* Here's the base case of the recursion. If I can solve the problem in one move, then I return that move. */ if (goal - next + 1 <= maxAdd) return goal-next+1; /* Now I go through and test every value of i from 1 to maxAdd. If my opponent loses after I add i to next, then I win! */ for (i = 1; i <= maxAdd; i++) { if (howMany(maxAdd, goal, next+i) == -1) { cache[next] = i; return i; } } /* Otherwise, I lose. :( */ cache[next] = -1; return -1; } |