#P1554. 新的词典序

    ID: 566 传统题 1000ms 512MiB 尝试: 21 已通过: 8 难度: 7 上传者: 标签>CF2200提高数位 DP上界限制状态Trie 上第 k 小HNOI2009集训Day7

新的词典序

题目描述

定义一个新的比较大小的规则:

1、第一关键字为各位数字之和;

2、第二关键字为字符序。

例如:

120<4120<4 因为 1+2+0<41+2+0<4;

555<78555<78,因为 5+5+5=15=7+85+5+5=15=7+8,而 555555 的字符序小于 7878;

20<20020<200,因为 2+0=2+0+02+0=2+0+0,而 2020 的字符序小于 200200。

现在要你求 11 到 nn 中 kk 是第几大的,第 kk 大的是几。

输入格式

本题有多组数据。

每组数据有 nn 和 kk,当 n=k=0n=k=0 时结束读入。

输出格式

对于每组输入,输出一组 11 到 nn 中 kk 是第几大的和第 kk 大的是几。

样例输入

20 10
0 0	

样例输出

2 14

数据范围:

数据保证数据组数最多只有 2020 组。

对于 30%30\% 的数据,1≤k≤n≤1051 \leq k \leq n \leq 10^5;

对于 100%100\% 的数据,1≤k≤n≤10181 \leq k \leq n \leq 10^{18}。

题目来源

HNOI2009 集训 Day7。