eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Дерево Хаффмана

Дерево Хаффмана

Ліміт часу 3 секунди
Ліміт використання пам'яті 32 MiB

Відносно простий метод стиснення даних може бути виконаний шляхом створення так званих дерев Хаффмана для файла і використовується для його стисненн та розпаковки даних у ньому. Для більшості додатків використовуються бінарні дерева Хаффмана (наприклад, кожен вузол є або листком, або має рввно два підвузла). Можна, проте, побудувати дерева Хаффмана з довільним числом піддерев (наприклад, трійкових або, у загальному випадку, N-кових дерев).

Дерево Хаффмана для файла, який містить Z різних символів має Z листків. Шлях від кореня до листка, який подає певний символ, визначає кодування, і кожен крок на шляху до листка визначає кодування (яке може бути 0, 1, ..., (N-1)). Шляхом розміщення символів, які частіше зустрічаються, ближче до кореня, і символів, які рідше зустрічаються, подалі від кореня, і досягається бажане стиснення. Строго кажучи, таке дерево буде деревом Хаффмана, лише якщо у результаті кодування буде використано мінімальну кількість N-кових символів для кодування заданого файлу.

У цій задачі ми будемо розглядати лише дерева, у яких кожен вузол є або внутрішнім вузлом або листком кодування символів і немає ізольованих листків, які не кодують символ.

На рисунку нижче показано приклад трійкового дерева Хаффмана, символи 'a' та 'е' кодуються за допомогою одного трійкового символа; символи, які зустрічаються менш часто, 's' та 'p', кодуються за допомогою двох трійкови символів і символи, які найбільш рідко зустрічаютьщиеся, 'x', 'q' та 'y', кодуються за допомогою трьох трійкових символів кожен.

Звичайно, якщо ми хочемо, щоб можна було рогорнути список N-кових символів потім назад, важливо знати, яке дерево використовується для стиснення даних. Це можна зробити декількома способами. У цій задачі ми будемо викорситовувати наступний метод: потоку вхідних даних буде передувати заголовок, який складається з закодованих значень символів Z, які знаходяться у заданому файлі у лексикографічному порядку.

Знаючи кількість вхідних символів Z, значення N, яке позначає "N-арність" дерева Хаффмана та сам заголовок, необхідно знайти початкове значення закодованих символів.

Вхідні дані

Вхідні дані починаються з цілого числа T, розміщеного у окремому рядку і яке позначає кількість наступних тестових випадків. Далі задано кожен з T тестових випадків, кожен з яких розміщено у 3-х рядках наступним чином:

  • Кількість різних символів у тестовому випадку Z (2Z20);

  • Число N, яке позначає " N -арність" дерева Хаффмана (2N10);

  • Рядок, який подає заголовок отриманого повідомлення, кожен символ буде цифрою у діапазоні [0, (N-1)]. Цей рядок буде містити менше 200 символів.

Примітка: Хоча й рідко, але це можливо для заголовку, що буде декілька тлумачень при розшифровці (наприклад, для заголовку '010011101100', та значеннях Z = 5 і N = 2). Гарантується, що у всіх пропонованих у вхідних даних тестових випадках, існує єдиний розв'язок.

Вихідні дані

Для кожного з T тестових випадків вивести Z рядків, які дають декодовану версію кожного з Z символів у порядку зростання. Використовуйте формат оригінал->кодування, де оригінал – це десяткове число у діапазоні [0, (Z-1)] і відповідний кодований рядок кодованих цифр для цих символів (кожна цифра ≥ 0 і < N).

Приклад

Вхідні дані #1
3 
3 
2 
10011 
4 
2 
000111010 
19 
10 
01234678950515253545556575859
Вихідні дані #1
0->10
1->0
2->11
0->00
1->011
2->1
3->010
0->0
1->1
2->2
3->3
4->4
5->6
6->7
7->8
8->9
9->50
10->51
11->52
12->53
13->54
14->55
15->56
16->57
17->58
18->59
Джерело ACM ICPC NWERC 2002