1019 Number Sequence

PKU

1019 Number Sequence

<概要>



S1S2...Sk...という数の集合の列をnumber sequenceという。

Skは12...kという数列である。

入力iが与えられたときi番目の数を答える問題。
!!! 注意 !!!

S10は12345678910であり、11個の数から構成される。

S10の10番目の要素は1であり、11番目の要素は0である。

二分探索×２で解ける。
まず、Sxまでのnumber sequenceの長さを返す関数length(x)を作る。
length(x)は単調増加するので、二分探索によってi番目の数が何個目のgroupに属するかを求められる。
length(l) < i < length(r)みたいな感じ。


例えばSnにi番目の数があるとわかったとする。
するとSnの中のi-length(S_{n-1})番目の数が求める数となる。

次にS∞の中でxまでの数列の長さを返す関数length2(x)を作る。
例えばlength2(12)=len("123456789101112")=15である。
これを使って再び二分探索を行い、i-length(S_{n-1})番目の数を求める。
length2(l) < i-length(S_{n-1}) < length2(r)みたいな感じ。


long long intを初めて使って苦労した。
型指定子は"ll"だ！
scanf("%lld", &i);

#include<cstdio>
#include<cmath>
#include<climits>
#include<string>

using namespace std;

/*
 * x番目のgroupまでの長さを返す
 * たとえばx=3ならば、
 * len("112123")=6を返す
 */
long long int length(long long int x) {
    long long int ret = 0;
    long long int keta = (long long int)log10(x);
    for (long long int i = 0, j = 10; i <= keta; ++i) {
        long long int xx = x - (long long int)pow((double)j, (double)i) + 1;
        ret += xx*(xx+1)/2;
    }
    return ret;
}

/*
 * 無限に続く∞番目のgroupを想定したとき
 * xまでの長さを返す
 * たとえばx=12ならば、
 * len("123456789101112")=15を返す
 */
long long int length2(long long int x) {
    long long int ret = 0;
    long long int keta = (long long int)log10(x);
    for (long long int i = 0, j = 10; i <= keta; ++i) {
        long long int xx = x - (long long int)pow((double)j, (double)i) + 1;
        ret += xx;
    }
    return ret;
}

/* long long int -> string変換
 */
string int2str(long long int num) {
    long long int keta = 1;
    long long int n = (long long int)log10(num);
    string ret = "";
    for (long long int i = 0; i < n; ++i) {
        keta *= 10;
    }
    for ( ; keta >= 1; keta/=10) {
        ret += num / keta + '0';
        num %= keta;
    }
    return ret;
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
	long long int i;
	scanf("%lld", &i);

        // i番目の数字が何番目のgroupに含まれるのか
        // 二分探索で求める
	long long int l = 1, r = 2147483647;
        while (r-l>1) {
	    long long int m = (l+r)/2;
	    if (length(m) > i) {
		r = m;
	    } else {
		l = m;
	    }
	}
	if (length(l) < i) {} // l+1番目のgroupにある
        else { --l;}  // l番目のgroupにある

        // 目的のgroupがわかったら
        // その中で再び二分探索をして、ターゲットを探す
        long long int ii = i-length(l); // l+1番目のgroupのii番目がターゲット
        long long int ll = 1, rr = length(l+1)-length(l);
        while (rr-ll>1) {
            long long int mm = (ll+rr)/2;
            if (length2(mm) > ii) {
                rr = mm;
            } else {
                ll = mm;
            }
        }
        if (length2(ll) < ii) {} // ll+1の中のどれか
        else { --ll; } // llの中のどれか
        
        string strnum = int2str(ll+1); // ll+1を文字列にする
        printf("%c\n", strnum[ii-length2(ll)-1]);
    }
}