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

Турниры > CEN303 2013-15 Questions > задача:


13-Fall2-10. 50411 - Sum of the Leaves

CEN303 2013-15 Questions

Старт: 15.дек.2013 в 14:00:00
Финиш: 15.дек.2013 в 19:00:00
Турнир завершён!
• Турнирная таблица

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

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

• 50472 - Minimum Sum Triangle
• 50842 - Minimum Sum Triangle - DP
• 50319 - Toll Plazas
• 51000 - Book Index
• 50531 - File Decryption
• 50464 - From Tirana to Durres
• 13-Fall2-10. 50411 - Sum of the...
• 13-Fall2-20. 50687 - Pascal Triangle - 2
• 13-Fall2-40. 50753 - Average of the...
• 13-Fall2-50. 50686 - The Container
• 14-Fall1-10. 50740 - Service Time - 1
• 14-Fall1-20. 50750 - Service Time - 2
• 14-Fall1-30. 50771 - BST Level Sum
• 14-Fall1-40. 50683 - Te Parkojme A...
• 14-Fall1-50. 50770 - Average Depth

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

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

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Question by Osman Ay.

Sum of the Leaves

A binary search tree (BST), also called ordered binary tree, is a type of binary tree where the nodes are arranged in order: for each node, all elements in its left subtree are less than the node (<), and all the elements in its right subtree are greater than the node (>). BST has the following properties:

  1. Each node has a unique value.
  2. A total order is defined on these values.
  3. The left subtree of a node contains only values less than the node's value.
  4. The right subtree of a node contains only values greater than the node's value.

The tree in the picture is obtained by inserting the values 4, 2, 1, 3, 2, 4, 6, and 5 in that order, starting from an empty tree. In the tree, the value of the root is 4, and the values of leaves are 1, 3 and 5. Make a program that calculates the sum of the leaf nodes' values of the binary search tree that is constructed from a given list of positive integers.

Input specification
Input has two lines. The first line of the input contains an integer N (1 ≤ N ≤ 10000) that represents the number of the integers in the list. The second line contains a list of N integers between 1 and 1000.

Output specification
Output contains a single integer that is the sum of the values of the leaf nodes.

Sample Input I   
  8
  4 2 1 3 2 4 6 5
Sample Input II   
  10
  13 10 10 20 4 17 2 20 11 17
Sample Output I   
  9
Sample Output II   
  30


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

www.contester.ru