Menu Close

G Number of Coins….[Cprogm] FcukTheCode

The much-anticipated video game “PUBG” has been released. The rules of “PUBG” are very simple.

The game field is a 100×100 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 the G number of coins from the 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 the player collects exactly the 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 follow. 
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 columns visited before completion of the 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.
#include <stdio.h>
int main()
{int i,j,row,col,t,moves;
long long int g,grid[100][50],coins[50];
for(i=0;i<100;i++){
 grid[i][0]=1;
 for(j=1;j<=i&&j<50;j++){
 if(i==j)
 grid[i][j]=1;
 else
 grid[i][j]=grid[i-1][j-1]+grid[i-1][j];
 }
}
scanf("%d",&t);
while(t--){
 scanf("%d %d %lld",&row,&col,&g);
 moves=0;
 while(g>0){
 row=col;
 while(row<100&&grid[row][col]<=g)
 row++;
 row--;
 g=g-grid[row][col];
 coins[moves]=grid[row][col];
 moves++;
 col--;
 }
 printf("%d\n",moves);
 for(i=0;i<moves;i++)
 printf("%lld ",coins[i]);
 printf("\n");
}
return 0;
}

 


INPUT_1:
3
3  2  5
3  3  10
5  4  7

OUTPUT:
2
3  2
1
10
3
5  1  1


INPUT_2:
3
1  2  4
1  3  9
5  3  6

OUTPUT:
2
3  1
3
4  3  2
3
4  1  1