ZOJ 2421 Recaman's Sequence


http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1421
タイトルの大意:
定義a^mは a^m=a^(m-1)-m a^mが正であって、かつ出現したことがない場合.a^m=a^(m-1)+mでないと.kをあげます.a^kをお願いします.
考え方:
メーターを押す
kは最大50万で、a[500000]<63万ですから、配列記録を作ってもいいです.
#include<cstdio>
const int MAXK=500000+2;
const int MAXN=630000;
int a[MAXK];
bool exist[MAXN]={0};
int main()
{
	a[0]=0;
	exist[0]=1;
	for(int i=1;i<MAXK;i++)
	{
		if(a[i-1]-i>0 && !exist[ a[i-1]-i ])
			a[i]=a[i-1]-i;
		else
			a[i]=a[i-1]+i;
		exist[ a[i] ]=1;
	}
	//printf("%d
",a[500000]); 62W int k; while(~scanf("%d",&k),k!=-1) { printf("%d
",a[k]); } return 0; }