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

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


15PrE-30. 50818 - Depth Limited BST

CEN303 2013-15 Questions

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

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

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

• 15HW-40. 50829 - Decode an Image
• 15HW-50. 50830 - Sorting BST Nodes
• 15HW-60. 50678 - The Jumping Rabbit
• 15MdE-10. 50802 - Comparing Exams
• 15MdE-20. 50803 - Sum of the dept...
• 15MdE-40. 50805 - Sum of the weig...
• 15PrE-10. 50816 - Largest Sum Path
• 15PrE-20. 50817 - The Knight Move
• 15PrE-30. 50818 - Depth Limited...
• 15PrE-40. 50819 - Linked Numbers
• 15PrE2-01. 50847 - The first m train...
• 15PrE2-06. 50837 - Sum is equal to K
• 15Rst-10. 50857 - Nine-Stones Game
• 2.15FE-03. 50996 - Checkers - the ...

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

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

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

Depth Limited BST

Assume that you need to place some numbers in to an initially empty BST. But if the depth grows too big, the BST becomes un-manageable. And, you want to make sure that no element will be inserted to the tree if depth goes deeper than the given value d.

Question:
Write a program that inserts the given numbers in the BST while preserving the given depth. Then, you will be given another number (num). Check if num is in the tree or not.

Input specification
You will be first given 2 numbers

  • The number of numbers (n) where 1 ≤ n ≤ 10,000
  • The depth limit (d) where 1 ≤ d ≤ 50
Then in the following n lines, you will be given n numbers where each number is between -3e4 and 3e4. Searching number (num) will be given on the last line.

Output specification
If the given number is in the tree, show its depth. If it's not in the tree, show -1.

Sample Input I
8 2
15
17
12
14
16
1
13
18
13
Sample Input II
8 3
15
17
12
14
16
1
13
18
13
Sample Output I  
-1
Sample Output II
3


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

www.contester.ru