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

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


15. 50863 - Total Access Cost of a BST

IMPC16 Group Contests

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

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

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

• 01. 50832 - Rock Paper Scissors Liz...
• 02. 50833 - Min of Odd Positions
• 03. 50834 - The train which leaves ...
• 11. 50859 - Low performance
• 12. 50860 - Number of Student Certi...
• 13. 50861 - The largest Student Group
• 14. 50862 - Sum of the Pairs
• 15. 50863 - Total Access Cost o...
• 21. 50873 - Max Frequency
• 22. 50874 - Apartment Building Adm...
• 23. 50875 - Take m-out
• 24. 50876 - He is my cousin
• 25. 50877 - Friendly Queue
• 32. 50926 - School Mail Merge
• 33. 50927 - Health Expenses
• 34. 50928 - War Of Battleships

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

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

Лимит времени 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



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

www.contester.ru