Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
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
|
Для отправки решений необходимо выполнить вход.
|