记录编号	607669	评测结果	AAAAAAAAAA
题目名称	2949.[SYOI 2018] WHZ 的数字	最终得分	100
用户昵称	梦那边的美好ME	是否通过	通过
代码语言	C++	运行时间	0.070 s
提交时间	2025-10-19 19:43:28	内存使用	3.70 MiB

#include <iostream>
#include <algorithm>
using namespace std;

using ull = unsigned long long;

// 计算 [0, x] 区间内所有数字中0的个数
ull countZeros(ull x) {
    if (x == 0) return 1;
    
    ull res = 0, b = 1;
    while (b <= x) {
        ull high = x / (b * 10);      // 高位部分
        ull digit = (x / b) % 10;     // 当前位
        ull low = x % b;              // 低位部分
        
        if (digit == 0) {
            // 当前位为0时
            res += (high > 0 ? (high - 1) * b + low + 1 : 0);
        } else {
            // 当前位不为0时
            res += high * b;
        }
        b *= 10;
    }
    return res + 1; // 包括数字0
}

// 计算 [l, r] 区间内0的个数
ull countZerosInRange(ull l, ull r) {
    if (l == 0) return countZeros(r);
    return countZeros(r) - countZeros(l - 1);
}

int main() {
	freopen("whz_number.in","r",stdin);
	freopen("whz_number.out","w",stdout);
    ull n, k;
    
    while (cin >> n >> k) {
        // 如果 [0, n] 区间内0的个数正好等于k，那么m=0就是解
        ull totalZeros = countZeros(n);
        if (totalZeros == k) {
            cout << 0 << endl;
            continue;
        }
        
        // 如果需要的0个数比总0个数还多，无解
        if (k > totalZeros) {
            cout << 0 << endl;
            continue;
        }
        
        // 二分查找最大的m，使得 [m, n] 区间内恰好有k个0
        ull left = 0, right = n;
        ull ans = 0;
        bool found = false;
        
        while (left <= right) {
            ull mid = left + (right - left) / 2;
            ull zeros = countZerosInRange(mid, n);
            
            if (zeros == k) {
                // 找到满足条件的m，尝试找更大的m
                ans = mid;
                found = true;
                left = mid + 1;
            } else if (zeros > k) {
                // 0太多了，需要增大m来减少0的数量
                left = mid + 1;
            } else {
                // 0太少了，需要减小m来增加0的数量
                right = mid - 1;
            }
        }
        
        if (found) {
            cout << ans << endl;
        } else {
            cout << 0 << endl;
        }
    }
    
    return 0;
}