Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1646. DeHuff
Грамматики, рекурсивный разборОлимпиадные задачи на английском языке
| 04/07/2011 | Лето 2011 - дорешивание (13E) |
| 20/07/2011 | Лето 2011 - 13 (E) |
Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Computer Science students know that a character is stored internally as a code, i.e. a bit
string, usually fixed-length and prescribed by some standard, e.g. ASCII or Unicode. In a Huffman
code, each character is stored as a code, but the lengths of the codes are not fixed, they vary
(preferring shorter codes for the most frequently used characters to increase compression). To
facilitate decoding a sequence of contiguously-stored Huffman codes into a string of characters
without boundary ambiguity, Huffman codes satisfy the prefix property — no character code is a
prefix of any other character code. For example, character strings over the alphabet {a, b, c, d}
could be stored internally using the Huffman code {a = 00, b = 010, c = 011, d = 1}, which has
the prefix property.
Because of the prefix property, a Huffman code can be represented as a Huffman tree – a binary tree
whose leaves are the alphabet characters and whose left and right branches are (implicitly) labeled
0 and 1, respectively. The leaves of a Huffman tree are arranged so that the code of a character is
read as the string of branch labels leading from the root to the leaf. Write a program that inputs
a Huffman tree (representing a Huffman code) and a bit string consisting of contiguously stored
character codes, and decodes the bit string into its corresponding string of characters, which is
output.
Input
The first line contains a Huffman tree. If a tree is a single leaf, it appears as a single character, which
is a lowercase latin letter; otherwise, if it has subtrees, it appears as a left parenthesis, followed by the
left Huffman subtree, followed by a comma, followed by the right Huffman subtree, followed by a right parenthesis.
You can assume every non-leaf tree has two non-empty subtrees. The subsequent lines each contain a nonempty
binary string to be decoded.
Output
For each of the binary strings to be decoded, print the string of characters that the binary string
represents.
Sample Input
((a,(b,c)),d) 0101011001101001100 000110110011010101000011
Sample Output
bdcaddbca accaddbdbac
