Editor

The Coin-Splitting Bank

#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.

Examples

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.

Constraints

  • 0 <= n <= 10^15
  • A coin stamped 0 is worth nothing.

Time limit

Each test must finish within 10 seconds, and the hidden tests use coins stamped up to 10^15.

Fastest solvers

Leaderboard

First solves only, ranked by stars and then time.