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

misof

Testers:

PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Brute Force, Dynamic Programming, Greedy, Recursion