Problem 3834 --Haffman编码

3834: Haffman编码

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 16  Solved: 9
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][20kb]

Description

哈弗曼编码大家一定很熟悉吧(不熟悉也没关系,自己查去。。。)。现在给你一串字符以及它们所对应的权值,让你构造哈弗曼树,从而确定每个字符的哈弗曼编码。当然,这里有一些小规定:

1.规定哈弗曼树的左子树编码为0,右子树编码为1;

2.若两个字符权值相同,则ASCII码值小的字符为左孩子,大的为右孩子;

3.创建的新节点所代表的字符与它的做孩子的字符相同;

4.所有字符为ASCII码表上32-96之间的字符(即“ ”到“`”之间的字符)。

Input

输入包含多组数据(不超过100组)
每组数据第一行一个整数n,表示字符个数。接下来n行,每行有一个字符ch和一个整数weight,表示字符ch所对应的权值,中间用空格隔开。
输入数据保证每组测试数据的字符不会重复。

Output

对于每组测试数据,按照输入顺序输出相应的字符以及它们的哈弗曼编码结果,具体格式见样例。

Sample Input

3
a 10
b 5
c 8
4
a 1
b 1
c 1
d 1

Sample Output

a:0
b:10
c:11
a:00
b:01
c:10
d:11

HINT

Source

[Submit][Status]