HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Contests > IMPC16 Group Contests > problem:


15. 50863 - Total Access Cost of a 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

• 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

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.

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