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

/* R is the total number of available red marbles.
   B is the total number of available blue marbles.
   u is the total number of red marbles already placed in arr.
   v is the total number of blue marbles already placed in arr.
   arr stores a particular arrangement of u + v marbles placed so far.
*/
int part1 ( int R, int B, int u, int v, char *arr)
{
   int cnt = 0;

   /* We have placed all available red and blue marbles in arr. That is,
      we have discovered one valid configuration. Print it, and return one
      to indicate that this is a valid arrangement of all the marbles.
   */
   if ((u == R) && (v == B)) {
      printf("%s\n", arr);
      return 1;
   }

   /* If all available red marbles are not already placed in arr, try to put
      another red marble at the (u+v+1)-st position (index u+v) in arr.
   */
   if (u < R) {
      /* A red marble is allowed at the zeroth index. At a positive index, a
         red marble is allowed if and only if the previous index contains a
         blue marble.
      */
      if ((u+v == 0) || ((u+v >= 1) && (arr[u+v-1] == 'b'))) {
         arr[u+v] = 'r'; /* Place the red marble */
         cnt += part1(R,B,u+1,v,arr); /* Add to cnt how many possibilities can
                                         be discovered after this placement of
                                         the red marble. */
      }
   }

   /* If all available blue marbles are not already placed in arr, put
      another blue marble at the (u+v+1)-st position (index u+v) in arr.
   */
   if (v < B) {
      /* This can proceed unconditionally. */
      arr[u+v] = 'b'; /* Place the blue marble */
      cnt += part1(R,B,u,v+1,arr); /* Add to cnt how many possibilities can
                                      be discovered after this placement of
                                      the blue marble. */
   }

   /* Return the total number of possibilities discovered from the input
      configuration of u red and v blue marbles. */
   return cnt;
}

/* R is the total number of available red marbles.
   B is the total number of available blue marbles.
   u is the total number of red marbles already placed in arr.
   v is the total number of blue marbles already placed in arr.
   arr stores a particular arrangement of u + v marbles placed so far.
*/
int part2 ( int R, int B, int u, int v, char *arr)
{
   int cnt = 0;

   if ((u == R) && (v == B)) {
      printf("%s\n", arr);
      return 1;
   }

   if (u < R) {
      if ((u+v == 0) || (u+v == 1) ||
         ((u+v >= 2) && ((arr[u+v-1]=='b') || (arr[u+v-2]=='b')))) {
         arr[u+v] = 'r';
         cnt += part2(R,B,u+1,v,arr);
      }
   }

   if (v < B) {
      arr[u+v] = 'b';
      cnt += part2(R,B,u,v+1,arr);
   }

   return cnt;
}

int main ()
{
   int R, B, cnt;
   char *arr;

   printf("Enter number of red marbles (R)  : "); scanf("%d", &R);
   printf("Enter number of blue marbles (B) : "); scanf("%d", &B);
   arr = (char *)malloc((R+B+1)*sizeof(char));
   arr[R+B] = '\0';

   printf("\nPart 1\n");
   cnt = part1(R,B,0,0,arr); /* Initially place no marble in arr */
   printf("Total number of possibilities is %d\n", cnt);

   printf("\nPart 2\n");
   cnt = part2(R,B,0,0,arr);
   printf("Total number of possibilities is %d\n", cnt);

   free(arr);
}