logo AlgoBeat OnlineJudge
登录 注册

#101261. [BZOJ 1261] [SCOI2006]zh_tree

内存限制:162 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

张老师根据自己工作的需要,设计了一种特殊的二叉搜索树。他把这种二叉树起名为 zh_tree,对于具有 个结点的 zh_tree,其中序遍历恰好为 ,其中数字 是每个结点的编号。 个结点恰好对应于一组学术论文中出现的n个不同的单词。第 个单词在该组论文中出现的次数记为 ,例如, 表示第 个结点所对应的单词在该组论文中出现了 次。

设该组论文中出现的单词总数为 ,显然,。记 为第 个单词在该组论文中出现的概率(频率)。 张老师把根结点深度规定为 ,如果第 个结点的深度为 ,则访问该结点的代价 ,其中 为已知的不超过 的正常数。 则 zh_tree 是满足以下条件的一棵二叉树:它使 达到最小。我们称上式为访问zh_tree的平均代价。

请你根据已知数据为张老师设计一棵 zh_tree。

输入格式

行: 个用空格隔开的正数:

其中 ,为整数。 为不超过 的正实数。

行: 个用空格隔开的正整数,为每个单词出现的次数(次数 )。

输出格式

行:( 分)一个正实数,保留 位小数,为访问 Zh_tree 的最小平均代价。

行:( 分) 个用空格隔开的整数,为该树的前序遍历。一般地,作为最优解的前序遍历不一定唯一,只输出一个解。

样例输入

4 2 3.520 30 50 20

样例输出

7.000