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

view plainprint?

1. package p2081;  
2.   
3. import java.util.*;  
4. import java.lang.*;  
5. import java.math.*;  
6. import java.io.*;  
7.   
8. import static java.lang.Math.*;  
9. import static java.util.Arrays.*;  
10.   
11. // AC  
12. public class Main{  
13.   
14.  Scanner sc=new Scanner(System.in);  
15.   
16.  final int INF=Integer.MAX_VALUE;  
17.  final double EPS=1e-9;  
18.   
19.  void run(){  
20.   int[] a=new int[500001];  
21.   HashSet<Integer> set=new HashSet<Integer>();  
22.   for(int m=1; m<500001; m++){  
23.    int a2=a[m-1]-m;  
24.    if(a2>0&&!set.contains(a2))  
25.     a[m]=a2;  
26.    else  
27.     a[m]=a[m-1]+m;  
28.    set.add(a[m]);  
29.   }  
30.   for(;;){  
31.    int k=sc.nextInt();  
32.    if(k==-1)  
33.     break;  
34.    println(a[k]+"");  
35.   }  
36.  }  
37.   
38.  void print(String s){  
39.   System.out.print(s);  
40.  }  
41.   
42.  void println(String s){  
43.   System.out.println(s);  
44.  }  
45.   
46.  public static void main(String[] args){  
47.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
48.   new Main().run();  
49.  }  
50. }  

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();
 }
}