StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I don't think you need dynamic programming, just do the following:</p> <ul> <li>Pick as many of the digit that costs the least as you can afford.</li> <li>Now you have a number (consisting of only 1 type of digit).</li> <li>Replace the first digit with the greatest possible digit that you can afford</li> <li>If you have money left, do the same for the second, and the third and so on, until you run out of money.</li> </ul> <p><strong>Why this works:</strong></p> <p>Consider that <code>11111</code> > <code>9999</code> and <code>91111</code> > <code>88888</code>, or, in words, it's best to:</p> <ul> <li>Pick as many digits as possible, which is done by picking the cheapest digits.</li> <li>Then replace these digits, from the left, with the highest valued digit you can afford (this is always better than picking a few more expensive digits to start).</li> </ul> <p><strong>Optimization:</strong></p> <p>To do this efficiently, discard any digits that cost more than a bigger digit: (because it's never a good idea to pick that one instead of a cheaper digit with a bigger value)</p> <pre><code>Given: 9, 11, 1, 12, 5, 8, 9, 10, 6 Removing all those where I put an X: X, X, 1, X, 5, X, X, X, 6 So: 1, 5, 6 </code></pre> <p>Now you can just do binary search on it (just remember which digit which value came from) (although, for only 9 digits, binary search doesn't really do wonders for the already-minor running time).</p> <p><strong>Running time:</strong></p> <p><code>O(n)</code> (with or without the optimization, since 9 is constant)</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload