HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Contests > IMPC - 2013-2014 > problem:


14-03-40. 50773 - Balanced Sum Tree

IMPC - 2013-2014

Start: Mar.16.2013 at 12:00:00 PM
Finish: Mar.16.2013 at 05:00:00 PM
The contest is finished!
• Contest scoreboard

Guest
• Review clarifications (1)

Contest problems

• 50386 - Conformity
• 14-01-10. 50457 - The Number of W...
• 14-01-40. 50419 - The longest bitoni...
• 14-01-50. 50795 - Trunk
• 14-03-10. 50412 - K numbers
• 14-03-20. 50398 - Sum of kth Anti-d...
• 14-03-30. 50377 - kth Permutation
• 14-03-40. 50773 - Balanced Su...
• 14-03-60. 50382 - Parkside's Other ...
• 14-03-70. 50468 - Draw Matrix - 2
• 14-03-70. 50468 - Draw Matrix - 2
• 14-03-80. 50675 - Kruja Boys
• 14-03-90. 50717 - Hurdle Jumping
• 14-04-20. 50493 - n-digit kth Prime ...
• 14-04-30. 50669 - Area of an Irregu...
• 14-04-40. 50712 - Moon algebra

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.

Balanced Sum Tree

Question: In a binary search tree (Figure 1), any element in the tree, is greater than its left children, and is smaller than its right children.

Similarly, Balanced Sum Tree (BST), is a Binary tree where sum of the elements on the left and right trees are balanced. When inserting elements, for any element in the tree, the following is applied:

  • Elements are inserted in order of the given elements
  • if the sum of the elements on the left and right subtrees are equal, the number is inserted to the left
  • if sum of the elements on the left tree is smaller than the sum of the elements on the right subtree, then it's inserted to the left;
  • Otherwise, it's inserted to the right.

Question: Write a program that is going to insert n integers into Balanced Sum Tree. After then, the program is going to show sum of the left most and right most numbers.

Input specification
You will be given an integer number (n) at the beginning where 1 ≤ n ≤ 10000. Then in the following line, you will be given n integers which are between 0 and 1000.

Output specification
Show just one number: sum of the left most and right most elements.

 Sample Input   
  7
  6 2 8 1 4 4 7
 Sample Output   
  12

Explanation: 6 is the first element. And thus, it's the root element. Then 2 is inserted to the left because, Sum of the left and right trees of 6 are both 0. Then, because sumLeft is 2 and sumRight is 0, 8 is inserted to the right. So on...

Left most element is 4, and the right most element is 8, And thus, the sum is 12.


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

www.contester.ru