← 返回题目列表

Codeforces · 118/C

C. 花式号码

中文机器翻译题面 查看原题

Berland 的汽车号码恰好由 n 位数字组成。如果一个数字至少有 k 个相同的数字,则该数字被称为漂亮数字。 Vasya 想要更改他的汽车号码中的数字,使号码变得漂亮。要替换 n 位数字中的一位,Vasya 必须支付一笔钱,等于旧数字和新数字之间的绝对差。

帮助Vasya:找到他应该支付的最低金额,以使他的汽车号码变得漂亮。您还应该找到结果漂亮的数字。如果有多个这样的数字,则打印字典顺序最小的一个。

输入

第一行包含两个空格分隔的整数 n 和 k (2 ≤ n ≤ 104, 2 ≤ k ≤ n),它们表示该数字有多少位以及一个漂亮的数字应该有多少个相等的数字。第二行由n位数字组成。它描述了 Vasya 汽车的旧号码。保证号码不包含空格,只包含数字。

输出

在第一行打印 Vasya 需要更改号码的最低金额。在第二行打印汽车的新号码。如果有多个解决方案,请打印字典顺序最小的一个。

示例

输入 #1

6 5
898196

输出 #1

4
888188

输入 #2

3 2
533

输出 #2

0
533

输入 #3

10 6
0001112223

输出 #3

3
0000002223

注意

在第一个示例中,用“8”替换第二个数字的成本为 |9 - 8| = 1. 将第五位数字替换为“8”的成本相同。替换第六位数字的成本为 |6 - 8| = 2. 结果,Vasya 将为一个美丽的数字“888188”支付 1 + 1 + 2 = 4。

字符串的字典顺序比较是由现代编程语言中的 < 运算符执行的。如果存在这样的 i (1 ≤ i ≤ n),即 xi < yi,并且对于任何 j (1 ≤ j < i) xj = yj,则字符串 x 按字典顺序小于字符串 y。此问题中比较的字符串的长度始终为 n。