Input File: fashin.txt
Output File: fashout.txt
Time Limit: 1 second
In the latest trend of skin-tight jeans and slimline handbags, having a bulging wallet or purse is simply a fashion crime. You are faced with a dilemma: either you find yourself disowned by your fashion-conscious friends, or risk carrying too little money for your taxi ride home.
You wish to carry the exact amount of money for your taxi ride (in case you are mugged or otherwise lose it). However, you also wish to use as few notes as possible to avoid being ridiculed by your friends. The notes available to you come in denominations of $1, $5, $20 and $100 (you never carry coins, which are simply far too bulky).
For example, if your taxi fare costs $67, the smallest number of notes you can carry is six — this is achieved by carrying three $20 notes, one $5 note and two $1 notes (20+20+20+5+1+1 = 67).
Your task is to determine the smallest number of notes you need to carry in order to make up a given taxi fare.
The input will consist of a single line containing the integer t, the cost of your taxi ride home. It is guaranteed that 0 <= t <= 1,000,000.
Your output should consist of a single integer the fewest number of notes required to make up your taxi fare.
The score for each input file will be 100% if the correct answer is written to the output file and 0% otherwise.