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万ですから、配列記録を作ってもいいです.
タイトルの大意:
定義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;
}