codeforces - 1216E1 Numerical Sequence (easy version) (前缀和/二分)

题目链接：https://vjudge.net/problem/CodeForces-1216E1

题目描述：

The only difference between the easy and the hard versions is the maximum value of kk.

You are given an infinite sequence of form "112123123412345……" which consist of blocks of all consecutive positive integers written one after another. The first block consists of all numbers from 11 to 11, the second one — from 11 to 22, the third one — from 11 to 33, ……, the ii-th block consists of all numbers from 11 to ii.

So the first 5656 elements of the sequence are "11212312341234512345612345671234567812345678912345678910". Elements of the sequence are numbered from one. For example, the 11-st element of the sequence is 11, the 33-rd element of the sequence is 22, the 2020-th element of the sequence is 55, the 3838-th element is 22, the 5656-th element of the sequence is 00.

Your task is to answer qq independent queries. In the ii-th query you are given one integer kiki. Calculate the digit at the position kiki of the sequence.

Input

The first line of the input contains one integer qq (1≤q≤5001≤q≤500) — the number of queries.

The ii-th of the following qq lines contains one integer kiki (1≤ki≤109)(1≤ki≤109) — the description of the corresponding query.

Output

Print qq lines. In the ii-th line print one digit xixi (0≤xi≤9)(0≤xi≤9) — the answer to the query ii, i.e. xixi should be equal to the element at the position kiki of the sequence.

Examples

5
1
3
20
38
56

1
2
5
2
0

4
2132
506
999999999
1000000000

8
2
9
8

Note

Answers on queries from the first example are described in the problem statement.

　　题目描述就是给你一串数，可以分成若干段，每段为这个数字以及这个数字前几个数就像1 12 123 1234 12345这样，然后给你一个数i

让你求这个数列第ai位的数。

　　首先我们先想对于1234567891011121314这列数来说，每个数字的末位处于这个数以及这个数前面所有数的位数之和，比如5就位于第

5个位置，10的0位于第11个位置，14的4位于第19个位置，我们可以用一个前缀和来表示这些数的位置。

　　然后对于112123123412345这列数来说， 第一个1出现的位置就是1第一个2的位置就是1的位数加上12的位数，第一个11末位1的位置

就是1 + 12 + 123 + 1234 。。。的位数，即上面位数前缀和的前缀和。

　　对于一个位置num来说，它前面必定有若干个1 12 123 1234这样的序列，所以我们就可以用二分在前缀和的前缀和序列中找一个小于他

的最大的数，那么他们的差就是序列12345678910...列数中的某个位置，即在前缀和序列中的位置，这里我们可以再用一次二分，然后求得

一个大于或者等于这个数的最小的值，那么num在减去这个位置就是答案了

#include<set>
#include<map>
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<string>
#include<vector>
#include<climits>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define endl ‘\n‘
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
#define mst(a) memset(a, 0, sizeof(a))
#define IOS ios::sync_with_stdio(false)
#define _test printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n")
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const double pi = acos(-1.0);
const double eps = 1e-7;
const ll MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const int _NAN = -0x3f3f3f3f;
const int NIL = -1;
const int maxn = 2e5+10;
ll _ls[maxn], _sumls[maxn];
int main(void) {
    for (ll i = 1; i<maxn; ++i) {
        ll t = (ll)((log10(i)+eps)+1); //求数字位数
        _ls[i] = _ls[i-1] + t; //求1234567位数的前缀和(1234567中每个数字末位对应的位数)
        _sumls[i] = _sumls[i-1] + _ls[i]; //求前缀和的前缀和(1121231234中每个数字第一次出现时其末位对应的位数)
    }
    //printf("%lld %lld\n", _ls[maxn-1],_sumls[maxn-1]);
    int n;
    scanf("%d", &n);
    while(n--) {
        ll num;
        scanf("%lld", &num);
        ll *pos1 = lower_bound(_sumls+1, _sumls+maxn, num); 
        if (*pos1 == num) 
            printf("%d\n", (pos1-_sumls)%10);//刚好对应某个第一次出现的数字的末尾
            //指针相减默认是int类型，如果用lld输出结果会出错
        else {
            //对应某个数字的某位上
            --pos1; 
            num -= *pos1;
            ll *pos2 = lower_bound(_ls+1, _ls+maxn, num);
            string nums; //把这个数字转成字符串
            ll t2 = pos2-_ls;
            while(t2) {
                nums += t2%10 + ‘0‘;
                t2 /= 10;
            }
            reverse(nums.begin(), nums.end());
            --pos2;
            num -= *pos2; //求出结果在字符串上的位置
            printf("%c\n", nums[num-1]);
            nums.clear();
        }
    }
    return 0;
}

codeforces - 1216E1 Numerical Sequence (easy version) (前缀和/二分)

原文：https://www.cnblogs.com/shuitiangong/p/12288504.html