ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Турниры > IMPC16 Group Contests > задача:


F6. 50979 - Minimum access cost for BST

IMPC16 Group Contests

Старт: 16.янв.2016 в 10:00:00
Финиш: 16.янв.2016 в 14:00:00
Турнир завершён!
• Турнирная таблица

Гость
• Вопросы к жюри (2)

Задачи турнира

• 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...

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
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