# 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