Hello everyone, could you give me any idea about this problem? Thanks a lot.
We have 2 arrays x[ ], y[ ] size n and an integer m. We can do 2 operations:
1- Multiply all x[ ] by a (a <= m). (x[i] = x[i] * a, i = 1-> n, 2 <= a <= m)
2- Decrease arbitrary x[i] by 1. (x[i] = x[i] — 1, only one value i per operation)
Find the minimum number of operations to transform x[ ] to y[ ].
Constrain: n <= 5000, m <= 1000. 0 <= x[ ], y[ ] <= 1000.
Example:
Input:
n = 2, m = 5.
x[ ] = (3, 5)
y[ ] = (8, 15)
Output:
2
Note:
(3, 5) -> (9, 15) (1st operation, a = 3) -> (8, 15) (2nd operation, i = 1).
Sorry for my bad English :(