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.
Solution CommentsShow comments
Problem Recent Solvers10
More from this Author4
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!Start Hunting!