[ZOJ2599]高级字典序

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file Lexicographical.in Output file Lexicographical.out

【题目描述】

考虑1到n的整数。我们把一个整数的各位数字和叫做其权值。记x的权值为w(x)。

现在我们把这些数字按照被称作“高级字典序”的顺序排序。考虑两个整数a和b。如果w(a)<w(b)那么在高级字典序中,a在b之前。如果w(a)=w(b),那么在高级字典序中a位于b之前的充要条件是在十进制下a的字典序比b的字典序小。

让我们考虑一些例子。

注:以下的“<”均指在高级字典序中,前者位于后者之前。

120 < 4,因为w(120) = 1 + 2 + 0 = 3 < 4 = w(4).

555 < 78,因为w(555) = 15 = w(78),并且“555”的字典序比“78”小。

20 < 200, 因为w(20) = 2 = w(200)并且“20”的字典序比“200”小。

给出n和一个整数k,找到k在1~n的高级字典序中排第几个,以及1~n的高级字典序中第k小的数。

【输入格式】

一行两个整数n,k(1<=k<=n<=10^18)。

【输出格式】

两个整数:k在1~n高级字典序中的位置,以及1~n高级字典序中的第k个数。

【样例输入】

20 10

【样例输出】

2 14

【提示】

这里的输入格式和ZOJ原题略有不同。

【来源】

ZOJ 2599 Graduated Lexicographical Ordering

Author: Andrew Stankevich

Source: Andrew Stankevich's Contest #6