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

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


14-Fall1-50. 50770 - Average Depth

CEN303 2013-15 Questions

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

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

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

• 13-Fall2-10. 50411 - Sum of the Lea...
• 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 ...
• 14-Fall1-60. 50784 - Top Growing C...
• 14-Fall2-10. 50751 - The biggest Mi...
• 14-Fall2-20. 50794 - Writing Files Int...
• 14-Fall2-30. 50490 - Across the River
• 14-Fall2-40. 50772 - The Path of a N...
• 14-Fall2-50. 50681 - Center of a Series
• 14-FallResit-10. 50525 - Ordering Pizza
• 14-FallResit-20. 50488 - Connecting...

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

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

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Prepared by Ibrahim Mesecan.

Average Depth

The depth of a node in trees, is the number of steps to reach to the node from the root. The depth of the root node is assumed to be zero.

Question: You will be given a series of numbers to be inserted into an initially empty Binary Search Tree (BST). Calculate the average depth of the tree.

Input specification
You will be first given a number (n) the number of numbers where 1 ≤ n ≤ 10000. Then you will be given n space separated numbers (nums[n]) where each of the number in the series is 1 ≤ nums[i] ≤ 10000.

Output specification
Calculate and show the average depth of the BST with three digits precision.

Sample Input I
  12
  6 8 2 4 1 2 7 9 4 3 6 5
Sample Output I
  1.778

Output I Explanation
  The depth of 6 is 0,
  The depth of 2 is 1,
  The depth of 8 is 1,
  The depth of 4 is 2,
  The depth of 7 is 2,
  The depth of 3 is 3, etc.
Each of the numbers: 2, 4, and 6 appears twice. Thus there are normally 9 numbers in the BST. Sum of the depths is 16, and thus the average is 16/9= 1.778


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

www.contester.ru