#634 · Recursion and backtracking · Advanced · Fast enough · 125 XP · about 22 min
In a small kingdom the bank exchanges a gold coin stamped with a number n for three new coins stamped n // 2, n // 3 and n // 4 (each rounded down). The new coins can be exchanged again, as often as you like. A merchant buys any coin for exactly the number stamped on it.
Write best_value(n) that returns the most money you can end up with, starting from one coin stamped n.
best_value(12) # returns 13 best_value(2) # returns 2 best_value(24) # returns 27
Exchanging 12 gives coins of 6, 4 and 3, which sell for 13 in all, and none of them is worth exchanging again. Exchanging 2 gives coins of 1, 0 and 0, so selling it as it is pays more. For 24 the exchange gives 12, 8 and 6, and the 12 is worth exchanging again: 13 + 8 + 6 = 27.
0 <= n <= 10^15Each test must finish within 10 seconds, and the hidden tests use coins stamped up to 10^15.
First solves only, ranked by stars and then time.