练习专区

今天的一小步就是明天的一大步

Problem 1288 哈夫曼编码................数构

Accepted: 0 Total Submit: 2
Time Limit: 1000ms Memory Limit: 30720KB

Description

有一个仓库要为存放的n种物品定编码，这n种物品进出的频率大不相同，为了让操作编码的动作最少，请你编程设计它们的编码，并求码长的和。

Input

输入有若干行，每行是一个仓库的情况。每行的第一个正整数n表示要编码的物品有n种，接着有n个小于1的正数，各表示相应物品的进出仓的频率。

Output

每个仓库的情况输出一行，输出这些物品所使用编码的长度和。格式见样例。

Sample Input

7 0.40 0.30 0.15 0.05 0.04 0.03 0.03
2 0.40 0.60
1 0.90
5 0.20 0.20 0.20 0.20 0.20
4 0.30 0.20 0.20 0.4

Sample Output

Case 1:26
Case 2:2
Case 3:1
Case 4:12
Case 5:8

Hint

提交　　　　　返回