HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Dynamic programming & Greedy > problem:


50979 - Minimum access cost for BST

Guest
• Review clarifications (2)

Section problems

• 50485 - Center of gravity of a plate
• 50674 - Collecting Eggs
• 50677 - The Cottage
• 50675 - Kruja Boys
• 50679 - Jetpack Hurdle Jumping
• 50673 - DNA Testing
• 50997 - Dynamic Knights
• 50936 - Saving the Soldiers
• 50979 - Minimum access cost fo...
• 51062 - Fish Pond II
• 51010 - Max Sequential Sum
• 51072 - Castle on chessboard
• 51075 - Shortest Path for Bishop
• 50688 - Epoka Furgon
• 50524 - Elevator
• 50536 - Epoka Furgon Shpk
• 50687 - Pascal Triangle - 2

Feedback

If you notice incorrect translations in Contester, please let author know.

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



Для отправки решений необходимо выполнить вход.

www.contester.ru