AOJ2177 Champernowne Constant

AOJ Volume21

問題リンク Champernowne Constant

  • 概要

Champernowne定数とは、"0."の後ろに正の数を連続で並べたような無理数の事である。
0.1234567891011121314...
2つの正の整数NとKが与えられる。Champernowne定数の小数点以下N位からK文字を求めよ。
1 <= N <= 10^9
1 <= K <= 100

  • 解法

区間分割で解きました。
10億以上の桁を生成するのは当然無理なので、1からの整数を1000個ずつ分割して考えます。
区間 i (0<=i)にはi*1000からi*1000+999までの整数があることになります。
ここで、区間の両端の整数i*1000とi*1000+999の桁数が等しかったら、この区間の長さは1000*桁数とすぐ分かります。もし違ったら、実際に1000個の整数の桁数を加算すればいいでしょう。区間の両端の数字が異なる箇所は多くても10回程度しか起こらないので、ほとんどの区間で定数時間で求まることになります。
配列a[i]には区間iより前にある区間の桁数の総和が入っているものとします。このとき、出力するべき部分の先頭を含んでいる区間iは
a[i] <= N && N < a[i+1]
を満たす場所となります。これを二分探索なり、めんどくさかったら線形時間なりで求めます。
目的の区間iが求まったら、N〜N+K-1文字目を覆うまで、文字列を作って出力すればOKです。

  • ソース
import java.util.Scanner;

//Champernowne Constant
public class AOJ2177 {

	void run(){
		int S = 125000;
		int[] a = new int[S];
		int s = 0;
		for(int i=0;i<S;i++){
			a[i] = s;
			int L = 1000*i, R = L+999;
			if((L+"").length()==(R+"").length())s+=1000*(L+"").length();
			else{
				for(int k=L;k<=R;k++)s+=(k+"").length();
			}
		}
		Scanner sc = new Scanner(System.in);
		for(;;){
			int N = sc.nextInt(), K = sc.nextInt();
			if((N|K)==0)break;
			int id = 0;
			for(int i=0;i+1<S;i++){
				if(a[i]<=N&&N<a[i+1]){
					id = i; break;
				}
			}
			N-=a[id];
			StringBuilder sb = new StringBuilder();
			for(int k=1000*id;sb.length()<=N+K;k++)sb.append(k);
			System.out.println(sb.substring(N, N+K));
		}
	}
	
	public static void main(String[] args) {
		new AOJ2177().run();
	}
}