• 博客访问： 1138966
• 博文数量： 196
• 博客积分： 4141
• 博客等级： 中将
• 技术积分： 2253
• 用 户 组： 普通用户
• 注册时间： 2009-03-21 20:04

2019年（31）

2016年（1）

2014年（16）

2011年（8）

2010年（25）

2009年（115）

2009-06-14 20:56:59

Recaman's Sequence

 Time Limit:5s Memory limit:32M Accepted Submit:383 Total Submit:1245

The Recaman's sequence is defined by a(0)=0; for m>0, a(m)=a(m-1)-m if the resulting a(m) is positive and not already in the sequence, otherwise a(m)=a(m-1)+m.

The first few numbers in the Recaman's Sequence is 0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9, ...

Input

The input consists of several test cases. Each line of the input contains an integer k where 0<=k<=500000.
The last line contains an integer -1, which should not be processed.

Output

For each k given in the input, print one line containing a(k) to the output.

Sample Input

`710000-1`

Sample Output

`2018658`

 ```#include #include #include struct Entry {     int i;     int val;     int next; }; int flag[1000000]; int out[500010]; int main() {     int i, val, t;     memset(flag, 0, sizeof(flag));     flag[0] = 1;     out[0] = 0;     for (i = 1; i <= 500000; ++i)     {         t = out[i - 1] - i;         if ((t < 0) || (flag[t / 32] & (1 << (t & 0x1F))))             t = out[i - 1] + i;         out[i] = t;         flag[t / 32] |= (1 << (t & 0x1F));     }     while (scanf("%d", &val) && (val >= 0))         printf("%d\n", out[val]);     return 0; } ```