# H. Special Palindrome

time limit per test:1 second

memory limit per test:64 megabytes

input:standard input

output:standard output

A sequence of positive and non-zero integers called palindromic if it can be read the same forward and backward, for example:

15 2 6 4 6 2 15

20 3 1 1 3 20

We have a special kind of palindromic sequences, let's call it a special palindrome.

A palindromic sequence is a special palindrome if its values don't decrease up to the middle value, and of course they don't increase from the middle to the end.

The sequences above is NOT special, while the following sequences are:

1 2 3 3 7 8 7 3 3 2 1

2 10 2

1 4 13 13 4 1

Let's define the function F(N), which represents the number of special sequences that the sum of their values is N.

For example F(7) = 5 which are : (7), (1 5 1), (2 3 2), (1 1 3 1 1), (1 1 1 1 1 1 1)

Your job is to write a program that compute the Value F(N) for given N's.

Input

The Input consists of a sequence of lines, each line contains a positive none zero integer N less than or equal to 250. The last line contains 0 which indicates the end of the input.

Output

Print one line for each given number N, which it the value F(N).

Examples

Input

```1
3
7
10
0```

Output

```1
2
5
17```

``` 1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
5 {
6     ll x=0,f=1;
7     char ch=getchar();
8     while(ch<'0'||ch>'9')
9     {
10         if(ch=='-')
11             f=-1;
12         ch=getchar();
13     }
14     while(ch>='0'&&ch<='9')
15     {
16         x=x*10+ch-'0';
17         ch=getchar();
18     }
19     return x*f;
20 }
21 inline void write(ll x)
22 {
23     if(x<0)
24     {
25         putchar('-');
26         x=-x;
27     }
28     if(x>9)
29         write(x/10);
30     putchar(x%10+'0');
31 }
32 ll dp[333][333];
33 inline void funday(ll n)
34 {
35     for(ll i=1;i<=n;i++)
36     {
37         for(ll j=1;j<=n;j++)
38         {
39             if(i==1||j==1)
40                 dp[i][j]=1;
41             else if(i>j)
42                 dp[i][j]=dp[i-j][j]+dp[i][j-1];
43             else if(i==j)
44                 dp[i][j]=dp[i][i-1]+1;
45             else dp[i][j]=dp[i][i];
46         }
47     }
48 }
49 ll n,m,ans;
50 int main()
51 {
52     funday(251);
54     {
55         if(n==0)
56             return 0;
57         ans=0;
58         if(n&1)
59         {
60             for(ll i=1;i<=n;i+=2)
61                 ans+=dp[(n-i)/2][i];
62             ans++;
63         }
64         else
65         {
66             for(ll i=2;i<=n;i+=2)
67                 ans+=dp[(n-i)/2][i];
68             ans+=dp[n/2][n/2];
69             ans++;
70         }
71         write(ans);
72         printf("\n");
73     }
74     return 0;
75 }```

``` 1 void dfseven(int k, int sum)
2 {
3     if(2*sum > 50) return;
4     //cout<<"here1"<<endl;
5     for(int i = k; i <= 50; i++){
6         if(2*(sum + i) <= 50) {ans[2*(sum + i)]++; dfseven(i, sum + i);}
7         else return;
8     }
9
10 }
11
12 void dfsodd(int mid, int k, int sum)
13 {
14     if(2*sum + mid > 50) return;
15     //cout<<"here2"<<endl;
16     for(int i = k; i <= 50; i++){
17         if(2*(sum + i) + mid <= 50 && i <= mid) {ans[2*(sum + i) + mid]++; dfsodd(mid, i, sum + i);}
18         else return;
19     }
20
21 }```

``` 1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 using namespace std;
5 typedef long long LL;
6 const int maxn = 250 + 8;
7
8 int ans[maxn];
9
10 //偶数个的
11 void dfseven(int k, int sum)
12 {
13     if(2*sum > 50) return;
14     //cout<<"here1"<<endl;
15     for(int i = k; i <= 50; i++){
16         if(2*(sum + i) <= 50) {ans[2*(sum + i)]++; dfseven(i, sum + i);}
17         else return;
18     }
19
20 }
21
22 void dfsodd(int mid, int k, int sum)
23 {
24     if(2*sum + mid > 50) return;
25     //cout<<"here2"<<endl;
26     for(int i = k; i <= 50; i++){
27         if(2*(sum + i) + mid <= 50 && i <= mid) {ans[2*(sum + i) + mid]++; dfsodd(mid, i, sum + i);}
28         else return;
29     }
30
31 }
32
33 int main()
34 {
35     #ifdef LOCAL
36     freopen("a.txt", "r", stdin);
37     freopen("b.txt", "w", stdout);
38     #endif // LOCAL
39     memset(ans, 0, sizeof ans);
40     //ans[2]++;
41     dfseven(1, 0);
42     //ans[1]++;
43     for(int i = 1; i <= 50; i++){
44         dfsodd(i, 1, 0);
45     }
46     for(int i = 1; i <= 50; i++){
47         printf("ans[%d] = %d;", i, ans[i] + 1);
48     }
49
50 /*
51     int n;
52     while(scanf("%d", &n)){
53         printf("%d", ans[n]);
54
55     }
56     */
57     return 0;
58 }```

```  1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 using namespace std;
5 typedef long long LL;
6 const int maxn = 250 + 8;
7
8 LL ans[maxn];
9
10 int main()
11 {
12
13 ans[1] = 1;
14 ans[2] = 2;
15 ans[3] = 2;
16 ans[4] = 4;
17 ans[5] = 3;
18 ans[6] = 7;
19 ans[7] = 5;
20 ans[8] = 11;
21 ans[9] = 8;
22 ans[10] = 17;
23 ans[11] = 12;
24 ans[12] = 26;
25 ans[13] = 18;
26 ans[14] = 37;
27 ans[15] = 27;
28 ans[16] = 54;
29 ans[17] = 38;
30 ans[18] = 76;
31 ans[19] = 54;
32 ans[20] = 106;
33 ans[21] = 76;
34 ans[22] = 145;
35 ans[23] = 104;
36 ans[24] = 199;
37 ans[25] = 142;
38 ans[26] = 266;
39 ans[27] = 192;
40 ans[28] = 357;
41 ans[29] = 256;
42 ans[30] = 472;
43 ans[31] = 340;
44 ans[32] = 621;
45 ans[33] = 448;
46 ans[34] = 809;
47 ans[35] = 585;
48 ans[36] = 1053;
49 ans[37] = 760;
50 ans[38] = 1354;
51 ans[39] = 982;
52 ans[40] = 1740;
53 ans[41] = 1260;
54 ans[42] = 2218;
55 ans[43] = 1610;
56 ans[44] = 2818;
57 ans[45] = 2048;
58 ans[46] = 3559;
59 ans[47] = 2590;
60 ans[48] = 4485;
61 ans[49] = 3264;
62 ans[50] = 5616;
63 ans[51] = 4097;
64 ans[52] = 7018;
65 ans[53] = 5120;
66 ans[54] = 8728;
67 ans[55] = 6378;
68 ans[56] = 10826;
69 ans[57] = 7917;
70 ans[58] = 13373;
71 ans[59] = 9792;
72 ans[60] = 16484;
73 ans[61] = 12076;
74 ans[62] = 20236;
75 ans[63] = 14848;
76 ans[64] = 24793;
77 ans[65] = 18200;
78 ans[66] = 30275;
79 ans[67] = 22250;
80 ans[68] = 36886;
81 ans[69] = 27130;
82 ans[70] = 44810;
83 ans[71] = 32992;
84 ans[72] = 54329;
85 ans[73] = 40026;
86 ans[74] = 65683;
87 ans[75] = 48446;
88 ans[76] = 79265;
89 ans[77] = 58499;
90 ans[78] = 95419;
91 ans[79] = 70488;
92 ans[80] = 114650;
93 ans[81] = 84756;
94 ans[82] = 137447;
95 ans[83] = 101698;
96 ans[84] = 164496;
97 ans[85] = 121792;
98 ans[86] = 196445;
99 ans[87] = 145578;
100 ans[88] = 234221;
101 ans[89] = 173682;
102 ans[90] = 278720;
103 ans[91] = 206848;
104 ans[92] = 331143;
105 ans[93] = 245920;
106 ans[94] = 392722;
107 ans[95] = 291874;
108 ans[96] = 465061;
109 ans[97] = 345856;
110 ans[98] = 549781;
111 ans[99] = 409174;
112 ans[100] = 649019;
113 ans[101] = 483330;
114 ans[102] = 764959;
115 ans[103] = 570078;
116 ans[104] = 900373;
117 ans[105] = 671418;
118 ans[106] = 1058191;
119 ans[107] = 789640;
120 ans[108] = 1242061;
121 ans[109] = 927406;
122 ans[110] = 1455820;
123 ans[111] = 1087744;
124 ans[112] = 1704261;
125 ans[113] = 1274118;
126 ans[114] = 1992458;
127 ans[115] = 1490528;
128 ans[116] = 2326608;
129 ans[117] = 1741521;
130 ans[118] = 2713398;
131 ans[119] = 2032290;
132 ans[120] = 3160899;
133 ans[121] = 2368800;
134 ans[122] = 3677789;
135 ans[123] = 2757826;
136 ans[124] = 4274556;
137 ans[125] = 3207086;
138 ans[126] = 4962526;
139 ans[127] = 3725410;
140 ans[128] = 5755174;
141 ans[129] = 4322816;
142 ans[130] = 6667228;
143 ans[131] = 5010688;
144 ans[132] = 7716070;
145 ans[133] = 5802008;
146 ans[134] = 8920663;
147 ans[135] = 6711480;
148 ans[136] = 10303379;
149 ans[137] = 7755776;
150 ans[138] = 11888671;
151 ans[139] = 8953856;
152 ans[140] = 13705118;
153 ans[141] = 10327156;
154 ans[142] = 15784173;
155 ans[143] = 11899934;
156 ans[144] = 18162385;
157 ans[145] = 13699699;
158 ans[146] = 20879933;
159 ans[147] = 15757502;
160 ans[148] = 23983452;
161 ans[149] = 18108418;
162 ans[150] = 27524280;
163 ans[151] = 20792120;
164 ans[152] = 31561603;
165 ans[153] = 23853318;
166 ans[154] = 36160845;
167 ans[155] = 27342421;
168 ans[156] = 41397124;
169 ans[157] = 31316314;
170 ans[158] = 47353396;
171 ans[159] = 35839008;
172 ans[160] = 54124796;
173 ans[161] = 40982540;
174 ans[162] = 61816437;
175 ans[163] = 46828032;
176 ans[164] = 70548311;
177 ans[165] = 53466624;
178 ans[166] = 80453313;
179 ans[167] = 61000704;
180 ans[168] = 91682668;
181 ans[169] = 69545358;
182 ans[170] = 104403741;
183 ans[171] = 79229676;
184 ans[172] = 118806744;
185 ans[173] = 90198446;
186 ans[174] = 135102223;
187 ans[175] = 102614114;
188 ans[176] = 153528658;
189 ans[177] = 116658616;
190 ans[178] = 174350347;
191 ans[179] = 132535702;
192 ans[180] = 197865953;
193 ans[181] = 150473568;
194 ans[182] = 224406247;
195 ans[183] = 170727424;
196 ans[184] = 254344551;
197 ans[185] = 193582642;
198 ans[186] = 288094273;
199 ans[187] = 219358315;
200 ans[188] = 326120818;
201 ans[189] = 248410816;
202 ans[190] = 368939881;
203 ans[191] = 281138048;
204 ans[192] = 417130912;
205 ans[193] = 317984256;
206 ans[194] = 471335560;
207 ans[195] = 359444904;
208 ans[196] = 532274004;
209 ans[197] = 406072422;
210 ans[198] = 600743477;
211 ans[199] = 458482688;
212 ans[200] = 677637038;
213 ans[201] = 517361670;
214 ans[202] = 763943462;
215 ans[203] = 583473184;
216 ans[204] = 860768675;
217 ans[205] = 657667584;
218 ans[206] = 969336374;
219 ans[207] = 740890786;
220 ans[208] = 1091013811;
221 ans[209] = 834194700;
222 ans[210] = 1227313238;
223 ans[211] = 938748852;
224 ans[212] = 1379921672;
225 ans[213] = 1055852590;
226 ans[214] = 1550704877;
227 ans[215] = 1186949056;
228 ans[216] = 1741741564;
229 ans[217] = 1333640710;
230 ans[218] = 1955329266;
231 ans[219] = 1497705768;
232 ans[220] = 2194025352;
233 ans[221] = 1681116852;
234 ans[222] = 2460655086;
235 ans[223] = 1886061684;
236 ans[224] = 2758359212;
237 ans[225] = 2114965120;
238 ans[226] = 3090606588;
239 ans[227] = 2370513986;
240 ans[228] = 3461249193;
241 ans[229] = 2655684608;
242 ans[230] = 3874538905;
243 ans[231] = 2973772212;
244 ans[232] = 4335193118;
245 ans[233] = 3328423936;
246 ans[234] = 4848416380;
247 ans[235] = 3723675326;
248 ans[236] = 5419976831;
249 ans[237] = 4163989458;
250 ans[238] = 6056235989;
251 ans[239] = 4654300706;
252 ans[240] = 6764237552;
253 ans[241] = 5200062976;
254 ans[242] = 7551745299;
255 ans[243] = 5807301632;
256 ans[244] = 8427348786;
257 ans[245] = 6482671322;
258 ans[246] = 9400510845;
259 ans[247] = 7233519619;
260 ans[248] = 10481691022;
261 ans[249] = 8067955712;
262 ans[250] = 11682407480;
263     int n;
264     while(scanf("%d", &n)){
265         if(n == 0) break;
266         printf("%I64d\n", ans[n]);
267     }
268
269     return 0;
270 }```

0 条评论

• ### HDU 3782 xxx定律

xxx定律 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Jav...

• ### UVAlive 3708 Graveyard(最优化问题)

题目描述： 在周长10000的圆上,初始等距的放置着n个雕塑,现在新加入m个雕塑,要使得这n+m个雕塑仍然等距,问原来n个雕塑要移动的距离总和的最小值. 原...

• ### FZU 2167 大王叫我来巡山呐

Problem 2167 大王叫我来巡山呐 Accept: 931    Submit: 1405 Time Limit: 1000 mSec    Memo...

• ### 剑指offer——丑数

题目描述 把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑...

• ### NYOJ----次方求模

次方求模 时间限制：1000 ms  |  内存限制：65535 KB 难度：3 描述 求a的b次方对c取余的值 输入第一行输入一个整数n表示测试数据的组数...

• ### 勾股数组

一般地，若三角形三边长a,b,c都是正整数，且满足a,b的平方和等于c的平方，那么数组(a,b,c)称为勾股数组。勾股数组是人们为了解出满足勾...

• ### HDU 3782 xxx定律

xxx定律 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Jav...

• ### UVAlive 3708 Graveyard(最优化问题)

题目描述： 在周长10000的圆上,初始等距的放置着n个雕塑,现在新加入m个雕塑,要使得这n+m个雕塑仍然等距,问原来n个雕塑要移动的距离总和的最小值. 原...

• ### FZU 2167 大王叫我来巡山呐

Problem 2167 大王叫我来巡山呐 Accept: 931    Submit: 1405 Time Limit: 1000 mSec    Memo...