题解

思路

对每个数 $x$ 记 $S_x$ 为写有 $x$ 的卡片集合。

做法

一对 $x,y$ 不能被任何卡片区分，当且仅当 $S_x=S_y$，所以题目条件等价于 $S_1,S_2,\ldots,S_K$ 两两不同。卡片集合只有 $2^N$ 种，因此 $K>2^N$ 时无解。若记 $c_x=|S_x|$，总代价为 $\sum c_x\operatorname{len}(x)$；大小为 $s$ 的不同集合恰有 $\binom Ns$ 个。根据交换论证，若位数较多的数反而分配了较大的集合，交换两者不会使代价变大；故应将集合大小按 $0,1,2,\ldots$ 的顺序，依次分配给 $K,K-1,\ldots,1$。

从 $s=0$ 开始递推二项式系数 $\binom Ns$，每次取尚未分配数量与 $\binom Ns$ 的较小值，把当前的 $s$ 乘上这些最大标签的十进制位数并累加。系数达到 $K$ 后即可截断，避免溢出；遍历完 $s=0,1,\ldots,N$ 仍有标签未分配则输出 $-1$。

复杂度

在题目给定的上界下，总时间复杂度为 $O(\sum(N+K))$，额外空间复杂度为 $O(1)$。