map水过2400ms+懒得改成hash了
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.
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.
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.
Sample Input
7 10000 -1
Sample Output
20 18658
#include <iostream>
#include <map>
using namespace std;
map<int,int> l;
map<int,int>::iterator it;
const int S=500010;
int a[S];
int main(){
a[0]=0;
l[0]=1;
int i,j,k,tmp,n,max=0;
for (i=1;i<S;i++){
tmp=a[i-1]-i;
it=l.find(tmp);
if (tmp>0)
if (it==l.end()){
l[tmp]=1;
a[i]=tmp;
continue;
}
tmp=a[i-1]+i;
if (tmp>max) max=tmp;
a[i]=tmp;
l[tmp]=1;
}
while (cin>>n,n>=0){
cout<<a[n]<<endl;
}
return 0;
}