**Problem Link : **
[Contest][1]
[Practice][2]
**Difficulty : ** Medium
**Pre-requisites : ** Expectations
**Solution : **
The first instinct in this problem is to formulate a DP, since the answer to a future state depends on the current one in a trivial manner. That basically goes through (more details on the dp later), apart from the fact that N could be as big as 10^18. The simple way to work around this is to observe that there’s another constraint given, ln(N) < 14 (P - 1). This basically implies the following inequality,
N/10^(6*P) < 10^(-6)
As a result, the expected number of birds you shoot down after X=10^6 will be less that 10^(-6), and hence the range N can be ignored! The DP can then be worked backwards from X=10^6.
More on the DP :
Let DP[i] = Expected number of birds you will shoot down from now onwards (that is from time i to time N (range))
Trivially, DP[i] = DP[i + T + R]/(i^P) + DP[i + T] * (1 - 1/(i^P))
Naturally, this DP is evaluated from backwards, and the answer to the question is DP[1].
In context of the above comments, if we need DP[1] within 10^(-6) of it’s correct value, beginning from DP[min (10^6, R)], and going backwards, suffices.
**Setter’s code : **
[3]
[1]: http://www.codechef.com/WPC1401/problems/IITK1P08
[2]: http://www.codechef.com/problems/IITK1P08
[3]: http://www.codechef.com/viewsolution/5215766