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