In a soccer game, n players are standing in a line, each player having a number from 1 to n. The coach decided that the team will make exactly m passes. The ball is initially with player number c. Also the coach instructs to pass only to players within a distance of Ak-1 towards either side holding the ball(between consecutive players distance is 1 unit) before the kth pass(for each k from 1 to m). You have to output the number of times each player had the ball in all possibilities of such games.
Soccer Line
Constraints:
0 < t <= 10
0 < n <= 10
0 < m <= 9
0 < c <=n
A[i] <= 4 for all i
Input Format:
first line contains the number of test cases t
for each test case you have two lines
line1 consists of n and m and c
line2 consists of array A of size m which represents the distance to which players can pass during each pass
Output Format:
result for each test case separated by newline
number of passes each player got separated by space
Sample Input:
1
4 2 3
1 2
Sample Output:
1 2 3 2
Explaination:
lets represent the player without ball by 0 and the player with a ball using 1
the the initial positioning looks like
No Pass Position : 0010
/ \
Pass 1 possible positions 0100 0001
/ | \ / \
Pass 2 possible positions 1000 0010 0001 0100 0010
During the 1st pass the player can only pass to distance one on either side (since A[0] is 1)
During the 2nd pass the player can only pass to distance two on either side (since A[1] is 2)
For player one there is only 1 case where he has the ball 1000 so output for player 1 is 1
For player two the cases where he has the ball are left scenario in pass 1 and left scenario in pass 2 (all 0100 cases) so his total is 2
similarly for player 3 it is 3 and for player 4 it is 2. Note that sum of all these numbers is equal to the nodes shown in the above tree.
Time Limit(s):
10
Memory Limit(MBs):
500