9068:哈夫曼编码

Time/Memory Limit:1000 MS/32768 K
Submitted: 630 Accepted: 387

 Problem Description

由若干个值无重复的结点及其权值,建立相应的哈夫曼树。在合并过程中,若出现权值相同的情况,则优先选取编号小的进行合并;要求哈夫曼树中所有左孩子编号小于右孩子编号(以结点的输入顺序做为其编号)。对所建的哈夫曼树,根据左0右1的原则,对各结点进行编码。设计一个算法,对给定的若干码串进行相应的解码,并输出解码结果。 

 Input

有多组测试数据,每组数据由结点信息和码串两部分组成。结点信息部分的第一行为一个整数n(n<=20),表示以下有n个结点信息,每个结点信息包括一个字符和一个整数,表示结点值和权值;码串部分的第一行为一个整数m,表示以下有m个码串(每个串长不超过100),码串由0和1构成,且均有效。

 Output

输出各码串对应的解码结果,每个解码结果占一行,每组测试数据后有一空行。

 Sample Input

4
A7
G5
O2
D4
2
10110110111
11111010

 Sample Output

GOOD
DOG

 Author

hwt

 Recommend

zh