[ZOJ2599]高级字典序

成绩 开启时间 2014年09月19日 星期五 10:08
折扣 0.8 折扣时间 2014年09月26日 星期五 10:08
允许迟交 是 关闭时间 2014年09月26日 星期五 10:08
输入文件 Lexicographical.in 输出文件 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