मान लीजिए हम कीबोर्ड का उपयोग करके अक्षर 'A' लिखने का प्रयास करेंगे। हमारा लक्ष्य केवल चार कुंजियों का उपयोग करके टेक्स्ट फ़ील्ड पर अधिकतम 'A' लिखना है। कुंजियाँ हैं 'A', 'C', 'V', और 'Ctrl'।
अधिकतम संख्या में A लिखने के लिए, हम Ctrl+A से सभी का चयन करेंगे, Ctrl+C से कॉपी करेंगे, और Ctrl+V से पेस्ट करेंगे।
उदाहरण के लिए, यदि इनपुट कीस्ट्रोक्स की संख्या 7 है तो आउटपुट 9 होगा क्योंकि हम A को तीन बार दबाते हैं। फिर Ctrl+A, Ctrl+C, Ctrl+V, Ctrl+V।
हल करने की विधि
हम डायनामिक प्रोग्रामिंग का उपयोग करेंगे:
- यदि कीस्ट्रोक्स <= 6, तो कीस्ट्रोक्स लौटाएं।
- n = 1 से 6 तक, result[n-1] = n।
- n = 7 से कीस्ट्रोक्स तक:
- result[n-1] = 0।
- ब्रेकपॉइंट = n-3 से 1 तक घटते क्रम में:
- curr = (n - ब्रेकपॉइंट - 1) * result[ब्रेकपॉइंट - 1]।
- यदि curr > result[n-1], तो अपडेट करें।
- result[कीस्ट्रोक्स - 1] लौटाएं।
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#include<iostream> using namespace std; int keyNumbers(int keystrokes){ //find number of 'A's using 4 types of keys if (keystrokes <= 6) //if keystrokes are less than 7 return keystrokes; int result[keystrokes]; //store intermediate results for (int n=1; n<=6; n++) //upto 6 keystrokes, we need that number of keystrokes for max result[n-1] = n; for (int n=7; n<=keystrokes; n++){ //for 7th to higher result[n-1] = 0; //initially store 0 as result for (int breakPoint=n-3; breakPoint>=1; breakPoint--){ //find breakpoint to select, copy and paste int curr = (n-breakPoint-1)*result[breakPoint-1]; if (curr > result[n-1]) result[n-1] = curr; } } return result[keystrokes-1]; } int main(){ int keystrokes; cout << "Enter Number of keystrokes: "; cin >> keystrokes; cout << "Maximum Number of A's with "<<keystrokes << " keystrokes is: "<< keyNumbers(keystrokes)<<endl; }
इनपुट
7
आउटपुट
Enter Number of keystrokes: Maximum Number of A's with 0 keystrokes is: 0
