Дан массив целых чисел А[0..n-1]. Известно, что на интервале [0, m] значения массива строго возрастают, а на интервале [m, n-1] строго убывают. Найти m за O(log m).
Требования: Время работы O(log m). Внимание! В этой задаче сначала нужно определить диапазон для бинарного поиска размером порядка m с помощью экспоненциального поиска, а потом уже в нем делать бинарный поиск.
Во всех задачах из следующего списка следует написать структуру данных, обрабатывающую команды push* и pop*. Формат входных данных.
В первой строке количество команд n. n ≤ 1000000.
Каждая команда задаётся как 2 целых числа: a b.
- a = 1 - push front
- a = 2 - pop front
- a = 3 - push back
- a = 4 - pop back
Команды добавления элемента 1 и 3 заданы с неотрицательным параметром b.
Для очереди используются команды 2 и 3. Для дека используются все четыре команды.
Если дана команда pop*, то число b - ожидаемое значение. Если команда pop вызвана для пустой
структуры данных, то ожидается “-1”.
Требуется напечатать YES - если все ожидаемые значения совпали. Иначе, если хотя бы одно ожидание не оправдалось, то напечатать NO.
Реализовать дек с динамическим зацикленным буфером (на основе динамического массива). Требования: Дек должен быть реализован в виде класса.
Напишите программу, которая использует кучу для слияния K отсортированных массивов суммарной длиной N.
Время работы O(N * logK)
Куча должна быть реализована в виде шаблонного класса.
Решение должно поддерживать передачу функции сравнения снаружи.
Куча должна быть динамической.
Сначала вводится количество массивов K. Затем по очереди размер каждого массива и элементы массива. Каждый массив упорядочен по возрастанию.
Итоговый отсортированный массив.
Дано множество целых чисел из [0..10^9] размера n. Используя алгоритм поиска k-ой порядковой статистики, требуется найти следующие параметры множества:
-
10% перцентиль
-
медиана
-
90% перцентиль
-
Требования: к дополнительной памяти: O(n).
-
Среднее время работы: O(n)
Должна быть отдельно выделенная функция partition. Рекурсия запрещена. Решение должно поддерживать передачу функции сравнения снаружи.
Функцию Partition следует реализовывать методом прохода двумя итераторами в одном направлении. Описание для случая прохода от начала массива к концу:
- Выбирается опорный элемент. Опорный элемент меняется с последним элементом массива.
- Во время работы Partition в начале массива содержатся элементы, не бОльшие опорного. Затем располагаются элементы, строго бОльшие опорного. В конце массива лежат нерассмотренные элементы. Последним элементом лежит опорный.
- Итератор (индекс) i указывает на начало группы элементов, строго бОльших опорного.
- Итератор j больше i, итератор j указывает на первый нерассмотренный элемент.
- Шаг алгоритма. Рассматривается элемент, на который указывает j. Если он больше опорного, то сдвигаем j. Если он не больше опорного, то меняем a[i] и a[j] местами, сдвигаем i и сдвигаем j.
- В конце работы алгоритма меняем опорный и элемент, на который указывает итератор i.
Функцию Partition реализуйте методом прохода двумя итераторами от конца массива к началу.
Дан массив строк. Количество строк не больше 100000. Отсортировать массив методом поразрядной сортировки MSD по символам. Размер алфавита - 256 символов. Последний символ строки = ‘\0’.
Реализуйте структуру данных типа “множество строк” на основе динамической хеш-таблицы с открытой адресацией. Хранимые строки непустые и состоят из строчных латинских букв.
Хеш-функция строки должна быть реализована с помощью вычисления значения многочлена методом Горнера.
Начальный размер таблицы должен быть равным 8-ми. Перехеширование выполняйте при добавлении элементов в случае, когда коэффициент заполнения таблицы достигает 3/4.
Структура данных должна поддерживать операции добавления строки в множество, удаления строки из множества и проверки принадлежности данной строки множеству.
Для разрешения коллизий используйте двойное хеширование.
Требования: В таблице запрещено хранение указателей на описатель элемента.
Каждая строка входных данных задает одну операцию над множеством. Запись операции состоит из типа операции и следующей за ним через пробел строки, над которой проводится операция. Тип операции один из трех символов:
-
+означает добавление данной строки в множество; -
-означает удаление строки из множества; -
?означает проверку принадлежности данной строки множеству.
При добавлении элемента в множество НЕ ГАРАНТИРУЕТСЯ, что он отсутствует в этом множестве. При удалении элемента из множества НЕ ГАРАНТИРУЕТСЯ, что он присутствует в этом множестве.
Программа должна вывести для каждой операции одну из двух строк OK или FAIL, в зависимости от того, встречается ли данное слово в нашем множестве.
Дано число N < 106 и последовательность целых чисел из [-231..231] длиной N. Требуется построить бинарное дерево, заданное наивным порядком вставки. Т.е., при добавлении очередного числа K в дерево с корнем root, если root->Key ≤ K, то узел K добавляется в правое поддерево root; иначе в левое поддерево root. Требования: Рекурсия запрещена. Решение должно поддерживать передачу функции сравнения снаружи. 2_2. Выведите элементы в порядке pre-order (сверху вниз).
Постройте B-дерево минимального порядка t и выведите его по слоям. В качестве ключа используются числа, лежащие в диапазоне [0..2^32-1]
- B-дерево должно быть реализовано в виде шаблонного класса.
- Решение должно поддерживать передачу функции сравнения снаружи.
Сначала вводится минимальный порядок дерева t. Затем вводятся элементы дерева.
Программа должна вывести B-дерево по слоям. Каждый слой на новой строке, элементы должны выводится в том порядке, в котором они лежат в узлах.
Солдаты. В одной военной части решили построить в одну шеренгу по росту. Т.к. часть была далеко не образцовая, то солдаты часто приходили не вовремя, а то их и вовсе приходилось выгонять из шеренги за плохо начищенные сапоги. Однако солдаты в процессе прихода и ухода должны были всегда быть выстроены по росту – сначала самые высокие, а в конце – самые низкие. За расстановку солдат отвечал прапорщик, который заметил интересную особенность – все солдаты в части разного роста. Ваша задача состоит в том, чтобы помочь прапорщику правильно расставлять солдат, а именно для каждого приходящего солдата указывать, перед каким солдатом в строе он должен становится.
Первая строка содержит число N – количество команд (1 ≤ N ≤ 30 000). В каждой следующей строке содержится описание команды: число 1 и X если солдат приходит в строй (X – рост солдата, натуральное число до 100 000 включительно) и число 2 и Y если солдата, стоящим в строе на месте Y надо удалить из строя. Солдаты в строе нумеруются с нуля.
На каждую команду 1 (добавление в строй) вы должны выводить число K – номер позиции, на которую должен встать этот солдат (все стоящие за ним двигаются назад).
Напишите две функции для создания архива из одного файла и извлечения файла из архива. Метод архивирует данные из потока original
void Encode(IInputStream& original, IOutputStream& compressed);Метод восстанавливает оригинальные данные
void Decode(IInputStream& compressed, IOutputStream& original);где:
typedef char byte;
interface IInputStream {
// Возвращает false, если поток закончился
virtual bool Read(byte& value) = 0;
};
interface IOutputStream {
virtual void Write(byte value) = 0;
};В архиве сохраняйте дерево Хаффмана и код Хаффмана от исходных данных. Дерево Хаффмана требуется хранить эффективно - не более 10 бит на каждый 8-битный символ. В контест необходимо отправить .cpp файл содержащий функции Encode, Decode, а также включающий файл Huffman.h. Тестирующая программа выводит размер сжатого файла в процентах от исходного.
Пример минимального решения:
#include "Huffman.h"
static void copyStream(IInputStream&input, IOutputStream& output) {
byte value;
while(input.Read(value)) { output.Write(value); }
}
void Encode(IInputStream& original, IOutputStream& compressed) {
copyStream(original, compressed);
}
void Decode(IInputStream& compressed, IOutputStream& original) {
copyStream(compressed, original);
}Дан базовый интерфейс для представления ориентированного графа:
struct IGraph {
virtual ~IGraph() {}
// Добавление ребра от from к to.
virtual void AddEdge(int from, int to) = 0;
virtual int VerticesCount() const = 0;
virtual std::vector<int> GetNextVertices(int vertex) const = 0;
virtual std::vector<int> GetPrevVertices(int vertex) const = 0;
};Необходимо написать несколько реализаций интерфейса:
-
ListGraph, хранящий граф в виде массива списков смежности, -
MatrixGraph, хранящий граф в виде матрицы смежности, -
SetGraph, хранящий граф в виде массива хэш-таблиц/сбалансированных деревьев поиска, -
ArcGraph, хранящий граф в виде одного массива пар {from, to}.
Также необходимо реализовать конструктор, принимающий const IGraph&. Такой конструктор должен скопировать
переданный граф в создаваемый объект.
Для каждого класса создавайте отдельные h и cpp файлы. Число вершин графа задается в конструкторе каждой реализации.
Дан невзвешенный неориентированный граф. В графе может быть несколько кратчайших путей между какими-то вершинами. Найдите количество различных кратчайших путей между заданными вершинами.
сложность O(V+E).
- v: кол-во вершин (макс. 50000),
- n: кол-во ребер (макс. 200000),
n пар реберных вершин, пара вершин u, w для запроса.
Количество кратчайших путей от u к w.
Требуется отыскать самый выгодный маршрут между городами.
-
Первая строка содержит число N – количество городов.
-
Вторая строка содержит число M - количество дорог.
-
Каждая следующая строка содержит описание дороги (откуда, куда, время в пути).
-
Последняя строка содержит маршрут (откуда и куда нужно доехать).
- Вывести длину самого выгодного маршрута.
Написать алгоритм для решения игры в “пятнашки”. Решением задачи является приведение к виду:
[ 1 2 3 4 ]
[ 5 6 7 8 ]
[ 9 10 11 12]
[ 13 14 15 0 ]
, где 0 задает пустую ячейку. Достаточно найти хотя бы какое-то решение. Число перемещений костяшек не обязано быть минимальным.
Начальная расстановка.
Если вам удалось найти решение, то в первой строке файла выведите число перемещений, которое требуется сделать в вашем решении. А во второй строке выведите соответствующую последовательность ходов: L означает, что в результате перемещения костяшка сдвинулась влево, R – вправо, U – вверх, D – вниз. Если же выигрышная конфигурация недостижима, то выведите в выходной файл одно число −1.
Найдите приближенное решение метрической неориентированной задачи коммивояжера в полном графе (на плоскости) с помощью минимального остовного дерева.
Оцените качество приближения на случайном наборе точек, нормально распределенном на плоскости с дисперсией 1. Нормально распределенный набор точек получайте с помощью преобразования Бокса-Мюллера.
При фиксированном N, количестве вершин графа, несколько раз запустите оценку качества приближения. Вычислите среднее значение и среднеквадратичное отклонение качества приближения для данного N.
Запустите данный эксперимент для всех N в некотором диапазоне, например, [2, 10]. Автоматизируйте запуск экспериментов.
В решении требуется разумно разделить код на файлы.
Каждому классу - свой заголовочный файл и файл с реализацией.
-
Вариант 1. Для построения минимального остовного дерева используйте алгоритм Крускала.
-
Вариант 2. Для построения минимального остовного дерева используйте алгоритм Прима.
В контесте протестируйте работу алгоритма построения минимального остовного дерева. (Варианты в контесте - не те, который описаны здесь. Правильные варианты - здесь.)