BICO GAMING

• Problem Description

  
  The much anticipated video game ""BiCo Grid"" has been released. The rules of ""Bico Grid"" are very simple.
  
  The game field is a 100x100 matrix, where each cell is either a blocked cell, or a cell with some number of coins. For a regular player the look of the field seems pretty random, but the programmer in you recognizes the following pattern: the i-th cell on the n-th row contains C(n, i) coins if and only if 0 i n, all other cells are blocked. Record C(n, i) denotes binomial coefficient ""n choose i"".
  
  The player starts from the cell situated at row R and column C in the matrix. The objective is to collect exactly G number of coins from matrix in several moves. There are some rules:
  
  On each move the player must collect all the coins from some unblocked cell in the current column.
  The rules of the game state, that player mustn't be really greedy, so the number of coins he collected must not increase. In other words, if at some move the player collected X coins then further he cannot collect more than X coins in a single move.
  After each move, the player is immediately moved to some cell of the column W-1 (where W denotes the current column of the player). If the current column of the player has index 0, the game ends.
  The game ends when player collects exactly G number of coins.
  You are given the description of the game. Please, output the sequence of moves that win the game (collect exactly G coins)! It is guaranteed that if the player will play optimally it is possible to win the game.
  
  Input
  
  The first line of the input contains an integer T denoting the number of test cases. Then T lines follows. Each containing three integers, R denoting the starting row, C, denoting the starting column, and G, denoting the number of coins to be collected.
  
  Output
  
  For each test case, output two lines. First line contains K, the number of column visited before completion of game. Second line contains K space separated integers, the number of coins collected from the cells, in the order they were collected.
  
  It is guaranteed that a solution exists. And if there are multiple solutions, print any of them.
  
  Constraints
  
  1 <= T <= 10000
  0 <= C <= 49
  0 <= R <= 99
  1 <= G <= 1012

• CODING ARENA::

• #include<stdio.h>

  long long int a[101][51];

  int main()

  {

  int i,j;

  long long int b[60];

  a[0][0] = 1;

  for(i=1;i<=100;i++)

  for(j=0;j<=i;j++)

  {

  if(j==0)

  a[i][j] = a[i-1][j];

  else if(j==i)

  a[i][j] = a[i-1][j-1];

  else

  a[i][j] = a[i-1][j] + a[i-1][j-1];

  }

  int t,r,c,m=0;

  long long int g;

  scanf("%d",&t);

  while(t--)

  {

  m=0;

  scanf("%d %d %lld",&r,&c,&g);

  while(g>0)

  {

  i=c;

  while((a[i][c]<=g)&&(i<=99))

  i++;

  i--;

  b[++m] = a[i][c];

  g-=a[i][c];

  c--;

  }

  printf("%d\n",m);

  for(i=1;i<=m;i++)

  printf("%lld ",b[i]);

  printf("\n");

  }

  return 0;

  }

• Test Case 1

  
  Input (stdin)

  3
  
  3 2 5
  
  3 3 10
  
  5 4 7
  
  

  Expected Output

  2
  
  3 2 
  
  1
  
  10 
  
  3
  
  5 1 1 

• Test Case 2

  
  Input (stdin)

  3
  
  3 2 4
  
  3 3 9
  
  5 4 6
  
  

  Expected Output

  2
  
  3 1 
  
  3
  
  4 3 2 
  
  2
  
  5 1