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