比赛 2025.10.18 评测结果 AAAAAAAAAA
题目名称 WHZ 的数字 最终得分 100
用户昵称 徐诗畅 运行时间 0.418 s
代码语言 C++ 内存使用 3.88 MiB
提交时间 2025-10-18 10:37:36
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
long long n,k;
__int128 f[21][21][2][2],a[21];
__int128 dfs(int pos,int s,int limit,int le){ 
	if(pos==0) return s;
	if(f[pos][s][limit][le]!=-1) return f[pos][s][limit][le];
	__int128 res=0;
	for(int i = 0;i<=(limit?a[pos]:9);i++){
		if(i==0){
			if(le) res+=dfs(pos-1,s+1,limit&&a[pos]==i,le);
			else res+=dfs(pos-1,s,limit&&a[pos]==i,0);
		}
		else res+=dfs(pos-1,s,limit&&a[pos]==i,1);
	}
	f[pos][s][limit][le]=res;
	return res;
}
__int128 solve(long long x){
	int len=0;
	while(x){
		a[++len]=x%10;
		x/=10;
	}
	memset(f,-1,sizeof(f));
	return dfs(len,0,1,0);
}
signed main(){
	freopen("whz_number.in","r",stdin);
	freopen("whz_number.out","w",stdout);
	while(scanf("%lld%lld",&n,&k)!=EOF){
		__int128 x=solve(n);
		long long l=0,r=n;
		while(l<r){
			long long mid=(l+r)>>1;
			if(x-solve(mid)>=(__int128)k) l=mid+1;
			else r=mid;
		}
		printf("%lld\n",l);
	}
	return 0;
}