मान लीजिए हमारे पास एक धनात्मक पूर्णांक n है, हमें लंबाई n के सभी संभावित उपस्थिति रिकॉर्ड की संख्या ज्ञात करनी है, जिन्हें पुरस्कार योग्य (rewardable) माना जाएगा। चूंकि उत्तर बहुत बड़ा हो सकता है, हम इसे मॉड 10^9 + 7 का उपयोग करके वापस करेंगे।
छात्र उपस्थिति रिकॉर्ड में स्ट्रिंग में केवल निम्न तीन वर्ण हो सकते हैं -
- 'A' का अर्थ अनुपस्थित (absent) है।
- 'L' का अर्थ देर से (late) है।
- 'P' का अर्थ उपस्थित (present) है।
एक उपस्थिति को पुरस्कार योग्य माना जाता है यदि इसमें एक से अधिक 'A' (अनुपस्थित) या दो से अधिक लगातार 'L' (देर से) नहीं हैं। तो हमें अधिकतम अंक ज्ञात करने हैं।
यदि इनपुट 2 जैसा है, तो आउटपुट 8 होगा, क्योंकि हम 8 संभावित तरीके उत्पन्न कर सकते हैं जिन्हें पुरस्कृत किया जा सकता है, ये हैं [PP, AP, PA, LP, PL, AL, LA, LL], केवल AA नहीं होगा।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे -
- एक फंक्शन add() परिभाषित करें, यह a, b लेगा,
- वापस करें ((a mod m) + (b mod m)) mod m
- मुख्य विधि से, निम्न करें,
- आकार n + 1 का एक ऐरे p, आकार n + 1 का एक ऐरे a, आकार n + 1 का एक ऐरे l, आकार n + 1 का एक ऐरे ap और आकार n + 1 का एक ऐरे al परिभाषित करें
- यदि n, 1 के समान है, तो -
- 3 वापस करें
- p[0] := 1, p[1] := 1, p[2] := 3
- a[0] := 1, a[1] := 1, a[2] := 2
- l[0] := 1, l[1] := 1, l[2] := 3
- ap[0] := 1, ap[1] := 1, ap[2] := 2
- al[0] := 1, al[1] := 1, al[2] := 2
- i := 3 से प्रारंभ करें, जब i <= n, i बढ़ाते हुए, करें -
- p[i] := add(add(p[i - 1], a[i - 1]), l[i - 1])
- l[i] := add(add(p[i - 1], p[i - 2]), add(a[i - 1], a[i - 2]))
- a[i] := add(al[i - 1], ap[i - 1])
- al[i] := add(ap[i - 1], ap[i - 2])
- ap[i] := add(ap[i - 1], al[i - 1])
- add(add(p[n], l[n]), a[n]) वापस करें
बेहतर समझ के लिए निम्न कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h> using namespace std; typedef long long int lli; const lli m = 1e9 + 7; class Solution { public: lli add(lli a, lli b){ return ( (a % m) + (b % m) ) % m; } int checkRecord(int n) { vector <int> p(n+1), a(n+1), l(n+1), ap(n+1), al(n+1); if(n == 1)return 3; p[0] = 1; p[1] = 1; p[2] = 3; a[0] = 1; a[1] = 1; a[2] = 2; l[0] = 1; l[1] = 1; l[2] = 3; ap[0] = 1; ap[1] = 1; ap[2] = 2; al[0] = 1; al[1] = 1; al[2] = 2; for(int i = 3; i <= n; i++){ p[i] = add(add(p[i-1], a[i-1]), l[i-1]); l[i] = add(add(p[i-1], p[i-2]),add(a[i-1] , a[i-2])); a[i] = add(al[i-1], ap[i-1]); al[i] = add(ap[i-1], ap[i-2]); ap[i] = add(ap[i-1], al[i-1]); } return add(add(p[n], l[n]), a[n]); } }; main(){ Solution ob; cout << (ob.checkRecord(3)); }इनपुट
3
आउटपुट
19