4161: 「NOI2015」荷马史诗
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
> 追逐影子的人，自己就是影子。 ——荷马
Allison 最近迷上了文学。她喜欢在一个慵懒的午后，细细地品上一杯卡布奇诺，静静地阅读她爱不释手的《荷马史诗》。但是由《奥德赛》和《伊利亚特》组成的鸿篇巨制《荷马史诗》实在是太长了，Allison 想通过一种编码方式使得它变得短一些。
一部《荷马史诗》中有 $n$ 种不同的单词，从 $1$ 到 $n$ 进行编号。其中第 $i$ 种单词出现的总次数为 $w_i$。Allison 想要用 $k$ 进制串 $s_i$ 来替换第 $i$ 种单词，使得其满足如下要求：
对于任意的 $1 \leq i,j \leq n, \ i \neq j$，都有：$s_i$ 不是 $s_j$ 的前缀。
现在 Allison 想要知道，如何选择 $s_i$，才能使替换以后得到的新的《荷马史诗》长度最小。在确保总长度最小的情况下，Allison 还想知道最长的 $s_i$ 的最短长度是多少？
一些定义：
一个字符串被称为 $k$ 进制字符串，当且仅当它的每个字符是 $0$ 到 $k−1$ 之间（包括 $0$ 和 $k−1$）的整数。
字符串 $\text{Str}_1$ 被称为字符串 $\text{Str}_2$ 的前缀，当且仅当：存在 $1 \leq t \leq m$，使得 $\text{Str}_1=\text{Str}_2[1 \ldots t]$。其中，$m$ 是字符串 $\text{Str}_2$ 的长度，$\text{Str}_2[1 \ldots t]$ 表示 $\text{Str}_2$ 的前 $t$ 个字符组成的字符串。
输入
输入文件的第一行包含两个正整数 $n,k$，中间用单个空格隔开，表示共有 $n$ 种单词，需要使用 $k$ 进制字符串进行替换。
接下来 $n$ 行，第 $i+1$ 行包含 $1$ 个非负整数 $w_i$，表示第 $i$ 种单词的出现次数。
输出
输出文件包括两行。
第一行输出一个整数，为《荷马史诗》经过重新编码以后的最短长度。
第二行输出一个整数，为保证最短总长度的情况下，最长字符串 $s_i$ 的最短长度。
样例输入 复制
4 2
1
1
2
2样例输出 复制
12
2提示
输入样例2
6 3 1 1 3 3 9 9
输出样例2
36 3
数据范围： #### 限制与约定 | Case # | $n$ 的规模 | $k$ 的规模 | 附加限制 | |:-:|:-:|:-:|:-:| | 1 | $n = 3$ | $k = 2$ | - | | 2 | $n = 5$ | $k = 2$ | - | | 3 | $n = 16$ | $k = 2$ | 所有 $w_i$ 均相等 | | 4 | $n = 1000$ | $k = 2$ | $w_i$ 在取值范围内均匀随机 | | 5 | $n = 1000$ | $k = 2$ | - | | 6 | $n = 100000$ | $k = 2$ | - | | 7 | $n = 100000$ | $k = 2$ | 所有 $w_i$ 均相等 | | 8 | $n = 100000$ | $k = 2$ | - | | 9 | $n = 7$ | $k = 3$ | - | | 10 | $n = 16$ | $k = 3$ | 所有 $w_i$ 均相等 | | 11 | $n = 1001$ | $k = 3$ | 所有 $w_i$ 均相等 | | 12 | $n = 99999$ | $k = 4$ | 所有 $w_i$ 均相等 | | 13 | $n = 100000$ | $k = 4$ | - | | 14 | $n = 100000$ | $k = 4$ | - | | 15 | $n = 1000$ | $k = 5$ | - | | 16 | $n = 100000$ | $k = 7$ | $w_i$ 在取值范围内均匀随机 | | 17 | $n = 100000$ | $k = 7$ | - | | 18 | $n = 100000$ | $k = 8$ | $w_i$ 在取值范围内均匀随机 | | 19 | $n = 100000$ | $k = 9$ | - | | 20 | $n = 100000$ | $k = 9$ | - | 对于所有数据，保证 $2 \leq n \leq 100000, \ 2 \leq k \leq 9, \ 0 \lt w_i \leq 10^{11}$。选手请注意使用 $64$ 位整数进行输入输出、存储和计算。 #### 评分方式 对于每个测试点： 若输出文件的第 $1$ 行正确，得到该测试点 $40\%$ 的分数； 若输出文件完全正确，得到该测试点 $100\%$ 的分数。