TopCoder problem "AnotherCoinProblem" used in TCHS09 Round 3 (Division I Level Two)



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 10K, and coins worth 25*100K.

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

0)
    
47
Returns: 5
The best way to pay 47 is 25+10+10+1+1.
1)
    
9
Returns: 9
To pay 9, we can only use nine coins worth 1 each.
2)
    
250111
Returns: 4
3)
    
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

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10285

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13730&pm=10285

Writer:

misof

Testers:

PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Brute Force, Dynamic Programming, Greedy, Recursion