AnotherCoinProblem | Topcoder Archive

Problem Statement

The monetary system in Absurdistan is really simple and systematic. The locals only use coins. The coins come in different values. The values used are:

1, 10, 25, 100, 1000, 2500, 10000, 100000, 250000, 1000000, ...

Formally, for each K>=0 there are coins worth 10^K, and coins worth 25*100^K.

You want to buy a new car. Its price is cost. Write a method that will return the smallest number of coins necessary to pay exactly the cost of the car (assuming you have a sufficient supply of coins of each of the types you will need).

Definition

Class:: AnotherCoinProblem
Method:: minimumCoins
Parameters:: long
Returns:: int
Method signature:: int minimumCoins(long cost)
(be sure your method is public)

Constraints

cost will be between 1 and 10^15, inclusive.

Examples

```
47
```
```
Returns: 5
```
The best way to pay 47 is 25+10+10+1+1.
```
9
```
```
Returns: 9
```
To pay 9, we can only use nine coins worth 1 each.
```
250111
```
```
Returns: 4
```
```
76540123
```
```
Returns: 16
```
3*25,000,000 + 1*1,000,000 + 2*250,000 + 4*10,000 + 1*100 + 2*10 + 3*1 = 76,540,123 3 + 1 + 2 + 4 + 1 + 2 + 3 = 16

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.