मान लीजिए कि रीमा निम्नलिखित खेल खेलती है, जो कि ताश के खेल "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 लौटाएं
- एन + 1 आकार की एक सरणी डीपी बनाएं, डीपी सेट करें [0]:=1
- wsum सेट करें:=1.0, रेट करें:=0.0
- i के लिए 1 से N की सीमा में
- dp[i] :=wsum / W
- अगर मैं <के, तो wsum :=wsum + dp[i], अन्यथा ret :=ret + dp[i]
- यदि i - W>=0, तो wsum :=wsum - dp[i - W]
- रिटर्न रिटर्न
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#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