#include <stdio.h>
#include <stdlib.h>

extern int *registerme ();
extern int makemove1 ( int );
extern int makemove2 ( int );

int *dptable ( int n, int k, int *p )
{
   int *T, i, j;

   T = (int *)malloc((n + 1) * sizeof(int));
   for (i=0; i<=n; ++i) {
      T[i] = -1;
      for (j=k-1; j>=0; --j) {
         if ((i >= p[j]) && (T[i-p[j]] == -1)) {
            T[i] = j; break;
         }
      }
   }
   return T;
}

void playgame1 ( int n, int k, int *p, int *T )
{
   while (n > 0) {
      if (T[n] != -1) {
         n = makemove1(T[n]);
      } else {
         n = makemove1(rand() % k);
      }
   }
}

/* The T values are periodic of least period t = first + last, where
   first = p[0] and last = p[0] + k - 1. In order to see why, suppose
   that you are in a losing position with i items left in the bag.
   Whatever move in [first, last] you make, the opponent can take out
   t - move items leaving you in the same position modulo t. What remains
   is to argue that this behavior of the opponent is sometimes the only
   optimal choice of the opponent. Suppose that you face n = t + first - 1.
   It is easy to see that this is a losing position for you. Suppose you
   choose move = first, so the opponent gets n = t - 1 = first + last - 1.
   The opponent should take out t - move = last items. If the opponent
   removes last - r items for some r > 0, you receive a bag with
   first + r - 1 items. Since last - r is a valid move for the opponent
   and r >= 1, first + r - 1 is a valid move for you too, that is, you
   empty the bag, and the opponent loses.

   It therefore suffices to know T[i] for i = 0, 1, 2, ..., t-1.
   Clearly, T[i] = -1 for i = 0, 1, 2, ..., first - 1. For i in the
   range [first, last], you can take all i items presenting the
   opponent an empty bag. So these are winning positions for you.
   In particular, you can take T[i] = i - first for these values of
   i. For i in the range [last + 1, t - 1] = [last + 1, last + (first - 1)],
   you cannot empty the bag. But if you pick last items, the opponent
   gets a bag with 1, 2, 3, ..., or first - 1 items, and loses. When
   i = t - 1, last is the only optimal move for you.
*/
void playgame2 ( int n, int k, int *p )
{
   int m, t, first, last, residue;

   first = p[0];
   last = first + k - 1;
   t = first + last;
   while (n > 0) {
      residue = n % t;
      if (residue < first) m = rand() % k;
      else if (residue <= last) m = residue - first;
      else m = k - 1;
      n = makemove2(m);
   }
}

int main ()
{
   int *p, *T;

   p = registerme();
   T = dptable(p[0],p[1],p+2);
   playgame1(p[0],p[1],p+2,T);
   playgame2(p[0],p[1],p+2);
}