#P16067. [2022国家队训练南京站]毒假强

    ID: 15278 传统题 1000ms 1024MiB 尝试: 5 已通过: 1 难度: 10 上传者: 标签>CF2900省选/NOI-数位 DP轮廓线 DP阈值划分大小情况字典序排名与反排名滚动数组

[2022国家队训练南京站]毒假强

题目描述

对于正整数 kk,定义毒假强数 xx 满足:

x×(10k−1)x\times(10^k-1)

的十进制表示中不包含数字 99。

请你求出第 nn 个毒假强数。

输入格式

一行两个整数 k,nk,n。

输出格式

一行一个整数,表示第 nn 个毒假强数。

样例一

输入

1 8

输出

9

样例二

输入

5 84

输出

11235

数据范围与提示

子任务编号 k≤k\le n≤n\le 分值
1 3 1000 25
2 1 101810^{18} 35
3 18 40

对于所有数据,满足:

1≤k≤18,1≤n≤1018.1\le k\le 18,\qquad 1\le n\le 10^{18}.