数位合并的最大值与最小值¶
预估时间限制：0.5 秒。内存限制：128 MB。
实际时限以标准程序在目标环境的最慢用例中位时间乘以 \(2\) ，按 \(0.5\) 秒向上取整。参考环境见评测说明。
背景故事¶
一座数字展馆有一块可合并数位的显示板。管理员希望知道，只操作一次，显示的数最大和最小能变成多少。
(本故事由GPT-6重写)
形式化问题描述¶
给定一个有 \(n\) 位的 \(k\) 进制正整数，数位从高到低为 \(a_1,\ldots,a_n\) .恰好选择一次两个位置 \(i<j\) ，令 \(s=a_i+a_j\) ，并同时执行以下操作：
- 若 \(s\ge k\) ，将位置 \(i\) 的数字改为一、位置 \(j\) 的数字改为 \(s-k\) ，其他位置不变。
- 若 \(s<k\) ，删除位置 \(i\) ，将原位置 \(j\) 的数字改为 \(s\) .其余数位保持相对顺序。删除数位会缩短数字，并非把该位改成零。
最后删除所有前导零。分别求可能得到的最大整数和最小整数。两项答案可以使用不同的两个位置。
输入格式¶
第一行两个整数 \(n,k\) .第二行 \(n\) 个以十进制书写、用空格分隔的整数 \(a_1,\ldots,a_n\) ，其中 \(a_1\) 是最高位。
输出格式¶
输出两行，依次表示最大值和最小值。每行从高到低输出结果的各个 \(k\) 进制数位；每个数位以十进制整数书写，相邻数位用一个空格分隔，不输出前导零。
样例¶
样例 1¶
输入¶
4 10
1 8 9 9
输出¶
1 8 9 0
9 9 9
样例 2¶
输入¶
5 10
7 0 0 1 1
输出¶
7 0 1 1
1 8
样例 3¶
输入¶
3 10
1 2 3
输出¶
3 3
1 5
样例解释¶
样例一最大值合并第一位和第四位，原来的最高位一保持不变，最低位变成零。最小值合并第一位和第二位，得到三个九。样例二的最小值合并第一位与第五位，删除最高位和随后的两个前导零，得到 \(1,8\) .样例三没有任何数位对会进位。
数据范围与保证¶
\(2\le n\le10^6\) , \(2\le k\le10^9\) , \(1\le a_1<k\) , \(0\le a_i<k\) . 输入字符总数不超过 \(21\times10^6\) .
| 分值比例 | 额外条件 |
|---|---|
| 100% | 无额外条件 |