程序设计能力实训

1256. 小香浓范诺编码

单点时限: 2.0 sec

内存限制: 256 MB

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

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

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

输入格式

第 $1$ 行:整数 $T$ ($1 \le T \le 10$) 为测试数据组数。

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

第一行:一个整数n,表示输入信元个,$1\lt n \le 200$。

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

输出格式

对于每组测试数据,输出一行问题的编号($0$ 开始编号,格式: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
不限期开放

题目列表