4034 - 哈夫曼编码
时间限制 : 1 秒
内存限制 : 128 MB
给定一个文本中n个字符的出现频率。设计n个字符的哈夫曼编码。
题目输入
输入包括多组数据。每组数据的第一行是一个整数n(1 <= n <= 100)，代表不同字符的总数，n = 0意味着输入结束；接下来有n行，其中的每一行包含一个字符及其出现频率。
题目输出
对每组数据，输出哈夫曼编码的平均位数，即l1 * f1 + l2 * f2 + ... + ln * fn，其中li是第i个字符的哈夫曼编码的位数，fi是第i个字符出现的频率。
输入/输出样例
输入格式
5 A 35 B 10 C 20 D 20 _ 15 3 x 20 Y 50 Z 5 0
输出格式
225 100