Hi. I am trying to solve this problem.

For convenience, I have replicated the problem statement below:

A person is on floor N of a building. He has to take the lift down to floor 0. To use the lift exactly once, one token is needed. This lift is special as it can only travel downwards for one of the following levels each time it is used:

1, 5, 10, 17, 50, 100, 500, 1000, 5000, 10000

For example, if the person is standing on floor 6, one way to reach floor 0 is to take the lift down 5 floors, then take the lift again to go down 1 more floor (6 - 5 - 1 = 0). 2 tokens are used in this case.

The objective is to find the minimum number of tokens that the person needs to use to reach floor 0 from a given floor N. For the above example, the answer is 2.

My analysis:

This problem looks exactly like the classical coin change problem where we want to find the minimum number of coins to make up a given value. The latter problem can be easily solved using DP or BFS (or maybe matrix exponentiation?). Applying the same methods on this problem could earn us the points for all except the last subtask where N ≤ 1e9.

Could someone please advise me on a solution that would solve this problem in its entirety?