Question

Question No. 1 of 2 30 Marks
Pass The Ball
1
2
3
4.
5
6
7
8
The 'Miscria Champions League' (MCL) is coming soon, and its preparations have already started. Thunde
Cracker is busy practicing with his team, when suddenly he thinks of an interesting problem.
ThunderCracker's team consists of 'N' players (including himself). All the players stand in a straight line (n
umbered from 1 to N), and pass the ball to each other. The maximum power with which any player can hi
t the ball on the i'th pass is given by an array Aj. This means that if a player at position '' (1<=j<=N) has th
e ball at the time of the i'th pass, he can pass it to any player with a position from (j-A;) to (j-1), or from
(+1) to (i+A;) (provided that the position exists).
Now, ThunderCracker wants to find out the number of ways in which, after exactly M passes, the ball re
aches his friend Munkee, given that the first pass is made by ThunderCracker. (Two ways are considered
different if there exists atleast one pass which resulted in the ball being passed to a different player.)
10
11
12
13
14
15
16
17
18
19
20
21
22
Input :
The first line of the input consists of 4 space separated integers - N (denoting
the number of players), M (denoting the number of passes), and X and Y, denoting
Thundercracker's and Munkee's numbers respectively.
The next line contains M space separated integers, denoting array A, the power
with which passes can be made in the i'th pass (1<=i<=M).
24
25
26
Output:
A single integer, that is the number of ways in which the ball can be passed such
that the first pass is made by Thundercracker, and the ball reaches Munkee after
M passes. As the answer can be very large, output it modulo 1000000007.
Constraints :​

Answer 1

Answer:

after seeing I quit this is a question? bruh

Answer 2

Output:

A single integer, that is the number of ways in which the ball can be passed such

that the first pass is made by Thundercracker, and the ball reaches Munkee after

M passes. As the answer can be very large, output it modulo 1000000007.

Solution:

The goal is to find the number of ways in which, after exactly M passes, the ball reaches a specific player, given that the first pass is made by a specific player.

Let's define dp[i][j] as the number of ways in which the ball can reach player j after I pass, given that the first pass is made by Thundercracker (player X). We can initialize dp[0][X] = 1 since Thundercracker has the ball initially.

Then, for each subsequent pass I, we can update the number of ways to reach each player j based on the number of ways to reach its possible previous positions. This gives us the recurrence relation:

dp[i][j] = sum(dp[i-1][k]) for all k in the range j-Ai <= k <= j+Ai

Finally, the answer we are looking for is dp[M][Y], i.e., the number of ways to reach player Y after M passes.

To avoid overflow, we can take the modulo 1000000007 at each step of the recurrence relation.

Overall, this algorithm has a time complexity of O(NM^2), which is sufficient to handle the constraints given in the problem (1 <= N, M <= 300, 1 <= Ai <= N).

#SPJ3