Ответы к экзамену: Cистема eJudge Задачи

# Модуль 2

## Фильтр Блума(A)
Реализуйте фильтр Блума, позволяющий дать быстрый, но вероятностный ответ, присутствует ли объект в коллекции.

Реализация самой структуры данных должна быть инкапуслирована, т.е. не зависеть от форматов входных/выходных данных и непосредственно ввода/вывода.

Реализация битового массива также должна быть инкапсулирована. Массив битов должен быть эффективно расположен в памяти.

Параметрами структуры данных являются n - приблизительное количество элементов (целое), P - вероятность ложноположительного ответа.

Размер структуры, m, вычисляется как -n log2 P / ln 2, а количество хэш-функций - как -log2 P. Оба значения округляются до ближайшего целого.

В качестве семейства функций используйте семейство хэш-функций вида

hi(x) = (((i + 1)*x + pi+1) mod M) mod m,

где - x - ключ, i - номер хэш-функции, pi - i-тое по счету простое число, а M - 31ое число Мерсенна.

### Формат входных данных
На стандартном потоке ввода задаётся последовательность команд. Пустые строки игнорируются.

Первая строка содержит команду вида set n P.

Каждая последующая строка содержит ровно одну команду: add K, search K или print, где K - неотрицательное число (64 бита вам хватит), ключ.

### Формат результата
Команда set инициализирует структуру и выводит вычисленные параметры в формате "m k".

Команда add добавляет в структуру ключ K.

Команда search выводит либо "1", если элемент возможно присутствует в структуре, либо "0", если он там отсутствует.

Команда print выводит внутреннее состояние струтуры - последовательность из 0 и 1, не разделенную пробелами.

В любой непонятной ситуации результатом работы любой команды будет "error".

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

## Задача про косое дерево(B)
Реализуйте косое дерево (splay tree).

Реализация самой структуры данных должна быть инкапуслирована, т.е. не зависеть от форматов входных/выходных данных и непосредственно ввода/вывода.

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

### Формат входных данных
На стандартном потоке ввода задаётся последовательность команд. Пустые строки игнорируются.

Каждая строка содержит ровно одну команду: add K V, set K V, delete K, search K, min, max или print, где K - целое число (64 бита вам хватит), ключ, V - произвольная строка без пробелов (значение).

### Формат результата
Команда add добавляет значение V в дерево по ключу K, set - изменяет данные по ключу, команда delete удаляет данные.

Команда search выводит либо "1 V", либо "0", где V - значение для найденного ключа.

Команды min и max выводят "K V", где K - минимальный или максимальный ключ дерева соответственно, V - значение по этому ключу.

Команда print выводит все дерево целиком. Она не изменяет дерево.

Дерево выводится строго по уровням, слева направо, 1 строка - 1 уровень. Первая строка содержит только корень дерева в формате "[K V]" или "_", если дерево пустое.

Каждая последующая строка содержит один уровень дерева. Вершины выводятся в формате "[K V P]", где P - ключ родительской вершины. Если вершина отсутствует, ставится "_". Вершины разделены пробелом.

В любой непонятной ситуации результатом работы любой команды будет "error".

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

## Непростая куча(C)
Реализуйте двоичную min-кучу. Модифицируйте ее таким образом, чтобы внутреннее ее строение было таким же, но при этом доступ по ключу к любому элементу осуществлялся в среднем за константное время.

Реализация самой структуры данных должна быть инкапуслирована, т.е. не зависеть от форматов входных/выходных данных и непосредственно ввода/вывода.

### Формат входных данных
На стандартном потоке ввода задаётся последовательность команд. Пустые строки игнорируются.

Каждая строка содержит ровно одну команду: add K V, set K V, delete K, search K, min, max, extract или print, где K - целое число (64 бита вам хватит), ключ, V - произвольная строка без пробелов (значение).

### Формат результата
Команда add добавляет значение V в кучу по ключу K, set - изменяет данные по ключу, команда delete удаляет данные.

Команда search выводит либо "1 I V", либо "0", где I - индекс, V - значение для найденного ключа

Команды min и max выводят "K I V", где K - минимальный или максимальный ключ кучи соответственно, I - индекс, V - значение по этому ключу.

Команда extract извлекает корень кучи и выводит "K V", где K, V - ключ и значение извлеченного элемента.

Команда print выводит всю кучу целиком.

Куча выводится строго по уровням, слева направо, 1 строка - 1 уровень. Первая строка содержит только корень кучи в формате "[K V]" или "_", если куча пустая.

Каждая последующая строка содержит один уровень кучи. Вершины выводятся в формате "[K V P]", где P - ключ родительской вершины. Если вершина отсутствует, ставится "_". Вершины разделены пробелом.

В любой непонятной ситуации результатом работы любой команды будет "error".

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