程序设计能力实训

1256. 小香浓范诺编码

单点时限: 2.0 sec

内存限制: 256 MB

给定一组信元符号出现的频率,按照从小到大的顺序排好,将信源符号分化为两大组,使两组的频率和近于相同,并各赋予一个二元码符号01。只要组内有两个或两个以上符号,就以同样的方法重复以上分组,以此确定这些符号的连续编码数字。依次下去,直至每一组只剩下一个信源符号为止,按照信元所在分组的赋值顺序组合成为该信元的编码,分组过程中不调整信元次序。

例如,输入四个信元的频次分别为,先分为:一组和另一组(差值为,最小),给排在前面的一组赋,后面的一组赋,第二组为一个信元,只剩下一个信元,所以它的编码就是1,对第一组继续按照和接近相同分组,分为第一组为,第二组为(差值为,最小),第一组赋值,第二组赋值,因此的编码是01,再对第一组分组,第一组,第二组(差值为,最小),第一组赋,第二组赋;因此,的编码为:000的编码为001

注意:如果输入四个信元的频次分别为,那么两组差值相等,我们以为一组,为一组为准。如果存在两个分割方式使得两个组差值相等,那么以第一个组元素个数少为准。

输入格式

行:整数 () 为测试数据组数。

每组测试数据按如下格式输入:

第一行:一个整数n,表示输入信元个,

第二行:个整数,从小到大排序的,整数为int类型范围。

输出格式

对于每组测试数据,输出一行问题的编号( 开始编号,格式:case #0: 等),然后按照输入的顺序输出相应频次和信元编码,两个数之间用 : 分隔,每行一个。

样例

Input
3
2
0 1
4
2 4 8 16
6
20 20 20 20 20 20
Output
case #0:
0:0
1:1
case #1:
2:000
4:001
8:01
16:1
case #2:
20:00
20:010
20:011
20:10
20:110
20:111
不限期开放

题目列表