Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб. Question by Ibrahim Mesecan.
Total Access Cost of a BST
A binary search tree is a binary tree where each node
can have at most two children: a left and a right tree.
In binary search trees, all the elements on the left of a node
are smaller and all the elements on the right of a node are
greater than the root. For example, the tree on the right
complies the binary search property.
The access cost of a binary search tree
is the sum of product of depth of items with their
frequencies.
Question:
You are given n items with their frequencies. Calculate and
show the total access cost when the elements are
inserted according to the given order. Assume that, there is no
duplicate item.
Input specification
You will be first given a number (n) the number of
items where 0 ≤ n ≤ 200. Then in the following
n lines, you will be given the information for n items.
Every line contains:
- The value of the node: an integer between -10,000 and +10,000.
- The frequency of the node: a floating point number between 0 and 1
Output specification:
Show one floating point number with 3 digits precision:
the total access cost of the tree.
Sample Input I
6
6 0.3
2 0.2
4 0.15
8 0.1
1 0.2
5 0.05
|
Sample Output I
2.15
|
Explanation: The depth of 6 is
1, as a result its access cost will be (0.3 * 1)
, The depth of 5 is 4 and its access cost is
(0.05 * 4) . And so, sum of the total
access cost for this BST with this given order is:
(0.3 * 1) + (0.2 * 2) + (0.1 * 2) + (0.2 * 3) +
(0.15 * 3) + (0.05 * 4) = 2.15
Для отправки решений необходимо выполнить вход.
|