比赛 EYOI与SBOI开学欢乐赛11th 评测结果 WWWWWWWWWW
题目名称 WHZ 的数字 最终得分 0
用户昵称 yrtiop 运行时间 0.465 s
代码语言 C++ 内存使用 4.59 MiB
提交时间 2022-10-14 21:44:03
显示代码纯文本
#include <bits/stdc++.h>
typedef unsigned long long ull;

const int maxn = 25;
ull n,k,f[maxn][maxn],sum[maxn][maxn],cur;
int d,lim[maxn];

ull dfs(int x) {
	if(!x)return 1;
	ull ans = 0;
	for(int i = 1;i < lim[x];++ i)
		ans += f[x][i];
	cur /= 10;
	if(x < d)ans += cur;
	return ans + dfs(x - 1);
}

ull ask(ull x) {
	if(x == 0)return 1; 
	d = 0;
	cur = x;
	memset(f , 0 , sizeof(f));
	for(ull m = x;m;m /= 10)lim[++ d] = m % 10;
	for(int i = 2;i <= d;++ i) {
		for(int j = i - 1;~ j;-- j) {
			for(int k = 1;k < 10;++ k) {
				f[i][k] += sum[j][9] + i - j - 1;
			}
		}
		for(int k = 1;k < 10;++ k)
			sum[i][k] = sum[i][k - 1] + f[i][k];
	}
	ull ans = 0;
	for(int i = 1;i < d;++ i)ans += sum[i][9];
	return ans + dfs(d) + (d > 1);
}

void work() {
	ull l = 0,r = n;
	while(l <= r) {
		ull mid = l + r >> 1;
		ull val;
		if(mid)val = ask(n) - ask(mid - 1);
		else val = ask(n); 
		if(val >= k)l = mid + 1;
		else r = mid - 1;
	}
	printf("%llu\n",r);
	return ;
}

int main() {
	freopen("whz_number.in","r",stdin);
	freopen("whz_number.out","w",stdout);
	while(~ scanf("%llu %llu",&n,&k)) {
		work();
	}
	return 0;
}