All submissions for this problem are available.
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.
Assuming you have a sufficient supply of coins of each of the types you will need.
The first line of input specifies the number of test cases t followed by t lines.(1<=t<=20)
Each test case contains the value of cost c between 1 and 10^15, inclusive.
Output the smallest number of coins necessary to pay exactly the cost of the car.
Input 3 47 9 76540123
OutPut5 9 16 For the first test case the best way to pay 47 is 25+10+10+1+1. For the second test case, to pay 9 we can only use nine coins worth 1 each. 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
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.4, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.