标签归档:扫描线

AIO2006 Solution

Fashion Statement

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.

继续阅读