| 题目名称 | 1620. [ZOJ 2599]高级字典序 |
|---|---|
| 输入输出 | Lexicographical.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 20 |
| 题目来源 |
 cstdio
于2014-05-06加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：3， 提交：12， 通过率：25% | ||||
 mikumikumi |
100 | 0.117 s | 0.31 MiB | C++ |
|
张灵犀不和我一般见识真可怕呢（笑 |
100 | 0.118 s | 0.31 MiB | C++ |
 cstdio |
100 | 0.130 s | 0.29 MiB | C++ |
|
张灵犀不和我一般见识真可怕呢（笑 |
95 | 1.066 s | 0.33 MiB | C++ |
|
张灵犀不和我一般见识真可怕呢（笑 |
95 | 1.076 s | 0.26 MiB | C++ |
|
张灵犀不和我一般见识真可怕呢（笑 |
60 | 0.056 s | 0.31 MiB | C++ |
|
张灵犀不和我一般见识真可怕呢（笑 |
60 | 0.063 s | 0.30 MiB | C++ |
|
张灵犀不和我一般见识真可怕呢（笑 |
60 | 0.321 s | 0.28 MiB | C++ |
|
张灵犀不和我一般见识真可怕呢（笑 |
60 | 1.046 s | 0.33 MiB | C++ |
|
张灵犀不和我一般见识真可怕呢（笑 |
45 | 0.066 s | 0.33 MiB | C++ |
| 关于 高级字典序 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
第一次见到卡unsigned long long与 long long的，丧心病狂
| ||||
1620. [ZOJ 2599]高级字典序
★★★ 输入文件：Lexicographical.in
输出文件：Lexicographical.out
简单对比时间限制：1 s 内存限制：256 MiB
【题目描述】
考虑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