POJ 1221

 1 #include <iostream>
 2 #define MAXN 500
 3 using namespace std;
 4 
 5 unsigned dp[MAXN][MAXN];
 6 
 7 int main()
 8 {
 9 //    freopen("acm.acm","r",stdin);
10     int i;
11     int j;
12     int num;
13     for(i = 0; i < MAXN; ++ i)
14     {
15         dp[0][i] = 1;
16     }
17 
18     for(i = 0; i < MAXN; ++ i)
19     {
20         for(j = i/2+1; j <= i; ++ j)
21         {
22             dp[i][j] = 1;
23         }
24     }
25 
26     for(i = 0; i < MAXN; ++ i)
27     {
28         for(j = i/2; j > 0; -- j)
29         {
30             dp[i][j] = dp[i-2*j][j] + dp[i][j+1];
31         }
32     }
33 
34     while(cin>>num,num)
35     {
36         cout<<num<<" "<<dp[num][1]<<endl;
37     }
38 }