PROGRAMMING:Optimal binary search tree
Let $$s = \ {x}_ 1,x_ 2,...,x_ N \} $$is an ordered set, and $$X_ 11. Find $$x = x in the inner node of binary search tree_ Let the probability of this case be $$P_ i$$
2. In the leaf node of binary search tree, determine $$X / in (x)_ i,x_{ I + 1}) $$(that is, the virtual node is found). Let the probability of this case be $$Q_ i$$
Set the depth of the root node to 0, and store the element $$X_ The node depth of I $$is $$C_ I $$, leaf node $$(x)_ j,x_{ J + 1}) $$node depth is $$d_ J $$, the average number of comparisons needed for a search in the binary search tree is $$M $$, then there is a formula:
$$
m=\sum_{ i=1}^np_ i(1+c_ i)+\sum^n_{ j=0}q_ jd_ j
$$
The average path length of $$M $$is also called binary search tree $$t $. The requirement of this problem is for the ordered set $$s $$and its access probability distribution $$(q)_ 0,p_ 1,q_ 1,..,p_ n,q_ n) In this paper, a binary search tree with the minimum average path length is found among all binary search trees representing the ordered set $$s $.
###Input format:
The first line gives the number of elements n (2 < n < 10) in the ordered set
The second line gives the access probability distribution of inner node (real node) $$P_ 1,..,p_ n$$
The third line gives the access probability distribution of leaf node (virtual node) $$Q_ 0,q_ 1,..,q_ n$$
###Output format:
The first line outputs the minimum $$M $$, retaining two decimal places.
The second line traverses the output binary tree first, and outputs its number for the real node, and '.', for the virtual node. There is a space after each symbol. If there are multiple binary trees that meet the requirements, the number of the root node is the smallest.
###Input example:
```in
three
0.50 0.1 0.05
0.15 0.1 0.05 0.05
```
###Output example:
```out
one point five zero
1 . 2 . 3 . .
```
answer：If there is no answer, please comment
2. In the leaf node of binary search tree, determine $$X / in (x)_ i,x_{ I + 1}) $$(that is, the virtual node is found). Let the probability of this case be $$Q_ i$$
Set the depth of the root node to 0, and store the element $$X_ The node depth of I $$is $$C_ I $$, leaf node $$(x)_ j,x_{ J + 1}) $$node depth is $$d_ J $$, the average number of comparisons needed for a search in the binary search tree is $$M $$, then there is a formula:
$$
m=\sum_{ i=1}^np_ i(1+c_ i)+\sum^n_{ j=0}q_ jd_ j
$$
The average path length of $$M $$is also called binary search tree $$t $. The requirement of this problem is for the ordered set $$s $$and its access probability distribution $$(q)_ 0,p_ 1,q_ 1,..,p_ n,q_ n) In this paper, a binary search tree with the minimum average path length is found among all binary search trees representing the ordered set $$s $.
###Input format:
The first line gives the number of elements n (2 < n < 10) in the ordered set
The second line gives the access probability distribution of inner node (real node) $$P_ 1,..,p_ n$$
The third line gives the access probability distribution of leaf node (virtual node) $$Q_ 0,q_ 1,..,q_ n$$
###Output format:
The first line outputs the minimum $$M $$, retaining two decimal places.
The second line traverses the output binary tree first, and outputs its number for the real node, and '.', for the virtual node. There is a space after each symbol. If there are multiple binary trees that meet the requirements, the number of the root node is the smallest.
###Input example:
```in
three
0.50 0.1 0.05
0.15 0.1 0.05 0.05
```
###Output example:
```out
one point five zero
1 . 2 . 3 . .
```
answer：If there is no answer, please comment