Problem 44787. What can you get for exactly amount of money(harder)
Because memory, some solution will not be allowed.
This problem merely requires a fast search heuristic that works only for the given test cases but not necessarily for the general case. For instance, the accepted solutions here will not pass for v = (1:50)+1e8 and s = 1e10+19. Also, the memory limit would be exceeded for v = 1:50 and s = 1e10+19.
The tip here is that numbers must be the same order of magnitude. For instance, if I have to add the integers 6 and 4 until they add to 1e20, it will take forever. However, the numbers 6e19 and 4e19 (multiples of 6 and 4) will find the sum 1e20 with one iteration.
And, I don't agree with Karl, my code finds a solution for v=1:50 and s=1e10+19 within 4 seconds. And for v = 1:50+1e8 within 12 seconds (at an i5-3230M CPU @ 2.60GHz). I am not sure there is a solution for (1:50)+1e8. It seems unlikely since 19 will be hard to appear from a magnitude of 1e8 within the range of s=1e10+19. In order words, we are trying to find the prime number 10000000019, and the smallest number that we are adding is 100000001 from (1:50)+1e8. If we add 100000001 one hundred times, the smallest number with the same order of 10000000019 is 10000000100.
Apparently, my solution worked faster when I sorted the vector "v" in descending order before doing anything else. Thanks Rafael S.T. Vieira. Now, I can find a solution for v=1:50 and s=1e10+19 within a few seconds as well.
Problem Recent Solvers9
Find perfect placement of non-rotating dominoes (easier)
More from this Author4
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!Start Hunting!