--->
24 задач
<---
Источники
Напишите программу, которая будет реализовывать действия в бинарном дереве поиска «вставить», «удалить» и «найти» (по значению). Программа должна обрабатывать запросы четырёх видов:
ADD n — если указанного числа еще нет в дереве, вставлять его и выводить слово «DONE», если уже есть — оставлять дерево как было и выводить слово «ALREADY».
DELETE n — если указанное число есть в дереве, удалять его и выводить слово «DONE», если нет — оставлять дерево как было и выводить слово «CANNOT». При удалении элемента, имеющего два сына, обязательно обменивать значение с максимальным элементом левого поддерева.
SEARCH — следует выводить слово «YES» (если значение найдено в дереве) или слово «NO» (если не найдено). Дерево при этом не меняется.
PRINTTREE — выводить все дерево, обязательно используя алгоритм, указанный в формате вывода результатов.
В каждой строке входных данных записан один из запросов ADD n или DELETE n или SEARCH n или PRINTTREE. Гарантируется, что запросы PRINTTREE будут вызываться только в моменты, когда дерево не пустое. Общее количество запросов не превышает 1000, из них не более 20 запросов PRINTTREE.
Для каждого запроса выводите ответ на него. Для запросов ADD, DELETE и SEARCH — соответствующее слово в отдельной строке. На запрос PRINTTREE надо выводить дерево, обязательно согласно такому алгоритму:
template<class T> void print_tree(Node<T> *p, int level)
{
if(p==NULL)
return;
print_tree(p->left, level+1);
for(int i=0; i<level; i++)
cout << ".";
cout << p->data << endl;
print_tree(p->right, level+1);
}
(Изначальный вызов этой функции — print_tree(root,0).)
ADD 2 ADD 7 ADD 5 PRINTTREE ADD 5 DELETE 3 ADD 0 PRINTTREE DELETE 7 PRINTTREE
DONE DONE DONE 2 ..5 .7 ALREADY CANNOT DONE .0 2 ..5 .7 DONE .0 2 .5
Знаете ли вы, почему четвертый этаж заперт и там не останавливается лифт? Потому что на самом деле четвертый, запертый, этаж, где не останавливается лифт, содержит бесконечное количество комнат, пронумерованных натуральными числами. На этот этаж регулярно приезжают дети, каждый из которых заранее выбрал, в какую комнату он хочет заселиться. Если выбранная комната оказывается свободна, то ребенок занимает ее, в противном случае он занимает первую свободную комнату с бóльшим номером.
Кроме того, некоторые дети уезжают в середине смены. Сразу после отъезда ребенка его комната становится доступна для заселения следующего.
Промоделируйте работу преподавателей, ответственных за четвертый этаж и научитесь быстро сообщать приезжающим детям, какую комнату им следует занимать.
Первая строка входного файла содержит натуральное число \(n\) — количество прибытий и отъездов, происходящих в течение смены (\(1 \le n \le 100\,000\)).
Следующие \(n\) строк содержат информацию об ЛКШатах. Число \(a > 0\) обозначает, что приехал школьник, желающий занять комнату номер \(a\) (\(1 \le a \le 100\,000\)). Число \(a < 0\) обозначает, что из комнаты номер \(|a|\) уехал школьник (гарантируется, что эта комната не была пуста).
Для каждого приезжающего школьника выведите одно натуральное число — номер комнаты, в которую он поселится.
6 5 5 5 -6 5 5
5 6 7 6 8
Дан массив. Надо научиться обрабатывать два типа запросов.
* 1 L R - перевернуть отрезок \([L,\,R]\)
* 2 L R - найти минимум на отрезке \([L,\,R]\)
Первая строка файла содержит два числа \(n\), \(m\). (\(1 \le n,m \le 10^5\)) Во второй строке находится \(n\) чисел \(a_i\) (\(1 \le a_i \le 10^9\)) — исходный массив. Остальные \(m\) строк содержат запросы, в формате описанном в условии. Для чисел \(L\), \(R\) выполняется ограничение (\(1 \le L \le R \le n\)).
На каждый запрос типа 2, во входной файл выведите ответ на него, в отдельной строке.
10 7 5 3 2 3 12 6 7 5 10 12 2 4 9 1 4 6 2 1 8 1 1 8 1 8 9 2 1 7 2 3 6
3 2 2 2
На вступительном экзамене по информатике в СУНЦ МГУ Вашему другу предложили реализовать структуру данных для хранения множеств чисел. Так как он специализируется на истории литературы, данную структуру придётся реализовать Вам.
Структура должна хранить m множеств чисел от 0 до n, при этом одно число может принадлежать сразу нескольким множествам.
Вы должны реализовать следующие операции на этой структуре:
ADD e s
Добавить в множество №s (0 <=
s <= m) число e (0 <= e <= n).
DELETE e s
Удалить из множества №s (0
<= s <= m) число e (0 <= e <= n). Гарантируется,
что до этого число e было помещено в
множество
CLEAR s
Очистить множество №s (0 <=
s <= m).
LISTSET s
Показать содержимое множества
№s (0 <= s <= m), либо -1, если множество
пусто.
LISTSETSOF e
Показать множества, в
которых лежит число e (0 <= e <= n), либо
-1, если этого числа нет ни в одном
множестве.
Сначала вводятся числа N (1 <= N <= 9223372036854775807), M (1 <= M <= 100000) и K (0 <= K <= 100000) — максимальное число, номер максимального множества и количество запросов к структуре данных. Далее следуют K строк указанного формата запросов.
На каждый запрос LISTSET Ваша программа должна вывести числа — содержимое запрошенного множества или -1, если множество пусто.
На каждый запрос LISTSETSOF Ваша программа должна вывести числа — номера множеств, содержащие запрошенное число или -1, если таких множеств не существует.
На прочие запросы не должно быть никакого вывода.
Гарантируется, что правильный вывод программы не превышает одного мегабайта.
10 10 9 ADD 1 1 ADD 1 2 ADD 2 1 LISTSET 1 LISTSETSOF 1 DELETE 1 1 LISTSET 1 CLEAR 1 LISTSET 1
1 2 1 2 2 -1
10 10 5 ADD 1 1 LISTSET 10 LISTSET 1 CLEAR 1 LISTSET 1
-1 1 -1