SP10444 CODING2 - Coding

对于一个包含 $2^N$ 个符号的字母表，我们可以使用二进制来编码，这种编码是这些符号与等数量的二进制码字之间的一一对应关系。例如，下表展示了对于四个符号（**a**、**b**、**c**、**d**）的三种不同二进制编码方式： | 符号 | 编码 1 | 编码 2 | 编码 3 | |------|--------|--------|--------| | a | 00 | 0 | 1 | | b | 01 | 10 | 10 | | c | 10 | 110 | 100 | | d | 11 | 111 | 1000 | 无前缀编码是指没有一个码字是其他码字的前缀。表中的编码 1 和编码 2 是无前缀编码，而编码 3 则不是。无前缀编码因其简化了编码和解码过程而被广泛采用。 这个问题要求你在给定 **N** 和一条长度为 **M** 的符号信息的情况下，找出一个适用于整个字母表（包括消息中未出现的符号）的无前缀编码，使得编码该信息所需的比特数最小。例如，当 **N**=2，符号为（a, b, c, d），而消息是 “a a a a b b b b a a a a c c d d”时： 使用编码 1 和编码 2 分别对消息进行编码的结果是： - 00 00 00 00 01 01 01 01 00 00 00 00 10 10 11 11，共计 32 比特。 - 0 0 0 0 10 10 10 10 0 0 0 0 110 110 111 111，总计 28 比特。 可以证明，无法使用少于 28 比特的无前缀编码来处理上述消息。

输入包含若干测试用例。每个测试用例由两行组成。第一行包含两个整数 **N** 和 **M**（1 ≤ N ≤ M），用单个空格隔开。第二行包含 **M** 个整数 **X $_{i}$**，其范围为 0 至 $2^N$ - 1，表示待编码的消息。输入以 **N**=**M**=0 结束，这种情况下不需要处理。

对于每个测试用例，输出一行，表示使用无前缀编码表示消息所需的最少比特数。 **本翻译由 AI 自动生成**