Question

求解一道ACM习题，北大OJ2081

Description

The Recaman's sequence is defined by a0 = 0 ; for m > 0, am = am−1 − m if the rsulting am is positive and not already in the sequence, otherwise am = am−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 ...
Given k, your task is to calculate ak.
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 ak to the output.

Answer 1

题意：
定义 a0 = 0 ；当m>0时，am = am-1 -m；如果am <1或者前面出现过am = am-1 + m.输入k，求出ak。

解法：
按所给的递推公式做就可以了。

代码：
#include<stdio.h>
#include<string.h>
int a[500005];
bool f[3012505];
void init()
{
int i;
memset(f,0,sizeof(f));
a[0] = 0;
for(i=1;i<=500000;i++){
if(a[i-1]-i > 0 && ! f[a[i-1]-i]){
a[i]=a[i-1]-i;
f[a[i-1]-i] = 1;
}
else{
a[i]=a[i-1]+i;
f[a[i-1]+i]=1;
}

}
}
int main()
{
int k;

init();
while(scanf("%d",&k),k!=-1){
printf("%d\n",a[k]);
}
return 0;
}