New Zealand currency consists of $100, $50, $20, $10, and $5 notes and $2, $1, 50c, 20c, 10c and 5c coins. Write a program that will determine, for any given amount, in how many ways that amount may be made up. Changing the order of listing does not increase the count. Thus 20c may be made up in 4 ways: 1 20c, 2 10c, 10c+2 5c, and 4 5c.

Input

Input will consist of a series of real numbers no greater than $50.00 each on a separate line. Each amount will be valid, that is will be a multiple of 5c. The file will be terminated by a line containing zero (0.00).

Output

Output will consist of a line for each of the amounts in the input, each line consisting of the amount of money (with two decimal places and right justified in a field of width 5), followed by the number of ways in which that amount may be made up, right justified in a field of width 12.

Sample input

0.20
2.00
0.00

Sample output

0.20           4
2.00         293

典型的动态规划问题：

可以先考虑只有n-1种硬币，V1,V2,V3,---Vn-1.设凑成总值为M的方法数为result[M];

现在又添加一种面值为Vn的硬币。

则咱们需要修改一些值，修改那些大于等于Vn的result[],不妨设M大于vn。

新result[M]=原result[M]+result[M-Vn]+result[M-2*Vn]+----直到M-p*Vn<=0;（1）

实际上如果如(2)那样处理 从大于等于Vn的result[]开始处理的话，从小到大，设Vn=M-p*Vn;

则result[M-p*Vn]第一个最先更新，result[M-p*Vn]+=result[M-p*Vn -Vn]   见(2)
随后更新result[M-(p-1)*vn]，则只需直接加上result[M-p*Vn]的值，无需如（1）式那样  累加。

用程序表达就是

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

for(i=1;i<10;i++)

 for(j=coin[i];j<=50000;j+=5)

     result[j]+=result[j-Coin[i]];   (2) //

-------------

还有一个注意点，见牛人博客，http://hi.baidu.com/piaoshi111/blog/item/9a6de84a00a6e5f882025c89.html

就是浮点数的四舍五入，

1.5，浮点数可能表为1.4999999，所以乘以100时转化为整型是149，应当注意。