मान लीजिए एक डाइस सिमुलेटर प्रत्येक रोल के लिए 1 से 6 तक एक यादृच्छिक संख्या उत्पन्न करता है। हम जनरेटर में एक प्रतिबंध पेश करना चाहते हैं जैसे कि यह संख्या i को rollMax[i] (1-इंडेक्स्ड) से अधिक लगातार बार रोल नहीं कर सकता। एक पूर्णांक सरणी rollMax और एक पूर्णांक n दिया गया है, हमें ठीक n रोल के साथ प्राप्त किए जा सकने वाले अलग-अलग अनुक्रमों की संख्या वापस करनी है। दो अनुक्रमों को अलग माना जाता है यदि कम से कम एक तत्व भिन्न है। उदाहरण के लिए, यदि n=2 और rollMax=[1,1,2,2,2,3], तो आउटपुट 34 होगा। 2 रोल के साथ, बिना प्रतिबंध के 6*6=36 संभावित संयोजन हैं, लेकिन संख्या 1 और 2 अधिकतम एक बार लगातार आ सकते हैं, इसलिए अनुक्रम (1,1) और (2,2) नहीं हो सकते। अंतिम उत्तर 36-2=34 होगा।
हल करने के चरण
- dfs() नामक एक विधि बनाएं, जो dieLeft, last, currLen, सरणी r और मैट्रिक्स dp लेती है
- यदि dieLeft = 0, तो 1 वापस करें
- यदि dp[dieLeft][last][currLen] -1 नहीं है, तो dp[dieLeft][last][currLen] वापस करें
- counter := 0
- i को 0 से 5 तक लूप करें
- यदि i = last और r[i] = currLen, तो अगले इटरेशन पर जाएं
- counter := dfs(dieLeft-1, i, i==last?currLen+1:1, r, dp)
- dp[dieLeft][last][currLen] := counter
- dp[dieLeft][last][currLen] वापस करें
- मुख्य विधि:
- (n+1) x 6 x 16 क्रम का एक 3D सरणी dp बनाएं और इसे -1 से भरें
- dfs(n, 0, 0, rollMax, dp) वापस करें
उदाहरण
#include <bits/stdc++.h> using namespace std; const int mod = 1e9+7; class Solution { public: int dfs(int dieLeft, int last, int currLen, vector <int> &r,vector < vector < vector <int> > > &dp){ if(dieLeft == 0){ return 1; } if(dp[dieLeft][last][currLen]!=-1)return dp[dieLeft][last][currLen]; int counter = 0; for(int i =0;i<6;i++){ if(i==last && r[i] == currLen)continue; counter = (counter%mod + (dfs(dieLeft-1,i,i==last?currLen+1:1,r,dp))%mod)%mod; } dp[dieLeft][last][currLen] = counter%mod; return dp[dieLeft][last][currLen]%mod; } int dieSimulator(int n, vector<int>& rollMax) { vector < vector < vector <int> > > dp(n+1, vector < vector <int> > (6, vector <int>(16, -1))); return dfs(n,0,0,rollMax, dp)%mod; } }; main(){ vector<int> v = {1,1,2,2,2,3}; Solution ob; cout << (ob.dieSimulator(2,v)); }इनपुट
2 [1,1,2,2,2,3]
आउटपुट
34
