Description

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.

Input Format

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 Format

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

4 2 3.5
20 30 50 20

7.000

Hint

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