Q147 - Dollars

HSCHE

紐西蘭的貨幣包含了 $100, $50, $20, $10,  $5 的紙鈔和 $2, $1, 50c, 20c, 10c, 5c 的硬幣。給你某金額的數字，請你寫一個程式回答：使用這些面額的紙鈔或硬幣，有多少種不同的方法可以組合成這個金額。例如：20c 可以有4個方法可以得到：（改變金額的順序不會增加方法數，例如 2 * 5c + 1 * 10c 和下面第3種方法視為同一種）

• 1 * 20c
• 2 * 10c
• 1* 10c + 2 * 5c
• 4 * 5c
  

Input

輸入含有多組測試資料。

每組測試資料一列，含有 1 個金額（不大於  $300.00）。這個金額一定是合法的，也就是一定是 5c 的倍數。

當輸入為  0.00 時代表輸入結束，請參考Sample Input。

Output

對每組測試資料輸出一列 ，包含輸入的金額（小數點2位，總長度6位，靠右對齊）以及有多少種不同的方法可以組合成這個金額（總長度17位，靠右對齊）。請參考 Sample Output。

Sample Input	Sample Output
0.202.000.501.00100.95300.000.00	0.20                4  2.00              293  0.50               13  1.00               50100.95      50619764500300.00  181490736388615

在此附上題目連結

UVA:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=83

LUCKY CAT:http://luckycat.kshs.kh.edu.tw/homework/q147.htm

解題感想:這題難易中偏高，須注意服點誤差和輸出格式，其他就自己加油啦！！

ＡＣ　ＣＯＤＥ：

#include<iostream>

#include<cmath>

#include<cstdio>

#include<vector>

using namespace std;

int item[]={10000,5000,2000,1000,500,200,100,50,20,10,5};

double a;

long long int x[60000];

long long *method=x+25000;

long long int aaa,ans;

int main()

{

    method[0]=1;

    for(int i=0;i<11;i++)

    {

            for(int y=item[i];y<=30000;y+=5)

            {

                    method[y]+=method[y-item[i]];        

            }

    }

    int aa,bb;

    while(~scanf("%d.%d",&aa,&bb))

    {

            a=aa+bb/100.0;

            if(a<0.0001)break;

            printf("%6.2f%17lld\n",a,method[aa*100+bb]);

    }

    return 0;

}