Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb. Question by Ibrahim Mesecan.
Minimum access cost for BST
For a website, you need to design an algorithm
to decrease the total access cost. The website
is used to search some items. The search items
change time to time. In order to have a faster
search you want the most frequent items to be accessed
first (the most frequent items to be usually at the top
positions). The total access cost of a BST is:
where n is the number of search items, pi
is the probability and di depth of item in
BST.
Question: Write a program that
takes names and probabilities of n items, then it calculates
the cost of BST configuration such that it complies
the BST property and has the minimum access cost
(the item on the left is smaller and the item on the
right is greater than the root).
Input specification:
You will be given an integer in the beginning:
the number of items (n). In the following n-lines,
you will be given the names and probabilities of n
items where
where 0 ≤ n ≤ 200
Output specification:
Show one floating point number with three
digits precision.
Sample Input
7
a 0.22
an 0.18
or 0.20
who 0.05
why 0.25
has 0.02
buy 0.08
|
Sample Output
2.19
|
Explanation:
When "or" is at the top, its access
cost will be 0.2 (probability) * 1 (depth+1)
. Then, the
minimum total access cost is
(0.22 * 3) + (0.18 * 2) + (0.08 * 3) + (0.02 * 4) +
(0.2 * 1) + (0.05 * 3) + (0.25 * 2) = 2.19
Для отправки решений необходимо выполнить вход.
|