2010年10月1日金曜日

PKU Judge Online 2081 Recaman's Sequence

■2081 Recaman's Sequence

□Problem
Recaman数列とは,以下で定義される.
a0=0
am=am-1-m
(am>0かつ,an=amとなるn<mが存在しない時)
am=am-1+m
(それ以外の時)

akを求めよ.

□Solution
0≦k≦500000であるため,予めakを求めておく.

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

0 件のコメント: