Huffman Trees#3231
A relatively simple method for compressing data works by creating a so-called Huffman tree for a file and using it to compress and decompress the data it contains. For most applications, binary Huffman trees are used (that is, each node is either a leaf or has exactly two sub-nodes). However, one can construct Huffman trees with an arbitrary number of sub-trees (for example, ternary or, in general, -ary trees).
A Huffman tree for a file containing different characters has leaves. The path from the root to a leaf that represents a certain character determines its encoding; each step towards the leaf determines an encoding character (which can be , , ..., N-1). By placing frequently occurring characters closer to the root, and less frequent characters further from the root, better compression is achieved. Strictly speaking, such a tree is a Huffman tree only if the resulting encoding uses the minimal number of -ary symbols to encode the complete file.
For this problem, we only consider trees where each node is either an internal node or a leaf encoding a character; there are no leaves that do not encode any character.
The figure below shows a sample ternary Huffman tree. The characters 'a' and 'e' are encoded using one ternary symbol; the less frequent characters 's' and 'p' are encoded using two ternary symbols; and the rarest characters 'x', 'q', and 'y' are each encoded using three ternary symbols.
Of course, if we want to later decompress a sequence of -ary symbols, it is important to know which tree was used for the compression. This can be done in several ways. In this problem, we use the following method: the stream of data is preceded by a header consisting of the encoded representations of the characters occurring in the original file, in lexicographical order.
Given the number of source symbols , a value denoting the arity of the Huffman tree, and a header, reconstruct the mapping from source symbols to encoded strings.
The input starts with a single integer on a separate line, denoting the number of test cases. Then, for each of the test cases, three lines follow:
The number of different characters (2 \leq Z \leq 20);
The degree (arity) of the Huffman tree (2 \leq N \leq 10);
A string representing the header of the received message. Each character in this string is a digit in the range [0, N-1]. This string will contain fewer than characters.
Note: Although rare, it is possible for a header to allow multiple decodings (for example, the header '010011101100' for Z = 5 and N = 2). It is guaranteed that each test case in the input has a unique solution.
For each test case, print lines, each giving the decoded mapping for one of the characters in ascending order (from to Z-1). Use the format original->encoding, where original is a decimal value in the range [0, Z-1] and is the string of encoding digits for this character (each digit is and ).
Example 1