ВНИМАНИЕДля получения программы своего варианта пишите на наш электронный адрес proglabs@mail.ru

Общая постановка

Каждая задача предполагает по последовательности чисел входного файла построение бинарного поискового дерева (предполагаем, что в дереве не может быть двух вершин с одинаковыми ключами). Затем в большинстве задач в дереве необходимо найти вершины, которые удовлетворяют заданным свойствам, удалить их и вывести итоговое дерево в выходной файл, используя указанный обход дерева.

Содержательная часть каждой задачи (за исключением построения дерева) должна решаться за линейное от числа вершин время. Исключение составляет задача $24$, где допускается нелинейная зависимость от числа вершин. Кроме того, в задачах $23$ и $35$ допускается линейная зависимость от параметра $k$, т.е. общее время $O(n \cdot k)$, где $n$ — число вершин дерева.

Задачи

Задача №1

Найти среднюю по значению вершину из вершин дерева, у которых число потомков в левом поддереве не равно числу потомков в правом поддереве. Удалить ее (правым удалением), если такая вершина существует. Выполнить прямой левый обход полученного дерева.

Если у вершины отсутствует некоторое поддерево, то число вершин этого поддерева полагаем равным $0$.

Формат входных данных

Входной файл содержит последовательность чисел — ключи вершин в порядке добавления в дерево.

Формат выходных данных

Выходной файл должен содержать последовательность ключей вершин, полученную прямым левым обходом итогового дерева.

Пример

входной файлвыходной файл
20
8
40
42
14
4
13
41
5
1		40
8
4
1
5
14
13
42
41

Задача №2

Найти среднюю по значению вершину из вершин дерева, у которых высота левого поддерева не равна высоте правого поддерева. Удалить ее (правым удалением), если такая вершина существует. Выполнить прямой левый обход полученного дерева.

Если у вершины отсутствует некоторое поддерево, то его высоту полагаем равным $-1$.

Формат входных данных

Входной файл содержит последовательность чисел — ключи вершин в порядке добавления в дерево.

Формат выходных данных

Выходной файл должен содержать последовательность ключей вершин, полученную прямым левым обходом итогового дерева.

Пример

входной файлвыходной файл
2
20
11
18
25
22
7
48
20
11
7
18
25
22
48
6
4
8
2
5
7
9
6
4
2
5
8
7
9

Задача №3

Найти среднюю по значению из вершин дерева, у которых число потомков в левом поддереве отличается от числа потомков в правом поддереве на единицу. Удалить ее (правым удалением), если такая вершина существует. Выполнить прямой левый обход полученного дерева.

Если у вершины нет некоторого поддерева, то число вершин этого поддерева полагаем равным $0$.

Формат входных данных

Входной файл содержит последовательность чисел — ключи вершин в порядке добавления в дерево.

Формат выходных данных

Выходной файл должен содержать последовательность ключей вершин, полученную прямым левым обходом итогового дерева.

Пример

входной файлвыходной файл
40
30
15
10
20
31
3
12
5
7		40
30
15
10
3
7
12
20
31

Задача №4

Найти высоту $H$ дерева и удалить (правым удалением) среднюю по значению из вершин на уровне $[\frac{H}{2}]$, у которых число потомков в левом поддереве больше числа потомков в правом поддереве. Выполнить прямой левый обход полученного дерева.

Если у вершины нет некоторого поддерева, то число вершин этого поддерева полагаем равным $0$.

Формат входных данных

Входной файл содержит последовательность чисел — ключи вершин в порядке добавления в дерево.

Формат выходных данных

Выходной файл должен содержать последовательность ключей вершин, полученную прямым левым обходом итогового дерева.

Пример

входной файлвыходной файл
20
10
22
15
13
12
14
5
6
16
4		20
10
5
4
6
16
13
12
14
22
1
2		1
2

Задача №5

Среди полупутей минимальной положительной длины между листьями выбрать тот, у которого сумма ключей вершин минимальна. Если такой полупуть существует, то удалить (правым удалением) центральную вершину этого полупути.

Если решение неоднозначно, то выбирать такой минимальный полупуть между листьями, корневая вершина которого имеет минимальное ключевое значение.

Формат входных данных

Входной файл содержит последовательность чисел — ключи вершин в порядке добавления в дерево.

Формат выходных данных

Выходной файл должен содержать последовательность ключей вершин, полученную прямым левым обходом итогового дерева.

Примеры

входной файлвыходной файл
10
5
13
7
4
11
6
8
15
1		10
5
4
1
8
6
13
11
15
5
1
0
15
19
8
7
6
9
10		6
1
0
15
8
7
9
10
19

Задача №6

Найти наибольший полупуть между вершинами дерева, у которого сумма ключей вершин максимальна, и удалить (правым удалением) сначала центральную вершину этого полупути, если она существует, потом корень этого же полупути, если он не являлся одновременно и центральной вершиной этого полупути. Выполнить прямой левый обход полученного дерева.

Формат входных данных

Входной файл содержит последовательность чисел — ключи вершин в порядке добавления в дерево. Гарантируется, что в дереве не менее двух вершин.

Формат выходных данных

Выходной файл должен содержать последовательность ключей вершин, полученную прямым левым обходом итогового дерева.

Пример

входной файлвыходной файл
10
11
5
3
6
7
8
4		11
5
3
4
6
7
8

Задача №7

Найти высоту $H$ дерева и удалить (правым удалением) среднюю по значению из вершин на уровне $[\frac{H}{2}]$, у которых высота левого поддерева равна высоте правого. Выполнить прямой левый обход полученного дерева.

Если у вершины отсутствует некоторое поддерево, то его высоту полагаем равной $-1$.

Формат входных данных

Входной файл содержит последовательность чисел — ключи вершин в порядке добавления в дерево. Гарантируется, что в дереве не менее двух вершин.

Формат выходных данных

Выходной файл должен содержать последовательность ключей вершин, полученную прямым левым обходом итогового дерева.

Пример

входной файлвыходной файл
10
5
15
7
13
17
3		10
5
3
7
15
13
17

Задача №8

Найти такой наибольший полупуть между вершинами дерева, у которого корневая вершина находится на наименьшей глубине. Удалить (правым удалением) эту корневую вершину.

Формат входных данных

Входной файл содержит последовательность чисел — ключи вершин в порядке добавления в дерево. Гарантируется, что в дереве не менее двух вершин.

Формат выходных данных

Выходной файл должен содержать последовательность ключей вершин, полученную прямым левым обходом итогового дерева.

Пример

входной файлвыходной файл
20
10
30
5
1
7
3
9
25
40
15
11
13
16
17

25
10
5
1
3
7
9
15
11
13
16
17
30
40

1
2
3
4
5		2
3
4
5

Задача №9

Найти вершины, через которые проходят наибольшие полупути, и удалить (правым удалением) ту из них, ключ которой является вторым по значению.

Формат входных данных

Входной файл содержит последовательность чисел — ключи вершин в порядке добавления в дерево. Гарантируется, что в дереве не менее двух вершин.

Формат выходных данных

Выходной файл должен содержать последовательность ключей вершин, полученную прямым левым обходом итогового дерева.

Пример

входной файлвыходной файл
10
30
180
181
20
70
60
50
40
130
176
177
178
179
120
110
100
90		0
30
180
70
60
50
40
130
120
110
100
90
176
177
178
179
181
Задача №9. Пример обработки бинарного поискового дерева

Задача №10

Найти вершины, через которые проходит наибольшее число наибольших (по длине) полупутей, и удалить их (правым удалением) обратным левым обходом.

Формат входных данных

Входной файл содержит последовательность чисел — ключи вершин в порядке добавления в дерево. Гарантируется, что в дереве не менее двух вершин.

Формат выходных данных

Выходной файл должен содержать последовательность ключей вершин, полученную прямым левым обходом итогового дерева.

Замечания

  1. Гарантируется, что хотя бы одна вершина не подлежит удалению.
  2. Для удаления всех вершин, удовлетворяющих заданным требованиям, необходимо разработать алгоритм, работающий за время $O(n)$.

Примеры

входной файлвыходной файл
10
5
15
4
6
14
16
17
9		14
4

10
30
180
181
20
70
60
50
40
130
176
177
178
179
120
110
100
90

10
30
20
180
70
60
50
40
176
120
110
100
90
177
178
179
181

Задача №11

Найти такой наибольший полупуть, у которого сумма ключей крайних вершин минимальна. Удалить (правым удалением) корневую вершину этого полупути.

Формат входных данных

Входной файл содержит последовательность чисел — ключи вершин в порядке добавления в дерево. Гарантируется, что в дереве не менее двух вершин.

Формат выходных данных

Выходной файл должен содержать последовательность ключей вершин, полученную прямым левым обходом итогового дерева.

Пример

входной файлвыходной файл

50
40
60
30
45
27
35
46

50
45
30
27
35
46
60

Задача №12

Найти наибольший полупуть между вершинами с разным числом потомков с минимальной суммой ключей крайних вершин (длина искомого полупути должна быть больше $0$).

Если таких полупутей несколько, то выбрать из них тот, у которого корневая вершина имеет минимальное ключевое значение. Удалить (правым удалением), если существует, среднюю по значению вершину этого полупути.

Если у вершины отсутствует некоторое поддерево, то число вершин этого поддерева полагаем равным $0$.

Замечания

В случае неоднозначности выбора удаляемой вершины (например, несколько полупутей максимальной длины между вершинами с разным числом потомков и с минимальной суммой ключей крайних вершин имеют один и тот же корень, но средние по значению вершины этих полупутей не совпадают) ничего из дерева удалять не нужно.

Формат входных данных

Входной файл содержит последовательность чисел — ключи вершин в порядке добавления в дерево.

Формат выходных данных

Выходной файл должен содержать последовательность ключей вершин, полученную прямым левым обходом итогового дерева.

Пример

входной файлвыходной файл
0
40
50
60
70
80
90
2
1		0
40
2
1
60
70
80
90
0
4
5
6
7
8
9
3
1		0
4
3
1
5
7
8
9

Задача №13

Необходимо найти наибольший полупуть между вершинами разной высоты с минимальной суммой ключей крайних вершин.

Если таких полупутей несколько, то выбрать тот из них, у которого корневая вершина имеет наименьшее ключевое значение.

Удалить (правым удалением), если существует, среднюю по значению вершину этого полупути.

Если у вершины отсутствует некоторое поддерево, то его высоту полагаем равной $-1$.

Замечание

В случае неоднозначности выбора удаляемой вершины (например, несколько наибольших полупутей между вершинами разной высоты и с минимальной суммой ключей крайних вершин имеют один и тот же корень, но средние по значению вершины этих полупутей не совпадают) ничего из дерева удалять не нужно.

Формат входных данных

Входной файл содержит последовательность чисел — ключи вершин в порядке их добавления в дерево.

Формат выходных данных

Выходной файл должен содержать последовательность ключей вершин, полученную прямым левым обходом итогового дерева.

Пример

входной файлвыходной файл
0
4
5
6
7
8
9
3
1		0
4
3
1
5
7
8
9

Задача №14

Необходимо найти пути минимальной длины между корнем и листьями и удалять (левый удалением) в порядке возрастания ключей средние по значению вершины этих путей, если они существуют.

Замечание

Если некоторая вершина является средней по значению для нескольких путей минимальной длины, то удаляется она только один раз.

Формат входных данных

Входной файл содержит последовательность чисел — ключи вершин в порядке их добавления в дерево. Гарантируется, что в дереве не менее двух вершин.

Формат выходных данных

Выходной файл должен содержать последовательность ключей вершин, полученную прямым левым обходом итогового дерева.

Пример

входной файлвыходной файл
10
15
13
18
5
8
3		10
3
18
1
2		1
2

Задача №15

Определить, являются ли два дерева зеркальным отражением друг друга по структуре, если сначала удалить (правым удалением) корень каждого из деревьев.

Замечания

  1. Если деревья были тривиальными (одна вершина в каждом дереве), то в результате удаления корней получаются два не графа, поэтому будем считать, что тривиальные деревья зеркально совпадают.
  2. Если в результате удаления корней получаются два тривиальных дерева, то будем считать, что они зеркально совпадают.

Формат входных данных

Входной файл содержит последовательность чисел — ключи вершин в порядке добавления в дерево. Деревья разделяются строкой с единственным символом «*».

Формат выходных данных

Выходной файл должен содержать в первой строке сообщение YES или NO. Если сообщение YES, то во второй строке вывести последовательность ключей вершин, полученную прямым левым обходом первого дерева, а в третьей строке — последовательность ключей вершин, полученную прямым левым обходом второго дерева.

Примеры

входной файлвыходной файл
2
1
3
*
2
1
3		NO
96
90
97
80
95
85
*
20
30
40
50
33
45		YES
97 90 80 85 95
30 40 33 50 4

Задача №16

Необходимо удалить (правым удалением) корень дерева, а затем для каждой вершины определить, сколько наибольших полупутей проходят через нее.

Формат входных данных

Входной файл содержит последовательность чисел — ключи вершин в порядке их добавления в дерево. Гарантируется, что в дереве не менее двух вершин.

Формат выходных данных

Выполните прямой левый обход итогового дерева. Для каждой вершины в отдельной строке выведите через пробел ее ключ и количество полупутей наибольшей длины, проходящих через нее.

Пример

входной файлвыходной файл
1
5
3
7
2
4
6
8		5 4
3 4
2 2
4 2
7 4
6 2
8 2
10
5
4
3
2
1
6
7
8
9

5 1
4 1
3 1
2 1
1 1
6 1
7 1
8 1
9 1

Задача №17

Найти и удалить (правым удалением), если существует, среднюю по значению из вершин дерева, у которых высота левого поддерева отличается от высоты правого наибольшим образом. Выполнить прямой левый обход полученного дерева.

Если у вершины отсутствует некоторое поддерево, то его высоту полагаем равной $-1$.

Формат входных данных

Входной файл содержит последовательность чисел — ключи вершин в порядке их добавления в дерево. Гарантируется, что в дереве не менее двух вершин.

Формат выходных данных

Выходной файл должен содержать последовательность ключей вершин, полученную прямым левым обходом итогового дерева.

Пример

входной файлвыходной файл
10
5
6
8
7
11
1
2
12
13
3		10
5
1
2
3
8
7
11
12
13
3
1
2
5
4
6
7		3
1
2
5
4
6
7

Задача №18

Найти вершины, через которые проходит четное число наибольших полупутей, и удалить (правым удалением) ту из них, ключ которой наименьший (если нет вершин, удовлетворяющих нужному свойству, то ничего из дерева удалять не надо).

Формат входных данных

Входной файл содержит последовательность чисел — ключи вершин в порядке добавления в дерево. Гарантируется, что в дереве не менее двух вершин.

Формат выходных данных

Выходной файл должен содержать последовательность ключей вершин, полученную прямым левым обходом итоговое дерева.

Пример

входной файлвыходной файл
2
1
5
4
6
3
7		2
5
4
3
6
7

Задача №19

Найти вершины, через которые проходят наибольшие полупути, и удалить (правым удалением) самую высокую из них.

Формат входных данных

Входной файл содержит последовательность чисел — ключи вершин в порядке добавления в дерево. Гарантируется, что в дереве не менее двух вершин.

Формат выходных данных

Выходной файл должен содержать последовательность ключей вершин, полученную прямым левым обходом итогового дерева.

Пример

входной файлвыходной файл

20
21
10
1
15
14
13
19
16
17
11
12
18

20
10
1
16
14
13
11
12
19
17
18
21

Задача №20

Найти наибольший полупуть между вершинами разного уровня с минимальной суммой ключей крайних вершин и сделать центральную вершину этого полупути корнем дерева (методом поворотов).

Замечания

  1. Исходное дерево содержит не менее двух вершин.
  2. Если центральной вершины нет, то метод поворотов не выполняется. Выходной файл должен содержать сначала минимальную сумму ключей крайних вершин, а затем массив вершин, полученный прямым левым обходом исходного дерева.
  3. Для выполнения метода поворотов нужно спуститься из корня дерева к центральной вершине и поднять ее (после выполнения очередного поворота центральная вершина оказывается на меньшей глубине).

Формат входных данных

Входной файл содержит последовательность чисел — ключи вершин в порядке добавления в дерево.

Формат выходных данных

Выходной файл должен содержать сначала сумму ключей крайних вершин найденного полупути, а затем последовательность ключей вершин, полученную прямым левым обходом итогового дерева.

Пример

входной файлвыходной файл
10
30
180
181
20
70
60
50
40
130
176
177
178
179
120
110
100
90		100
130
10
30
20
70
60
50
40
120
110
100
90
180
176
177
178
179
181

Задача №21

Найти среднюю по значению из вершин дерева, у которых высоты поддеревьев равны, а число потомков в правом и левом поддеревьях отличается. Удалить ее (правым удалением), если такая вершина существует.

Если у вершины отсутствует некоторое поддерево, то его высоту полагаем равной $-1$, а число вершин этого поддерева — $0$.

Формат входных данных

Входной файл содержит последовательность чисел — ключи вершин в порядке добавления в дерево.

Формат выходных данных

Выходной файл должен содержать последовательность ключей вершин, полученную прямым левым обходом итогового дерева.

Пример

входной файлвыходной файл
3
2
1
5
4
6

4
2
1
5
6

Алгоритмы на бинарных деревьях. Задача №21

Задача №22

Найти среднюю из вершин дерева, у которых высоты поддеревьев не равны, а число потомков в правом и левом поддеревьях равны. Удалить ее (правым удалением), если такая вершина существует.

Если у вершины отсутствует некоторое поддерево, то его высоту полагаем равной $-1$, а число вершин этого поддерева — $0$.

Формат входных данных

Входной файл содержит последовательность чисел — ключи вершин в порядке добавления в дерево.

Формат выходных данных

Выходной файл должен содержать последовательность ключей вершин, полученную прямым левым обходом итогового дерева.

Пример

входной файлвыходной файл
10
8
12
4
9
11
13
3
6
2
5
7
1		10
8
5
3
2
1
6
7
9
12
11
13

Алгоритмы на бинарных деревьях. Задача №22

Задача №23

Найти все вершины, через которые проходят полупути длины $K$ между висячими вершинами. Выбрать те, которые находятся на наименьшей глубине, и удалить (левым удалением) из них среднюю по значению, если она существует.

Формат входных данных

Входной файл содержит в первой строке число $K$ ($2 < K \leq 10^9$), а в последующих строках — последовательность чисел — ключи вершин в порядке добавления в дерево.

Формат выходных данных

Выходной файл должен содержать последовательность ключей вершин, полученную прямым левым обходом итогового дерева.

Пример

входной файлвыходной файл
8
13
1
57
20
81
59
48
36
90
83
75
18
86
72
52
31
2
10
37
15
17
99
45
12
3		12
1
2
10
3
57
20
18
15
17
48
36
31
37
45
52
81
59
75
72
90
83
86
99

Алгоритмы на бинарных деревьях. Задача №23

Задача №24

Найти все полупути длины $H$ между висячими вершинами, где $H$ — высота дерева. Выбрать корни этих полупутей, расположенные на максимальной глубине, и удалить (правым удалением) тот из них, который является средним по значению.

Формат входных данных

Входной файл содержит последовательность чисел — ключи вершин в порядке добавления в дерево. Гарантируется, что в дереве не менее двух вершин.

Формат выходных данных

Выходной файл должен содержать последовательность ключей вершин, полученную прямым левым обходом итогового дерева.

Пример

входной файлвыходной файл
10
8
16
7
9
13
17
12
14		10
8
7
9
17
13
12
14

Задача №25

Найти и удалить (правым удалением), если существует, среднюю по значению из вершин дерева, у которых число потомков в левом поддереве отличается от числа потомков в правом наибольшим образом.

Если у вершины отсутствует некоторое поддерево, то число вершин этого поддерева полагаем равным $0$.

Формат входных данных

Входной файл содержит последовательность чисел — ключи вершин в порядке добавления в дерево. Гарантируется, что в дереве не меньше двух вершин.

Формат выходных данных

Выходной файл должен содержать последовательность ключей вершин, полученную прямым левым обходом итогового дерева.

Пример

входной файлвыходной файл
50
40
60
30
55
70
27
35
40
65
80
30		50
30
27
35
60
55
70
65
80

Задача №26

Найти и удалить (правым удалением), если существует, вершину с наибольшим ключом из вершин дерева, у которых число потомков в правом и левом поддеревьях отличается наибольшим образом.

Если у вершины отсутствует некоторое поддерево, то число вершин этого поддерева полагаем равным $0$.

Формат входных данных

Входной файл содержит последовательность чисел — ключи вершин в порядке добавления в дерево. Гарантируется, что в дереве не меньше двух вершин.

Формат выходных данных

Выходной файл должен содержать последовательность ключей вершин, полученную прямым левым обходом итогового дерева.

Пример

входной файлвыходной файл
50
40
60
30
45
55
70
27
35
46
65
62
68
30		50
40
30
27
35
45
46
60
55
65
62
68

Задача №27

Найти средний по значению, если существует, из листьев дерева и удалить (правым удалением) его отца.

Формат входных данных

Входной файл содержит последовательность чисел — ключи вершин в порядке добавления в дерево.

Гарантируется, что в дереве не менее двух вершин.

Формат выходных данных

Выходной файл должен содержать последовательность ключей вершин, полученную прямым левым обходом итогового дерева.

Пример

входной файлвыходной файл
50
40
60
30
45
55
70
27
35
46
50
80
40
55
90		50
40
30
27
35
46
60
55
70
80
90
1
2		2

Задача №28

Найти в дереве среднюю по значению из вершин, у которых высоты поддеревьев равны. Удалить (правым удалением) данную вершину, если она существует. Листья дерева также рассматриваются в качестве вершин, у которых высоты поддеревьев равны.

Если у вершины отсутствует некоторое поддерево, то его высоту полагаем равной $-1$.

Формат входных данных

Входной файл содержит последовательность чисел — ключи вершин в порядке добавления в дерево.

Гарантируется, что в дереве не менее двух вершин.

Формат выходных данных

Выходной файл должен содержать последовательность ключей вершин, полученную прямым левым обходом итогового дерева.

Пример

входной файлвыходной файл
50
60
70
80		50
60
70

Задача №29

Найти в дереве среднюю по значению из вершин, у которых число потомков в левом поддереве отличается от числа потомков в правом на два.  Удалить (левым удалением) данную вершину, если она существует. Если у вершины отсутствует некоторое поддерево, то число вершин этого поддерева полагаем равным $0$.

Формат входных данных

Входной файл содержит последовательность чисел — ключи вершин в порядке добавления в дерево.

Формат выходных данных

Выходной файл должен содержать последовательность ключей вершин, полученную прямым левым обходом итогового дерева.

Пример

входной файлвыходной файл
10
5
11
21
9
1
6		9
5
1
6
11
21

Алгоритмы на бинарных деревьях. Задача №29

Задача №30

Найти среднюю по значению вершину в дереве, у которой высота левого поддерева отличается от высоты правого на два. Удалить (левым удалением) данную вершину, если она существует. Выполнить прямой (левый) обход полученного дерева.

Если у вершины отсутствует некоторое поддерево, то его высоту полагаем равной $-1$.

Формат входных данных

Входной файл содержит последовательность чисел — ключи вершин в порядке добавления в дерево.

Формат выходных данных

Выходной файл должен содержать последовательность ключей вершин, полученную прямым левым обходом итогового дерева.

Пример

входной файлвыходной файл
10
5
11
12
6
3
1
2		10
3
1
2
6
11
12
10
1
15
11
14		10
1
15
11
14

Задача №31

Найти вершины, через которые проходит нечетное число наибольших полупутей, и удалить (правым удалением) ту из них, ключ которой наибольший.

Если в дереве нет вершин, удовлетворяющих нужному свойству, то ничего удалять не требуется. Выполнить прямой (левый) обход полученного дерева.

Формат входных данных

Входной файл содержит последовательность чисел — ключи вершин в порядке добавления в дерево.

Гарантируется, что в дереве не менее двух вершин.

Формат выходных данных

Выходной файл должен содержать последовательность ключей вершин, полученную прямым левым обходом итогового дерева.

Пример

входной файлвыходной файл
10
5
20
4
6
15
30
3
7
14
40
8
50
9
60

10
5
4
3
6
7
8
9
20
15
14
30
40
50

Задача №32

Найти среднюю по значению вершину дерева из вершин, через которые проходит четное положительное число наибольших полупутей, и удалить ее (правым удалением), если она существует. Если в дереве нет вершин, удовлетворяющих заданному свойству, то ничего из дерева удалять не надо.

Формат входных данных

Входной файл содержит последовательность чисел — ключи вершин в порядке добавления в дерево.

Формат выходных данных

Выходной файл должен содержать последовательность ключей вершин, полученную прямым левым обходом итогового дерева.

Пример

входной файлвыходной файл
20
10
22
5
11
21
23		21
10
5
11
22
23

Задача №33

Найти наибольший полупуть между вершинами дерева, у которого сумма ключей крайних вершин минимальна. Удалить (правым удалением) среднюю по значению вершину этого полупути.

Если средней по значению вершины не существует (т.е. число вершин искомого полупути четно), то ничего из дерева удалять не надо.

Формат входных данных

Входной файл содержит последовательность чисел — ключи вершин в порядке добавления в дерево.

Гарантируется, что в дереве не менее двух вершин.

Формат выходных данных

Выходной файл должен содержать последовательность ключей вершин, полученную прямым левым обходом итогового дерева.

Пример

входной файлвыходной файл
50
40
60
30
45
27
35
46		50
45
30
27
35
46
60

Задача №34

Найти и удалить (если такая вершина есть, правым удалением) максимальную по значению среди вершин, для которых расстояние до любой другой вершины дерева строго меньше $k$ и через которые не проходят полупути длины $k$ (длина полупути и расстояние между двумя вершинами измеряются числом дуг).

Формат входных данных

В первой строке находится целое число $K$ ($0 \leq K \leq 10^9$).

В последующих строках, в каждой по одному числу, находятся ключи вершин исходного дерева (от $0$ до $2^{31} — 1$) в порядке добавления в дерево.

Число вершин произвольное от $0$ до $1\ 000$.

Формат выходных данных

Выходной файл должен содержать последовательность ключей вершин, полученную прямым левым обходом итогового дерева.

Если в результате дерево удалилось полностью, то необходимо вывести в выходной файл сообщение Empty.

Пример

входной файлвыходной файл

6
5
3
1
0
6
4
8
2
7
9

5
3
1
0
2
6
8
7
9

Задача №35

Найти максимальную по значению вершину, расстояние от которой до любой другой вершины дерева строго меньше $k$ и через которую не проходят полупути длины $k$ с висячими концевыми вершинами (длина полупути и расстояние между двумя вершинами измеряется в дугах). Если такая вершина есть, то удалить ее правым удалением.

Формат входных данных

В первой строке находится целое число $k$ ($0 \leq k \leq 10^9$). В последующих строках, в каждой по одному числу — ключи вершин исходного дерева, в порядке добавления в дерево (значения в пределах от $0$ до $2^{31} — 1$). Число вершин не превосходит $1\ 000$.

Формат выходных данных

Выходной файл должен содержать последовательность ключей вершин, полученную прямым левым обходом итогового дерева. Если в результате дерево удалилось полностью, то необходимо вывести в выходной файл сообщение Empty.

Пример

входной файлвыходной файл
6
5
3
1
0
6
4
8
2
7
9		5
3
1
0
2
6
8
7
9
ВНИМАНИЕДля получения программы своего варианта пишите на наш электронный адрес proglabs@mail.ru