मान लीजिए रीमा निम्नलिखित गेम खेलती है, जो कार्ड गेम "21" पर आधारित है। तो रीमा 0 अंकों से शुरू करती है, और जब तक उसके पास K से कम अंक हैं, तब तक संख्याएं निकालती है। अब, प्रत्येक ड्रॉ के दौरान, वह [1, W] रेंज से यादृच्छिक रूप से एक पूर्णांक संख्या में अंक प्राप्त करती है, जहां W दिया गया है, और यह एक पूर्णांक है। अब प्रत्येक ड्रॉ स्वतंत्र है और परिणामों की समान संभावनाएं हैं। रीमा संख्याएं निकालना बंद कर देती है जब उसे K या अधिक अंक मिलते हैं। हमें यह पता लगाना है कि उसके N या कम अंक होने की संभावना क्या है?
तो यदि N = 6, K 1 है और W 10 है, तो उत्तर 0.6 होगा, क्योंकि रीमा को एक कार्ड मिलता है, फिर रुक जाती है, 10 संभावनाओं में से 6 में, वह N = 6 अंकों पर या उससे नीचे है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- यदि k 0 है, या N >= K + W है, तो 1 लौटाएं
- आकार N + 1 की एक सरणी dp बनाएं, dp[0] := 1 सेट करें
- wsum := 1.0, ret := 0.0 सेट करें
- i को 1 से N की रेंज में
- dp[i] := wsum / W
- यदि i < K, तो wsum := wsum + dp[i], अन्यथा ret := ret + dp[i]
- यदि i - W >= 0, तो wsum := wsum - dp[i - W]
- ret लौटाएं
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
double new21Game(int N, int K, int W) {
if(K == 0 || N >= K + W) return 1.0;
vector <double> dp (N + 1);
dp[0] = 1;
double Wsum = 1.0;
double ret = 0.0;
for(int i = 1; i <= N; i++){
dp[i] = Wsum / W;
if(i < K){
Wsum += dp[i];
}else ret += dp[i];
if(i - W >= 0) Wsum -= dp[i - W];
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.new21Game(6, 1, 10));
}
इनपुट
6 1 10
आउटपुट
0.6