Print maximum number of A’s using given four keys

Problem Statement

You are given following four keys on a keyboard:

1. Print A (print a single character A)
2. Ctrl-A (Select All)
3. Ctrl-C (Copy selected content)
4. Ctrl-V (Append the selected content right next to already printed content)

If you can only press the keyboard for N times (with the above four keys), write a program to produce maximum numbers of A’s i.e. the input parameter is N (number of keys that you can press), the  output is M (number of A’s that you can produce).

Solution

The basic idea is that once we have a combination of Ctrl-A, Ctrl-C and Ctrl-V, we can reuse Ctrl-V repeatedly to append the same copied content again and again. Thus with every extra Ctrl-V, we are adding as many A’s that are there in the copied buffer with a single keystroke. For example, for N = 7, the first few keystrokes are – Print A, Print A, Print A, Ctrl-A, Ctrl-C, Ctrl-V. After this sequence of 6 keystroke, we have 6 A’s in the output with 3 A’s still in the copied buffer. Now, with just one more keystroke of Ctrl-V, we can append 3 more characters to the output making it 9 A’s. Let us look at an example to explain it better (N = 10):

1. 1 Print A, Ctrl-A, Ctrl-C, Ctrl-V, another 6 Ctrl-V => 8 A’s
2. 2 Print A, Ctrl-A, Ctrl-C, Ctrl-V, another 5 Ctrl-V => 14 A’s
3. 3 Print A, Ctrl-A, Ctrl-C, Ctrl-V, another 4 Ctrl-V => 18 A’s
4. 4 Print A, Ctrl-A, Ctrl-C, Ctrl-V, another 3 Ctrl-V => 20 A’s
5. 5 Print A, Ctrl-A, Ctrl-C, Ctrl-V, another 2 Ctrl-V => 20 A’s
6. 6 Print A, Ctrl-A, Ctrl-C, Ctrl-V, another 1 Ctrl-V => 18 A’s
7. 7 Print A, Ctrl-A, Ctrl-C, Ctrl-V  => 14 A’s
8. 8 Print A, after this no other option than to press Print A twice => 10 A’s
9. 9 Print A, after this no other option than to press Print A once more => 10 A’s
10. 10 Print A => 10 A’s

From above example, there is no sure method to tell us whether we have to maximize ‘Print A’ or ‘Ctrl-V’, only option is to try out all the combinations recursively. Also while we are trying out all the solutions, for N = 10, we need not consider 8, 9, and 10 from the above example, since they all lead us to the same result of printing all A’s as we cannot use the full combination of (Ctrl-A, Ctrl-C, Ctrl-V) which requires 3 keystrokes. So, for each N we need to start our search from N-3 down to 1. For inputs N = 1 to N = 6, the maximum is N itself. The recurrence relation can formally be stated as:

F(N) = MAX(F(j) * (N – j -1)) where N-3 <= j <= 1