Minimum Time to Display N Character
You need to display N similar characters on a screen. You are allowed to do three types of operation each time.
- You can insert a character,
- You can delete the last character
- You can copy and paste all displayed characters. After copy operation count of total written character will become twice.
All the operations are assigned different times.
- Time for insertion is X
- Time for deletion is Y
- Time for copy, paste is Z
You need to output minimum time to display N characters on the screen using these operations.
Input:
The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case contains an integer N denoting the number of same characters to write on the screen. The next line contains time for insertion, deletion, and copying respectively.
Output:
Print the minimum time to display N characters on the screen.
Constraints:
1 <= T <= 100
1 <= N <= 100
1 <= X, Y, Z <= N
Example:
Input:
Test case: 2
First test case,
N, number of characters to be displayed = 9
Value of X, Y, Z respectively,
1 2 1
N, number of characters to be displayed = 10
Value of X, Y, Z respectively,
2 5 4
Output:
minimum time for first test case: 5
minimum time for second test case: 14
Explanation:
For the first test case no of character to be displayed is: 9
Time for insertion is 1
Time for deletion is 2
Time for copy paste is 1
Say the similar character is 'a'
So the best way is
Insert two character
Time is 2
Copy paste
Total character so far is 4
Total time 3
Copy paste again
Total character so far is 8
Total time 4
Insert gain
Total character so far is 9
Total time 5
This is the most optimum way we can solve this
This is a recursive problem
And we have a few possibilities,
Now we need to understand the optimal option based on the situation
Say a situation where we need to reach character 13 and we are at character 7 displayed already
Also, Cost of Inserting 6 digits is much higher than one-time copy paste and deleting ( just consider this case, it may not happen always if copy paste option is costly)
So, the question is when the "delete" options is useful
It's useful for such case what I mentioned. So if we formulate the recursion
Say,
N = number of characters to be displayed.
So, if n is odd only then we need deletion if n is we even don't need that.
Now, we have our recursion, so we can write the recursive function. Since there will be many overlapping sub-problems, we can wither use top-down DP or bottom-up DP. I have used memoization in my implementation. As an exercise, you should be able to convert the above recursion to tabulation DP.
C++ Implementation:
Output:
need an explanation for this answer? contact us directly to get an explanation for this answer