**New 21 Game** is a problem that is based on the **card game “21”**. The problem statement of this problem is simple. We are initially having 0 points. If the value of our current points is less than K points then we draw numbers. During each draw we gain an integer number D points randomly from range 1 to M. Each draw does not depend upon the previous draw. At each draw, the outcome has equal probabilities. Once we hit the points greater than or equal to K point then stop drawing the number. We have to find out the probability that we have less than N points.

**Input Format**

First-line containing three integer numbers N, K and M.

**Output Format**

Print the single float type variable containing probability such that absolute error less than 10^-5.

**Constraints**

- 0<=K<=N<=10000.
- 1<=M<=10000.

**Sample Input:** N=6, K=1, M=10

**Sample Output:** 0.600000

**Explanation: **We get a single card, then stops. In 6 out of W = 10 possibilities, our points below N = 6 points.

## Working Process For New 21 Game

By the use of the **Dynamic Programming** approach for finding the solution here. DP[n] = sum(dp from n-W to n-1)/W, since we can reach score n by being at score n-1 and drawing a 1, or being at score n-2 and drawing a 2, and so on. The chance of being at score n-i and drawing i is dp[n-i]/W. However, if we’ve stopped drawing, then we need to sum from n-W to K-1. So properly, dp[n] = sum(dp from max(n-W, 0) to min(n-1, K))/W. The final result is the sum of dp in the range [K, N], since the set of possible end scores are K to K + W – 1, (as such the sum of dp from K to K + W – 1 should be 1.0 if we actually computed the whole vector) and we’re looking for the chance of ending up with a score below or equal to N.

Therefore, the chance of getting N or less points is the chance of ending at K (dp[K]), plus the chance of ending at K+1, and so on up to N.

## Algorithm For New 21 Game

Step:1 Find the maximum possible score(m_score) which we reach(min(N,K+M-1)). Step:2 Create a array of type double for storing the probabilities at each instant. Step:3 Set DP[0] = 1.00 Step:4 Set windowsum = 0.0 Step:5 For i in range 0 to maximum possible score(m_score): if i is less than K then: windowsum+=DP[i] if i is greater than or equal to M then: windowsum-=DP[i] DP[i+1] = windowsum/M Step:6 The final result is the sum of dp in range [K, N].

## Implementation For New 21 Game

/*C++ Implementation of "New 21 Game" using DP approach.*/ #include<bits/stdc++.h> using namespace std; int main() { /*input values.*/ int n,k,m; cin>>n>>k>>m; int m_score = min(n, k+m-1); /*dp[n] is the probability that score n will be reached at some point.*/ vector<double> dp(m_score+5); /*Since the game starts at score 0, dp[0] is 100%.*/ dp[0] = 1.0; /* dp[n] = sum(dp from n-W to n-1)/W, since we can reach score n by being at score n-1 and drawing a 1, or being at score n-2 and drawing a 2, and so on. The chance of being at score n-i and drawing an i is dp[n-i]/W. However, if we've stopped drawing, then we need to sum from n-W to K-1. So properly, dp[n] = sum(dp from max(n-W, 0) to min(n-1, K))/W. */ // wsum, the windowed sum, is the sum or the last W elements, or properly // sum(dp from max(n-W, 0) to min(n-1, K)). The next element is wsum/W. double wsum = 0.0; /*Windowed.*/ for(int i=0;i<=m_score;++i) { if(i<k) { // Only add to wsum if we're still drawing. wsum += dp[i]; } if(i-m>=0) { // Delete last element from window. wsum-=dp[i-m]; } dp[i+1]=wsum/m; } /* The final result is the sum of dp in range [K, N], since the set of possible end scores are K to K + W - 1, (as such the sum of dp from K to K + W - 1 should be 1.0 if we actually computed the whole vector) and we're looking for the chance of ending up with a score below or equal to N. Therefore, the chance of getting N or less points is the chance of ending at K (dp[K]), plus the chance of ending at K+1, and so on up to N. */ double ans= accumulate(dp.begin()+k, dp.begin()+n+1, 0.0); /*print the result.*/ cout<<fixed<<setprecision(10)<<ans<<endl; return 0; }

6 1 10

0.6000000000

## Time Complexity

**O(N)** where N is the number of points given to us. We run one loop which runs maximum min(K+M-1, N). So we can say that its linear time complexity. We just update our dp array for each value of i where 0<=i<=min(K+M-1,N).

## Space Complexity

**O(N)** where N is the number of points given to us. We use only single dp array of double type of maximum size equal to min(K+M-1, N).

In the worst case, the maximum size possible is O(N).