PKU Judge Online 2081 Recaman's Sequence

■2081 Recaman's Sequence

□Problem
Recaman数列とは，以下で定義される．
a₀=0
a_m=a_m-1-m
(a_m>0かつ，a_n=a_mとなるn<mが存在しない時)
a_m=a_m-1+m
(それ以外の時)

a_kを求めよ．

□Solution
0≦k≦500000であるため，予めa_kを求めておく．

□Code

package p2081;

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

 Scanner sc=new Scanner(System.in);

 final int INF=Integer.MAX_VALUE;
 final double EPS=1e-9;

 void run(){
  int[] a=new int[500001];
  HashSet<Integer> set=new HashSet<Integer>();
  for(int m=1; m<500001; m++){
   int a2=a[m-1]-m;
   if(a2>0&&!set.contains(a2))
    a[m]=a2;
   else
    a[m]=a[m-1]+m;
   set.add(a[m]);
  }
  for(;;){
   int k=sc.nextInt();
   if(k==-1)
    break;
   println(a[k]+"");
  }
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}