HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Contests > IMPC16 Group Contests > problem:


F6. 50979 - Minimum access cost for BST

IMPC16 Group Contests

Start: Jan.16.2016 at 10:00:00 AM
Finish: Jan.16.2016 at 02:00:00 PM
The contest is finished!
• Contest scoreboard

Guest
• Review clarifications (2)

Contest problems

• 32. 50926 - School Mail Merge
• 33. 50927 - Health Expenses
• 34. 50928 - War Of Battleships
• 35. 50929 - Present from your uncles
• F1. 50841 - My grand-grand-grandfa...
• F2. 50936 - Saving the Soldiers
• F4. 50977 - Gaussian Elimination
• F5. 50978 - Albanian Coders
• F6. 50979 - Minimum access cos...

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