Special Keyboard
Imagine you have a special keyboard with four types of keys:
Key 1: Prints 'I' on screen
Key 2: Select whatever printed in screen
Key 3: Copy selection to buffer
Key 4: Append buffer on-screen after what has already been printed. If you can only press the keyboard for N times (with the above four keys), write a program to produce maximum numbers of I's possible to be printed on the screen.
Input:
Input is N, number of times keys can be pressed in total.
Output:
Print maximum number of I's possible to print
Constraints:
1 ≤ N ≤ 75
Example:
Input:
2
Output:
2
Explanation:
We can at most get 2 I's on screen by pressing
following key sequence Key1, key1.
Pressing other keys have no effect.
Like key 1, key2 will produce only one I on screen.
Input:
7
Output:
9
Explanation:
We can at most get 9 I's on screen by pressing
following key sequence.
Key1, Key1, Key1, Key2, Key3, key4, Key4
I //after pressing key1
I I //again pressing key 1
I I I //again pressing key1
I I I //pressing key2 selects three I's
I I I // pressing key3 copies these three I's to buffer
I I I I I I // pressing key4 appends these three I's
I I I I I I I I I // pressing key4 again appends these three I's
Basically,
Two things need to be understood to solve this problem
Key4 appends whatever is printed already on screen before 3 key pressing
That means at moment 4,
You can append whatever was printed while moment 1 as to print in moment 4, you need to press key2 at moment 2 and key3 at moment 3.
So, the recursive function can be written as
Let,
F(n) = max number of I’s printed on screen
So, for n>3
So, now we need to convert the recursion into DP.
C++ Implementation:
Output:
need an explanation for this answer? contact us directly to get an explanation for this answer