Recaman's Sequence
| Time Limit: 3000MS | Memory Limit: 60000K | |
| Total Submissions: 18575 | Accepted: 7751 |
Description
The Recaman's sequence is defined by a0 = 0 ; for m > 0, a
m = a
m−1 − m if the rsulting 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 ...
Given k, your task is to calculate a k.
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 a k.
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.
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
7 10000 -1
Sample Output
20 18658
#include <stdio.h>
#include <string.h>
const int N=500010;
int ch[N];
bool vis[N*10];//状态数组一定要开得比数字数组大，否则测试时会ＲＥ
void init()
{
int i,j;
memset(vis,false,sizeof(vis));
memset(ch,0,sizeof(ch));
vis[0]=vis[1]=vis[3]=true;
ch[0]=0;ch[1]=1;
for(i=2;i<N;i++)
{
ch[i]=ch[i-1]-i;
if(ch[i]<1||vis[ch[i]])
ch[i]=ch[i-1]+i;
vis[ch[i]]=true;
}
return ;
}
int main()
{
int i,j,k;
init();
while(scanf("%d",&k),k!=-1)
printf("%d\n",ch[k]);
return 0;
}
