# p147 dollars
某國家有貨幣種類：100元、50元、20元、10元、 5元、 2元、 1元、50分、20分、10分和5分（0.05元）。
寫一支程式找出輸入金額的所有貨幣組合可能，順序不影響組合。例如20分有四種方法：1×20分、2×10分、10分+2×5分 和 4×5分。
## 輸入
輸入為最大300.00元的實數金額，每行一個金額。金額必定被五分整除。當輸入0時，程式結束。
## 輸出
輸出對應每行輸入的金額，每行的輸出首先為金額（精度為小數點下兩位，寬6個字元，靠右對齊），再來是該金額的可能組合數（整數，寬17個字元，靠右對齊）。
### python輸出範例

print("{:6.2f}{:17d}".format(金額,組合數))

### C++輸出範例

std::cout << std::setw( 6 ) << std::fixed << std::setprecision(2)<< double(金額) ;
std::cout << std::setw( 17 )<< 組合數 << std::endl;

## python解答

COIN_TYPE = [1,2,4,10,20,40,100,200,400,1000,2000]
NUM_COIN_TYPE = len(COIN_TYPE)
def findMaxCoin(num):
    #num>=1
    for key, coin in enumerate(COIN_TYPE):
        if coin==num:
            return key
        elif coin>num:
            return key-1
    return key
def getCombinationList(num, table):
    max_coin_idx = findMaxCoin(num)
    count = 0
    combination_table = [1]*NUM_COIN_TYPE
    for key, coin in enumerate(COIN_TYPE):
        if coin==1:#COIN_TYPE[0]
            count+=1
        elif coin==2:#COIN_TYPE[1]
            count+=num//2
        elif key<=max_coin_idx:#key>=2
            if coin==num:
                count+=1
                combination_table[key]=count
                continue
            for rest in range(num % coin, num, coin):
                count+=table[rest][key-1] if rest!=0 else 1
        combination_table[key]=count
    #if(num>2000):
    #    print(combination_table)
    return combination_table, count

def findCombinationOf(num):
    table=[]
    for i in range(num):
        if i<=1:
            table.append([1]*NUM_COIN_TYPE)
        else:
            combination_table, _ = getCombinationList(i,table)
            table.append(combination_table)
    _, count = getCombinationList(num,table)
    return count

def getCombinationListUnder(num):
    table=[]
    countList=[]
    for i in range(num):
        if i<=1:
            table.append([1]*NUM_COIN_TYPE)
            countList.append(1)
        else:
            combination_table, count = getCombinationList(i,table)
            countList.append(count)
            table.append(combination_table)
    _, count = getCombinationList(num,table)
    countList.append(count)
    #print(combination_table)
    return countList

def main():
    countList = getCombinationListUnder(6000)
    while True:
        num = input()
        num = float(num)
        idx = round(num/.05)
        if idx==0:
            break
        print("{:6.2f}{:17d}".format(num,countList[idx]))
def mainWrite():
    countList = getCombinationListUnder(6000)
    path = './Uva_p147_dollar.txt'
    with open(path, 'w') as f:
        while True:
            num = input()
            num = float(num)
            idx = round(num/.05)
            if idx==0:
                break
            print("{:6.2f}{:17d}".format(num,countList[idx]), file=f)

if __name__ == '__main__':
    main()