/********* Problem 5--Going Down!**************************************
 If you tried to come up with an easy mathematical formula to solve 
 this problem, you almost certainly came up empty.  Mathematicians
 have tried for years to find patterns in partition problems such as
 this one.  And patterns do exist, but they are very hard to spot.
 On the other hand, it was not necessary to do an exhaustive search,
 either:  computing and counting every single non-increasing sequence
 works, but there was an easier way of looking at it.
 This is an excellent example of dynamic programming using recursion and
 memoization.
 **********************************************************************/

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

#define MIN(a,b) ((a)<(b)?(a):(b))

int main (int argc, char **argv);
static int ct (int n, int k, int max);
static void printinfo (int n, int k, int count, int cs);

FILE *in, *out;

/****** main **********************************************************
 main repeatedly reads n and k from the input file, computes how many
 different non-increasing sequences of length k totalling n exist, and
 prints this answer--formatted properly--to the output file.
 **********************************************************************/

int main (int argc, char **argv) {

  int n, k, /* The parameters n and k */
      c=0;    /* The case number of this input example (for output) */

 in = fopen ("prob5.in","r");   /* Redirecting input and output */
 out = fopen ("prob5.out","w");
 while (1) {
  fscanf (in,"%d %d",&n,&k);   /* read in the integers */
  if (n==0 && k==0) break;  /* stop when they are both zero */
                           /* compute and print the next case */
  printinfo (n,k,ct(n,k,n-k+1),++c);
 }
 fclose (in);      /* close our files */
 fclose (out);
 return EXIT_SUCCESS;
}

/******* ct ***********************************************************
 ct accepts parameters n, k, max and computes the number of 
 non-increasing sequences of length k totalling n, none of whose entries
 are greater than max.  The basic idea is this:
 The largest possible value that the first value in the sequence could
 be is max.
 The smallest possible value that the first value in the sequence could
 be is ceil (n/k), which occurs when the total amount is distributed
 evenly among all numbers in the sequence (ceil means rounded up).
 So, for each of the possible values for the the first element in the
 sequence, we compute how many possible ways there are to divide the
 rest of the total up among the other k-1 elements, such that none of
 the succeeding elements are larger than the first one (which is how
 we enforce non-increasing).
 Notice that when ct is called in main, the value n-k+1 is assigned to
 max.  That's the largest value an element could possibly be:  all 
 elements but the first are set to 1.
 Additionally, past results of n, k, max are stored in a table.  That
 way, we avoid recomputing common subproblems.
 **********************************************************************/

static int ct (int n, int k, int max) {

  static int ctarr[100][100][100];  /* The memoized table */
  int s,                            /* The value to be returned */
      i;                            /* loop counter */

 if (ctarr[n-1][k-1][max-1] > 0)   /* If this value is already in the */
  return ctarr[n-1][k-1][max-1];      /* table, just return it! */
 if (k==1)     /* Otherwise, if a seqence is of length 1, there is */
  return 1;       /* only one way to do that. */
               /* Otherwise, we try all possible combinations for the */
               /* first element in the sequence. */
 for (s=0,i=max;i>=(n+k-1)/k;i--)
               /* the smallest we can be is n/k rounded up */
  s += ct(n-i,k-1,MIN(i,n-i-(k-1)+1)); 
           /* We compute the number of valid sequences starting with i.
              This amounts to computing the number of sequences 
              of length k-1 whose sum is n-i none of whose elements
              exceed i.  Additionally, none of the elements can exceed
              n-i-(k-1)+1, which is what the next element of the
              sequence would be if all the subsequent values were 1. */
 ctarr[n-1][k-1][max-1] = s;  /* Add this value to the table. */
 return s;
}

/***** printinfo ******************************************************
 printinfo accepts n, k, count (representing the number of valid
 sequences) and cs (representing this specific case number) and prints
 the output in the reasonably sophisticated manner required by the
 problem.  (It keeps everything grammaticaly correct, for example.)
 This routine is entirely self-explanatory.
 **********************************************************************/

static void printinfo (int n, int k, int count, int cs) {

 if (count==1)
  if (k==1)
   fprintf (out,
            "Case %d: One non-increasing sequence with one integer has "
            "%d as its sum.\n",cs,n);
  else
   fprintf (out,
            "Case %d: One non-increasing sequence with %d integers has "
            "%d as its sum.\n",cs,k,n);
 else
  fprintf (out,
           "Case %d: %d non-increasing sequences with %d integers have "
           "%d as their sum.\n",cs,count,k,n);
}