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.
Для отправки решений необходимо выполнить вход.
|