Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में छात्र उपस्थिति रिकॉर्ड II (Student Attendance Record II)


मान लीजिए हमारे पास एक धनात्मक पूर्णांक 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

  1. - C++ में मितव्ययी संख्या (Frugal Number)

    इस समस्या में, हमें एक धनात्मक पूर्णांक N दिया गया है। हमारा कार्य यह जांचने के लिए एक प्रोग्राम बनाना है कि दी गई संख्या मितव्ययी संख्या है या नहीं। मितव्ययी संख्या (FRUGAL NUMBER) − एक संख्या जिसके अंकों की संख्या उस संख्या के अभाज्य गुणनखंडन में अंकों की संख्या से सख्ती से अधिक है। उदाहरण &

  1. C++ में पेंटाटोप संख्या C++ में पेंटाटोप संख्या

    एक पेंटाटोप संख्या को पास्कल के त्रिभुज में पांचवीं संख्या के रूप में वर्णित किया गया है। अब, चूंकि यह पांचवीं संख्या है, इसका मतलब है कि पास्कल के त्रिभुज में कम से कम पांच संख्याएं होनी चाहिए, इसलिए इस श्रृंखला की पहली संख्या 1 4 6 4 1 से शुरू होती है जो पास्कल के त्रिभुज की चौथी पंक्ति है। तो, इस

  1. HP प्रिंटर सेटअप कैसे करें - चरण-दर-चरण पूर्ण गाइड HP प्रिंटर सेटअप कैसे करें - चरण-दर-चरण पूर्ण गाइड

    HP प्रिंटर की पहली बार स्थापना आधुनिक दुनिया में हमें किताबें, जर्नल लेख, शोध सामग्री, पावरपॉइंट स्लाइड आदि कंप्यूटर, मेमोरी कार्ड, वेबसाइट, USB स्टोरेज से प्रिंट करने की आवश्यकता होती है। प्रिंटर वह उपकरण है जो इलेक्ट्रॉनिक रूप से भौतिक कागज पर प्रिंट करता है। HP जैसी प्रसिद्ध कंपनियां इस बढ़ती मां