Maximum number of A’s using four keys

Program to print maximum number of A’s using four keys is discussed here. 

DESCRIPTION:

You are given a task to print maximum As with the given number of keystroke. There are four keys you use

  1. You can directly press A.
  2. You can select all the A that has been printed till now using the select all key. (Ctrl + A)
  3. You can copy the selected text. (Ctrl + C)
  4. You can paste the copied text. (Ctr + V)
  5. Now, once copied, you can paste it any number of time but each time it will take one keystroke.

For example,

Sample Input: 7 (Number of times we can press the key)

Sample Output: 9

Explanation:

A   A   A   Ctrl+A   Ctrl+C   Ctrl+V   Ctrl+V

By following this sequence, A can be printed 9 times.

Algorithm to print maximum number of A,s using four keys

  • Input N, number of times the key can be used.
  • For N <= 6, return N as the maximum value.
  • For N > 6, try all combinations and store the value in a temporary variable.
  • Keep updating the temporary variable until all combinations have been applied.
  • Print the temporary variable.

Program to print the maximum number of A’s using the given keys is given below.

/* C++ program to print the maximum number of A’s using the given keys */

#include<iostream>
using namespace std;
int main()
{
   int n;
   cin>>n;
   long int dp[n];
   for(int i=1;i<=6;i++)
   {
       dp[i-1]=i;
   }
   for(int i=7;i<=n;i++)
   {
       dp[n-1]=0;
       for(int b=i-3;b>=1;b–)
       {
           int temp=(i-b-1)*dp[b-1];
           if(temp > dp[i-1])
               dp[i-1]=temp;
       }
   }
   cout<<dp[n-1];
}

Tab Content

Test Case 1

I/P
8
O/P
12

Test Case 2

I/P
20
O/P
324

Test Case 3

I/P
50
O/P
1327104

Test Case 4

I/P
100
O/P
1946157056

Test Case 5

I/P
67
O/P
150994944