Four Keys Keyboard

Key 1: (A): Print one ‘A’ on screen. Key 2: (Ctrl-A): Select the whole screen. Key 3: (Ctrl-C): Copy selection to buffer. Key 4: (Ctrl-V): Print buffer on screen appending it after what has already been printed.

The first line of input contains an integer ‘T’ denoting the number of test cases. The next ‘T’ lines represent the ‘T’ test cases. The first and only line of each test case contains a positive integer ‘N’, representing the number of times you can press the keys of the keyboard.

Test case 1: We can at most get 3 A's on the screen by pressing the following key sequence: A, A, A Test case 2: We can at most get 9 A's on the screen by pressing the following key sequence: A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V as mentioned below Press Key(A), Screen will have “A” Press Key(A) again, Screen will have “AA” Press Key(A) again, Screen will have “AAA” Press Key(Ctrl-A), This will select all three A’s which are printed on the screen. Press Key(Ctrl-C), This will copy all three A’s in the buffer. Press Key(Ctrl-V), It appends 3 ‘A’s from the buffer on screen, So the screen will now have “AAAAAA”. Press Key(Ctrl-V), It appends 3 ‘A’s from the buffer on screen, So the screen will now have “AAAAAAAAA”.

Test case 1: We can at most get 27 A's on the screen by pressing the following key sequence. A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V Test case 2: We can at most get 1 ‘A’ on the screen by pressing key ‘A’ once.

Recursion

Approach: We can observe that if ‘n’ < 7, the output is ‘n’ itself. Otherwise, if ‘n’ is greater than or equal to 7, then the optimal sequence of operations will end with a suffix of one Ctrl-A, one Ctrl-C, followed by one or several Ctrl-V’s.

If F(n) given the maximum number of ‘A’s that can be printed by ‘n’ keystrokes and ‘x’ represent the number of Ctrl-V’s at the end, then recurrence relation should be-:

F(n) = n if n < 7;

F(n) = maximum of all (x+1)*F(n-x-2), where ‘x’ ranges from 1 to n-3. Here, we try for all possible points from where the suffix may start.

This approach's algorithm can be implemented as follows.

This is a recursive approach.
If ‘N’ is smaller than 7, return ‘N’.
Otherwise, Initialize an integer variable ‘RESULT’: = 0.
Run a loop where ‘i’ ranges from 1 to ‘N’ - 3. And for each ‘i’ recursively find the maximum number of ‘A’s that can be printed in ‘N - i - 2’ keystrokes and update ‘RESULT’ with a maximum of its current value and product of value returned by a recursive call with (i + 1).
Return ‘RESULT’.

Time Complexity

O(N!), where ‘N’ is the integer representing the number of times you can press the keys of a keyboard.

In the first step, we make N-3 recursive calls, in the second step we make N-3 recursive calls for each of the previous calls and so on. We can upper bound the number of such recursive calls to N!. Note, that we can also find a tighter bound.

Space Complexity

O(N), where ‘N’ is the integer representing the number of times you can press the keys of a keyboard.

The recursion depth will be of the order of (N).

Problem statement

Sample Input 1:

Sample Output 1:

Explanation For Sample Input 1:

Sample Input 2:

Sample Output 2:

Explanation For Sample Input 2: