记录编号	576994	评测结果	AAAAAAAAAA
题目名称	[SYOI 2018] WHZ 的数字	最终得分	100
用户昵称	lihaoze	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2022-10-19 23:50:24	内存使用	0.00 MiB

#include <bits/stdc++.h>

using i64 = long long;

i64 base[21];
i64 f[21], g[21];

void init() {
    base[0] = 1;
    for (int i = 1; i <= 20; ++ i) 
        base[i] = base[i - 1] * 10;
    f[1] = 1;
    for (int i = 2; i <= 20; ++ i)
        f[i] = f[i - 1] * 10 + base[i - 1];
    for (int i = 2; i <= 20; ++ i) 
        g[i] = g[i - 1] + f[i - 1] * 9;
}

i64 dp(i64 n) {
    if (n == 0) return 1;
    std::vector<int> nums;
    while (n) nums.emplace_back(n % 10), n /= 10;
    i64 last = 0, ans = 0;
    ans = g[nums.size() - 1];
    for (int i = nums.size() - 1; i >= 0; -- i) {
        int x = nums[i];
        for (int j = i == nums.size() - 1; j < x; ++ j) {
            ans += last * base[i] + f[i];
            if (j == 0) ans += base[i];
        }
        if (x == 0) ++ last;
        if (i == 0) ans += last;
    }
    return ans;
}

int main() {
    freopen("whz_number.in", "r", stdin); 
    freopen("whz_number.out", "w", stdout);
    init();
    i64 n, k;
    while (std::cin >> n >> k) {
        if (dp(n) < k) {
            std::cout << 0 << '\n';
            continue;
        }
        i64 l = 0, r = n;
        while (l < r) {
            i64 mid = l + r >> 1;
            if (dp(n) - dp(mid) < k) r = mid;
            else l = mid + 1;
        }
        std::cout << r << '\n';
    }
    return 0;
}