Дерево Хаффмана
Относительно простой метод сжатия данных может быть выполнен путём создания так называемых деревьев Хаффмана для файла и используется для его сжатия и распаковки данных в нём. Для большинства приложений используются бинарные деревья Хаффмана (например, каждый узел является либо листом, либо имеет ровно два подузла). Можно, однако, построить деревья Хаффмана с произвольным числом поддеревьев (например, троичных или, в общем случае, N-ичных деревьев).
Дерево Хаффмана для файла, содержащего Z разных символов имеет Z листьев. Путь от корня к листу, который представляет определенный символ, определяет кодировку, и каждый шаг на пути к листу определяет кодировку (которая может быть 0, 1, ..., (N-1)). Путём размещения часто встречающихся символы ближе к корню, и менее часто встречающихся символов дальше от корня, и достигается желаемое сжатие. Строго говоря, такое дерево будет деревом Хаффмана, только если в результате кодирования будет использовано минимальное число N-ичных символов для кодирования заданного файла.
В этой задаче мы будем рассматривать только деревья, где каждый узел является либо внутренним узлом либо листом кодирования символов и нет изолированных листьев, которые не кодируют символ.
На рисунке ниже показан пример троичного дерева Хаффмана, символы 'a' и 'е' кодируются с помощью одной троичного символа; менее часто встречающиеся символы 's' и 'p' кодируются с помощью двух троичных символов и наиболее редко встречающиеся символы 'x', 'q' и 'y' кодируются с помощью трех троичных символов каждый.
Конечно, если мы хотим, чтобы можно развернуть список N-ичных символов потом обратно, важно знать, какое дерево используется для сжатия данных. Это можно сделать несколькими способами. В этой задаче мы будем использовать следующий метод: потоку входных данных будет предшествовать заголовок, состоящий из закодированных значений символов Z, находящихся в исходном файле в лексикографическом порядке.
Зная количество входных символов Z, значение N, обозначающее "N-арность" дерева Хаффмана и сам заголовок, необходимо найти первичное значение закодированных символов.
Входные данные
Входные данные начинаются с целого числа T, расположенного в отдельной строке и обозначающего количество последующих тестовых случаев. Далее задано каждый из T тестовых случаев, каждый из которых расположен в 3-х строках следующим образом:
Количество различных символов в тестовом случае Z (2 ≤ Z ≤ 20);
Число N, обозначающее " N -арность" дерева Хаффмана (2 ≤ N ≤ 10);
Строка, представляющая заголовок полученного сообщения, каждый символ будет цифрой в диапазоне [0, (N-1)]. Эта строка будет содержать меньше 200 символов.
Примечание: Хотя и редко, но это возможно для заголовка, чтобы иметь несколько толкований при расшифровке (например, для заголовка '010011101100', и значениях Z = 5 и N = 2). Гарантируется, что во всех предлагаемых во входных данных тестовых случаях, имеется единственное решение.
Выходные данные
Для каждого из T тестовых случаев вывести Z строк, дающих декодированную версию каждого из Z символов в порядке возрастания. Используйте формат оригинал->кодировка, где оригинал – это десятичное число в диапазоне [0, (Z-1)] и соответствующая кодированная строка кодированных цифр для этих символов (каждая цифра ≥ 0 и < N).