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.
Table of Contents
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).