P4539 [SCOI2006] zh_tree

Teacher Zhang designed a special binary search tree for his work. He named this binary tree zh_tree. For a zh_tree with $n$ nodes, its inorder traversal is exactly $(1, 2, 3, \cdots, n)$, where the numbers $1, 2, 3, \cdots, n$ are the identifiers of the nodes. The $n$ nodes correspond to $n$ distinct words that appear in a set of academic papers. Let the $j$-th word appear $d_j$ times; for example, $d_2 = 10$ means that the word corresponding to node $2$ appears $10$ times. Let $S$ be the total number of word occurrences in this set of papers. Obviously, $S = d_1 + d_2 + \cdots + d_n$. Define $f_j = \frac{d_j}{S}$ as the probability (frequency) of the $j$-th word. The root node has depth $0$. If node $j$ has depth $r$, then its access cost $h_j$ is $h_j = k (r + 1) + c$, where $k$ and $c$ are known positive constants not exceeding $100$. A zh_tree is a binary tree that minimizes $h_1 f_1 + h_2 f_2 + \cdots + h_n f_n$. We call the expression above the average access cost of the zh_tree. Please design a zh_tree based on the given data.

Line 1: Three positive numbers separated by spaces: $n, k, c$, where $n < 30$ is an integer. $k$ and $c$ are positive real numbers not exceeding $100$. Line 2: $n$ positive integers separated by spaces, the occurrence counts for each word (each count $< 200$).

Output one positive real number on a single line, rounded to $3$ decimal places: the minimal average access cost of the zh_tree.

The original problem also required constructing the tree and outputting its inorder traversal. For various reasons, we removed that second requirement to keep compatibility with existing solutions and code. Translated by ChatGPT 5