C++ . में छात्र उपस्थिति रिकॉर्ड II

मान लीजिए कि हमारे पास एक धनात्मक पूर्णांक n है, हमें लंबाई n के साथ सभी संभावित उपस्थिति रिकॉर्डों की संख्या ज्ञात करनी है, जिन्हें पुरस्कृत माना जाएगा। चूंकि उत्तर बहुत बड़ा हो सकता है, हम इसे मॉड 109 + 7 का उपयोग करके वापस कर देंगे।

छात्र उपस्थिति रिकॉर्ड में स्ट्रिंग में केवल निम्नलिखित तीन वर्ण हो सकते हैं -

'ए' का अर्थ है अनुपस्थित।
'L' का मतलब देर से होता है।
'P' का अर्थ है उपस्थित।

एक उपस्थिति को पुरस्कृत माना जाता है यदि इसमें एक से अधिक 'ए' (अनुपस्थित) या दो से अधिक निरंतर 'एल' (देर से) शामिल नहीं हैं। इसलिए हमें अधिकतम अंक खोजने होंगे।

यदि इनपुट 2 की तरह है, तो आउटपुट 8 होगा, क्योंकि हम 8 संभावित तरीके उत्पन्न कर सकते हैं जिन्हें पुरस्कृत किया जा सकता है, ये हैं [पीपी, एपी, पीए, एलपी, पीएल, एएल, एलए, एलएल], केवल एए नहीं होगा वहाँ रहो।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

एक फ़ंक्शन ऐड () को परिभाषित करें, इसमें a, b,
- वापसी ((एक मॉड एम) + (बी मॉड एम)) मॉड एम
मुख्य विधि से, निम्न कार्य करें,
आकार n + 1 के एक सरणी p को परिभाषित करें, n + 1 आकार की सरणी a, n + 1 आकार की एक सरणी l, आकार n + 1 की एक सरणी एपी और आकार n + 1 की एक सरणी
यदि 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
एपी[0]:=1, एपी[1]:=1, एपी[2]:=2
al[0] :=1, al[1] :=1, al[2] :=2
इनिशियलाइज़ i :=3 के लिए, जब i <=n, अपडेट करें (i को 1 से बढ़ाएँ), −
- 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])
रिटर्न ऐड(जोड़ें(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));
}