---
tags: VNOJ, THT, Medium Implementation, Implementation, Greedy, DP, DP-digit, Champernowne Constant, Binary Search, Stack, Online Query, SPyofgame
---

Tin học trẻ 2021 - Vòng sơ khảo - Bảng C - Dãy số tự nhiên
===

[https://oj.vnoi.info/problem/tht21_skc_seq](https://oj.vnoi.info/problem/tht21_skc_seq)

-----

###### Tags: `Medium Implementation`, `Greedy`, `DP-digit`, `Champernowne Constant`, `Binary Search`, `Stack`, `Online Query`
###### Contributor: @[WuTan](https://codeforces.com/profile/WuTan), @[Duy_e](https://codeforces.com/profile/Duy_e), @[Demen100ns](https://codeforces.com/profile/DeMen100ns)

-----
### Hướng dẫn subtask 1

**Gợi ý 1:** Chỉ cần xét $k + p$ số đầu tiên của dãy $123456789101112131415161718192021\dots$

**Gợi ý 2:** Thực hiện $k$ lần thao tác xóa, mỗi lần xóa duyệt qua $k + p$ chữ số là cùng

**Gợi ý 3:** Gọi kí tự đang xét là $x$ và kí tự bên phải nó là $y$. Xét các trường hợp $x < y$, $x = y$ và $x > y$ để xóa cho tối ưu

**Gợi ý 4:** Ưu tiên xóa các chữ số ở bên trái trước bên phải

> **Phần cài đặt xin bạn đọc xem như là bài tập để hiểu rõ hơn trước khi bước vào subtask 2**

-----
### Hướng dẫn subtask 2

Lấy ít nhất $k + p$ số đầu tiên của dãy $123456789101112131415161718192021\dots$

Gọi $S$ là đoạn giá trị lấy được, $T$ là giá trị tối đa của $S$ sau khi xóa $k$ kí tự cần tìm

Ban đầu xét $T$ rỗng. Để làm $T$ lớn hơn sau khi xóa đủ $k$ kí tự thì ta duyệt từ trái qua phải các chữ số $d$ trong $S$ và ưu tiên chọn kí tự lớn hơn để thêm. Nếu có chữ số cuối cùng của $T$ là $c$ mà
- $c \geq d$, ta thêm chữ số $d$ vào cuối $T$ vì nó không ảnh hưởng gì cả
- $c < d$, nếu ta thêm $d$ sẽ không tối ưu, nên ta xoá các chữ số cuối cùng của $T$ tới khi điều kiện không còn thỏa hoặc không còn xóa được nữa ($T$ rỗng, hoặc số lần xóa đã bằng $k$ rồi)

Cuối cùng để tránh trường hợp mà thừa $k$ ví dụ như $S$ gồm các chữ số thì ta sẽ xóa $k$ chữ số cuối của $T$

Giờ ta cần phải biết tại sao $c < d$ sẽ không tối ưu:
- Nhận thấy mình duyệt các chữ số từ trái qua phải nên nếu có một kí tự ở đầu không tối ưu thì dù số cuối có full chữ số $9$ cũng không thể lớn hơn dược.
- Cụ thể, xét $T_1 = \overline{125ABC}$ và $T_2 = \overline{124XYZ}$ là 2 cách chọn khác nhau. Thì ta có $\overline{125ABC} \geq 125000 > 124999 \geq \overline{124XYZ}$
- Nên nếu giả sử chữ số cuối của $T$ đang là $c = 4$ mà có chữ số $d$ trong $s$ là $d = 5$ thì mình sẽ xóa chữ số cuối của $T$ đi đến khi nào không xóa được nữa

-----
### Code Subtask 2

> **Time:** $O(p + k + log_{10}(max(k, p)))$
> **Space:** $O(p + k + log_{10}(max(k, p)))$
> **Algo:** Stack, Greedy

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

const int LIM = 1e6 + 16;
vector<int> dig[LIM];

/// Precalculation reduce significant amount of modulo you use and some other constant factors
void precal()
{
    for (int n = 1; n <= LIM; ++n)
    {
        for (int t = n; t > 0; t /= 10) dig[n].push_back(t % 10);
        reverse(dig[n].begin(), dig[n].end());
    }
}

int query(int k, int p)
{
    /// If this range is too large to calculate then we can stop
    /// But the answer is likely to be 9 so you can return for a little score
    if (k > LIM || p > LIM) return 9;

    /// Take at least k + p numbers, and at most k + p + 6 digits (since log10(LIM) = 6)
    /// Using reserve to boost vector faster
    vector<int> T;
    T.reserve(k + p + 6);
    
    /// For each number from 1 to 1e15 (actually we limit it at 1e6)
    for (int x = 1; x <= LIM; ++x)
    {
        /// For each digit in x
        for (int d : dig[x])
        {
            /// While the last digit in T is not optimal
            while (k > 0 && T.size() && T.back() < d) --k, T.pop_back();
            
            /// Insert the digit to the back of T
            T.push_back(d);
            
            /// Found the answer
            /// * (k == 0)        -> used (k) deletion
            /// * (T.size() >= p) -> found the (p)-th digit
            ///
            if (k == 0 && T.size() >= p) return T[p - 1];
        }
    }
}

int main()
{
    ios::sync_with_stdio(NULL);
    cin.tie(NULL);
    precal();
    
    int q;
    cin >> q;

    while (q-->0)
    {
        int k, p;
        cin >> k >> p;
        cout << query(k, p) << "\n";
    }


    return 0;
}

-----
### Hướng dẫn subtask 3

Để cho tiện thì ta sẽ định nghĩa $F_{1, X} = \overline{123456789101112131415161718192021...X}$ là một số mà được ghép bởi từng chữ số của các số nguyên dương từ $1$ đến $X$
Tương tự ta định nghĩa tổng quát cho $F_{L, R}$

---
**Nhận xét:** Ta sẽ luôn ưu tiên xoá các chữ số nhỏ hơn chữ số $9$ vì chữ số $9$ lớn nhất trong hệ thập phân

Ta sẽ tìm vị trí $m$ đầu tiên mà có $S = F_{1, m}$ sao cho nếu ta coi $T$ là phần còn lại của $S$ sau khi xóa tối đa $k$ chữ số khác chữ số $9$ thì $|T| \geq p$.
Hay nói một cách đơn giản hơn là số $m$ nhỏ nhất mà số $S$ tạo bởi $F_{1, m}$ có độ dài ít nhất là $k + p$

Sau đó ta tìm vị trí $x$ lớn nhất không quá $m$ mà có ít nhất một chữ số $9$, sau đó ta xóa hết tất cả các chữ số khác $9$ trong đoạn $F_{1, x}$ của $S$. Nếu không tồn tại chữ số $x$ như thế, thì gán $x = 0$
- Nhận thấy rằng với mọi $x \geq 9$ thì sẽ tồn tại ít nhất một số nguyên dương trong đoạn $[x - 9, x]$ mà có chữ số $9$ ở hệ biểu diễn thập phân nên ta có thể trâu tìm kết quả
- Trong trường hợp $x < 9$, khi không tồn tại số nào có chứ số $9$, hay ta gán cụ thể là $x = 0$, ta cũng có thể chứng minh được là lúc này $m \leq 9$
- Vì độ dài của một số tối đa là $15$ (vì $x \leq 10^{15}$) nên cùng lắm cần duyệt qua $10 \times 15$ chữ số để tìm $X$ (tối ưu được nhưng không đáng kể)

Để cho tiện thì định nghĩa
- $len$ là số chữ số của $S$
- $cnt$ là số chữ số $9$ trong $S$
- $curp$ là số chữ số trong $S$ sau khi xóa $k$ kí tự
Ta có số chữ số đã bị xóa trong hành động vừa rồi là $len - cnt$

Xét trường hợp thứ nhất khi $T$ có dạng $\overline{99999\dots99}$.
- Giờ ta có xóa thêm $k - cnt$ chữ số cho đủ $k$ thì $T$ vẫn chỉ chứa chữ số $9$
- Vì trong $T$ đã chứa vị trí $p$ cần tìm nên kết quả sẽ là $9$

Ngược lại số có dạng $T$ = $\overline{99999\dots ABCDE\dots}$ với $A, B, C, D, E, \dots$ là các chữ số khác $9$
Lúc này ta sẽ bỏ qua nguyên đoạn số $9$ ở đầu để chỉ duyệt phần còn lại $Q = \overline{ABCDE\dots}$

Xét trường hợp thứ hai khi $x < m$
- Lúc này $Q = F_{x + 1, m}$
- Giờ chúng ta cần tìm chữ số thứ $p - cnt$ sau khi xóa thêm $k - (len - cnt)$ kí tự
- Ta làm tương tự như subtask $2$

Xét trường hợp thứ ba là khi $x = m$
- Ta cần tìm chữ số thứ $p$ trong dãy $|S|$ độ dài $curp$
- Làm tương tự như trường hợp thứ hai, với $Q = F_{m, m}$

-----
### Code Subtask 3

> For constant $b = 10$ is the current base
> **DP Time:** $O(f(x)) = O(log^2_{b}(max(k, p)))$
> **Query Time**: $O(g(x)) = O(log_{2}(max(k, p)) \times f(x) + log_{b}(max(k, p)) \times b)$
> **Total Time:** $O(q \times g(x)) \leq O(q \times log^3(k + p))$
> **Space:** $O(f(x))$
> **Algo:** Medium Implementation, Greedy, DP-digit, Champernowne Constant, Binary Search, Stack, Online Query

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>

using namespace std;
typedef long long ll;

/// Break number into a list of digits
/// Assume V = 102109
/// Then num = {1, 0, 2, 1, 0, 9}
vector<int> num;
void pull(ll V)
{
    num.clear();
    do num.push_back(V % 10);
    while (V /= 10);
    reverse(num.begin(), num.end());
}

/// DP-digit:
///     Let S = 123456789101112131415161718192021...n
///     For n = number before break into list <num>
///     Return the number of digit 9 in |S|
///
/// DP-Function: magic(int len, int cnt, bool iln)
///     Currently have (len) length and counted (cnt) digit (9)
///     If (iln = true) means the current number is less than (n)
///     otherwise current number is not greater than (n)
///
/// Transistion: Sigma(len + 1, cnt + (d == 9), iln || (d < upper)) | d = 0 -> upper
///     d = 0 -> upper            : only build the number that not greater than n
///     len -> len + 1            : build next digit
///     cnt -> cnt + (d == 9)     : if selected digit is (9) then count the digit
///     iln -> iln || (d < upper) : If (iln) is already true, or (d < upper) meaning this number is smaller than n
///                                 For example: 123'xyzt < 124'0000 for all xyzt
///
/// Default: (0, 0, 0)
///     Currently the number has (0) length, counted (0) digit 9 and currently not greater than n
///     No leading-zero numbers are counted

ll f[18][18][2];
ll magic(int len = 0, int cnt = 0, bool iln = 0)
{
    if (len >= num.size()) return cnt;
    ll &res = f[len][cnt][iln];
    if (res != -1) return res;
    
    res = 0;
    int upper = iln ? 9 : num[len];
    for (int d = 0; d <= upper; ++d)
        res += magic(len + 1, cnt + (d == 9), iln || (d < upper));

    return res;
}

/// S = 123456789101112131415161718192021...n
/// return length of S
ll Champernowne_length(ll n)
{
    ll cnt = 0;
    for (ll x = 1; x <= n; x *= 10)
        cnt += (n - x + 1);

    return cnt;
}

/// S = 123456789101112131415161718192021...n
/// return number of digit 9 in S
ll Champernowne_cnt_9(ll V)
{
    pull(V);
    memset(f, -1, sizeof(f));
    return magic();
}

/// Let n = 10^15
/// And S = 123456789101112131415161718192021...n
///
/// query >> (k, p)
///     Delete (k) digit in (S) that (S) is maximum
///     Find (p)-th digit in (S)
///
/// Example: (k = 10, p = 5)
///     (S) = 123456789101112131415...n
///     After delete (S) = 91112131415...n
///
int query(ll k, ll p)
{
/// The optimal solution is to delete all digit except (9)
///     
///     We find first position (m) that S = 123456789101112131415161718192021...m
///     and the remaining length of (S) >= p after deleting at most (k) non-9 digits
///     after that we find the largest number (x) not greater than (m) that contain last digit 9
///     then we delete all digits exept (9) in 123456789101112131415161718192021...x
///                             
    ll curp; /// Length of |S|, also the position of last digit in S after deletion
    ll curk; /// The last number concated to S
    ll len;  /// The number of digit in (S)   (no leading zeros)
    ll cnt;  /// The number of digit 9 in (S) (no leading zeros)
    for (ll l = 1, r = 1e15; l <= r; )
    {
        ll m = l + r >> 1;
        
        ll tmp_cnt = Champernowne_cnt_9(m);  
        ll tmp_len = Champernowne_length(m);
        ll tmp_p = tmp_len - k;
        if (tmp_p >= p) 
        {
            curk = m;
            curp = tmp_p;
            cnt = tmp_cnt;
            len = tmp_len;
            r = m - 1;
        }
        else
        {
            l = m + 1;
        }
    }

    if (k >= len - cnt)
    {
    /// Case #1: If the number of digit we must delete (k) is greater than or equal the number of digit (9) in S
    ///          
    ///     We can delete all other digit that is not (9)
    ///     The remaining (S) will be 9999999...
    ///     Therefore the answer will be (9) (since p <= |S|)
    ///
        return 9;
    }
    
    ll curx = curk;
    while (curx >= 1 && curx % 10 != 9) --curx;
    cnt = Champernowne_cnt_9(curx);
    len = Champernowne_length(curx);
    
    k -= len - cnt;
    if (k >= 0)
    { 
    /// Case #2: (x) < (m)
    ///
    ///     Let Q = (x+1)(x+2)(x+3)...m | concatenating positive integers from (x + 1) to (m)
    ///     Now we have to know how to find the (p)-th digit in Q after deleting (k) digits that maximize Q
    ///     For every (x) >= 9, it will always exist at least one number in [x - 9, x] that having digit 9 in it
    ///     And when (x) < 9, you can prove that (m <= 9)
    ///     Therefore you can just simply do a brute-forces of maximumly O(log10(m) * 10) digits
    //     
        vector<int> S;
        while (++curx <= curk)
        {
            /// Get digits of current number
            ///
            pull(curx);
            for (ll d : num)
            {
                /// We remove all smaller digits since them only make the whole number smaller
                /// Example: 125XYZ > 124XYZ for whatever XYZ you choose
                /// Therefore the last digits of the current stack should be as large as possible
                /// Notice that you only delete exactly k digits therefore you cant make the number smaller 
                ///
                while (k && S.size() && d > S.back()) S.pop_back(), --k;
                S.push_back(d);
            }
        }
        
        /// You ignored the first (cnt) digits
        p -= cnt;
        return S[p - 1];
    } 
    
/// Case #3: (x) = (m)
///     
///     The answer is in the digits of (x).
///     You have deleted exactly (k) digits
///     But dont forget that you still need to output the digit at [p]
///     Currently use are in (m)     
///
    pull(curk);

    /// Notice that (curk) give you up to (curp) digits, therefore reduce it to the (p)-th digit
    while (curp > p) num.pop_back(), --curp;
    return num.back();
}

int main()
{
    /// Fast input
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    
    ll q;
    cin >> q;
    
    /// For each query
    while (q-->0)
    {
        ll k, p;
        cin >> k >> p;    
        cout << query(k, p) << "\n";
    }

    return 0;
}

-----
### Bonus:

- Bạn có thể giải với độ phức tạp $O(q \times log^2(k + p))$ không ?