Тема: Деревья поиска
1.Минимальная и максимальная высота
ограничение по времени на тест 1 секунда
ограничение по памяти на тест 256 мегабайт

Высотой корневого дерева называется длина максимального пути от корня до листа. Например, для дерева на рисунке высота равна 2, так как самый длинный путь от корня до листа имеет длину 2 ребра.

Вам дано одно целое число N — количество элементов в бинарном дереве. Найдите минимально возможную и максимально возможную высоту дерева с таким количеством элементов.


Входные данные
Вводится одно целое число N (1 ≤ N ≤ 1000) – количество элементов в бинарном дереве.

Выходные данные
Выведите два целых числа – минимально возможную и максимально возможную высоты дерева.


входные данные
5
выходные данные
2 4

ссылка для теста задачи: https://codeforces.com/group/50U9rD7F6W/contest/380514/problem/A


2.Корень декартова дерева
ограничение по времени на тест 1 секунда
ограничение по памяти на тест256 мегабайт

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

Пример декартова дерева показан на рисунке.

Вам известен ключ и приоритет в каждом узле дерева. Однако, о связях узлов вам информации не даётся. Определите:

1. который из узлов является корнем дерева
2. сколько узлов лежит в его левом и правом поддереве

Входные данные
В первой строке вводится целое число N (1 ≤ N ≤ 1000) — количество узлов декартова дерева. В каждой из следующих N строк вводятся по два числа — ключ и приоритет очередного узла (целые числа в интервале от 0 до 109). Гарантируется, что никакие два ключа и никакие два приоритета не совпадают. Узлы дерева даются в произвольном порядке.

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


входные данные
5
5 3
9 4
4 8
7 10
2 6

выходные данные
7 10
3 1

ссылка для теста задачи: https://codeforces.com/group/50U9rD7F6W/contest/380514/problem/B

Высота простого дерева поиска
ограничение по времени на тест 1 секунда
ограничение по памяти на тест 256 мегабайт


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

Вставка нового элемента x в дерево начинается с корневого узла. Сравним x с ключом в корне. Если они равны, то делать ничего не надо – вставка закончена. Если x меньше ключа в корне, то идём в левое поддерево, если больше – в правое. Продолжаем делать так до тех пор, пока идти станет больше некуда – в этом случае создаём новый листовой узел.

На рисунке показано дерево, полученное из пустого дерева после вставки элементов 8, 5, 7, 11, 9, 3, 6.

Высотой дерева называется длина максимального пути от корня до листа. Например, для дерева на рисунке высота равна 3, так как путь от от корня до листа с ключом 6 имеет длину 3.

Вам дана последовательность элементов, которые поочерёдно вставлялись в изначально пустое дерево. Требуется найти его высоту.


Входные данные
В первой строке входных данных записано целое число N (1 ≤ N ≤ 1000) – количество элементов. В следующей строке через пробел записаны N целых чисел – вставляемые элементы (все элементы не превышают по модулю 109).

Выходные данные
Выведите одно целое число – высоту дерева.


входные данные
7
8 5 7 11 9 3 6

выходные данные
3

входные данные
3
5 5 5

выходные данные
0

ссылка для теста задачи: https://codeforces.com/group/50U9rD7F6W/contest/380514/problem/C



Множество с поиском по номеру
ограничение по времени на тест 1 секунда
ограничение по памяти на тест 256 мегабайт

Вам требуется написать программу для работы со множеством целых чисел, реализующую следующие основные операции:

• вставка элемента. Если элемент уже есть во множестве, оно не изменяется;
• поиск элемента по его порядковому номеру (считая, что у самого маленького элемента номер 1, у следующего – 2 и так далее).

Входные данные
В первой строке входных данных записано целое число N – количество вставляемых элементов (1 ≤ N ≤ 105). В следующих N строках записана команда (add или get) и через пробел целое число x. В случае команды add число x – это элемент, который нужно вставить в множество. В случае команды get число x – это порядковый номер элемента, который нужно напечатать (гарантируется, что элемент с таким номером в множестве есть). Все элементы множества не превышают по модулю 109.

Выходные данные
Выведите ответ для каждой команды get.


входные данные
5
add 1
add 3
get 1
add 1
get 2

выходные данные
1
3

ссылка для теста задачи:https://codeforces.com/group/50U9rD7F6W/contest/380514/problem/D

Тема: теория чисел
Обратное число
ограничение по времени на тест 2 секунды
ограничение по памяти на тест 256 мегабайт

В этой задаче нужно ответить на 1≤t≤1051≤t≤105 запросов. Каждый запрос состоит из двух целых чисел 2≤p≤1092≤p≤109 и 0<a<p0<a<p, число pp является простым. На каждый запрос нужно вывести в отдельной строке целое число 0<b<p0<b<p такое что a⋅b−1a⋅b−1 делится на p.


Входные данные
В первой строке дано целое число tt — количество запросов. В следующих строках даны по два числа pipi и aiai.

Выходные данные
Выведите tt целых чисел (каждое число в отдельной строке) — ответы на запросы.


входные данные
4
5 1
5 2
5 3
5 4

выходные данные
1
3
2
4

ссылка для теста задачи:https://codeforces.com/group/50U9rD7F6W/contest/382612/problem/C