牛奶容器

2013年12月19日3,2573

来源：http://218.5.5.242:9018/JudgeOnline/problem.php?id=1146

题目描述

农民保罗有如下型号的牛奶容器: 10加伦，2加伦，1 加伦，1/4加伦，1/8加伦， 1/16加伦。
请您帮他编写一个程序，能计算保罗用这些容器取X加伦牛奶共有多少不同方法。在所有的数据中，X都是整数且(1<=X<=100)。

输入

输入数据中有多组测试数据，每组测试数组仅有一行，包含一个整数x。最后一行以0表示结束。

输出

对于每组数据，输出一行，为保罗用这些容器取X加伦牛奶共有的不同方法数。

样例输入

5 10 0

样例输出

1308 12477

代码

#include<iostream>
#include<cstring>
int f[1601],x;
int a[7]={0,1,2,4,16,32,160};
using namespace std;
int main()
{
    while(cin>>x)
    {
        if(x==0)break;
        x*=16;
        memset(f,0,sizeof(f));
        f[0]=1;
        for(int i=1;i<=6;i++)
           for(int j=a[i];j<=x;j++)
              f[j]+=f[j-a[i]];
        cout<<f[x]<<endl;
        }
    return 0;
}