PKU 1019 Number Sequence

Number Sequence

入力 i に対して、i が含まれるグループを S_k とすると、k もグループ S_k の長さ |S_k| も O(√i) 程度である。x の桁数を digit(x) として、

　|S_x| = |S_x-1| + digit(x)

が成り立つことから k を求める。グループ１つに対してならば n 番目の数字をナイーブに計算しても間に合う。

#include <iostream>
#include <cmath>

using namespace std;

//  x の桁数
int digit( int x )
{
    return (int)log10( (double)x ) + 1;
}

int main()
{
    int t;  cin >> t;
    while ( t-- > 0 )
    {
        int i;  cin >> i;

        //  i が含まれるグループ以前の分をまとめて引く
        int s = 0;
        for ( int j=1; i>0; j++ )
            i -= s += digit(j);
        i += s;

        //  i が含まれる数字を求める
        int j;
        for ( j=1; i>0; j++ )
            i -= digit(j);
        i += digit(--j);

        //
        int ans = (int)( j / pow(10.0,digit(j)-i) ) % 10;
        cout << ans << endl;
    }

    return 0;
}