- Ввод/вывод отделены от решения.
- Не должно быть утечек памяти.
Обязательная задача
Дан базовый интерфейс для представления ориентированного графа:
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.
4
5
0 1
0 2
1 2
1 3
2 3
0 3
2
Обязательная задача
Требуется отыскать самый выгодный маршрут между городами.
Требования: время работы O((N+M)logN), где N - количество городов, M - известных дорог между ними.
- Первая строка содержит число N – количество городов.
- Вторая строка содержит число M - количество дорог.
- Каждая следующая строка содержит описание дороги (откуда, куда, время в пути).
- Последняя строка содержит маршрут (откуда и куда нужно доехать).
Вывести длину самого выгодного маршрута.
6
9
0 3 1
0 4 2
1 2 7
1 3 2
1 4 3
1 5 3
2 5 3
3 4 4
3 5 6
0 2
9
Написать алгоритм для решения игры в "пятнашки". Решением задачи является приведение к виду:
[ 1 2 3 4 ]
[ 5 6 7 8 ]
[ 9 10 11 12]
[ 13 14 15 0 ]
где 0 задает пустую ячейку.
Достаточно найти хотя бы какое-то решение. Число перемещений костяшек не обязано быть минимальным.
Начальная расстановка.
Если решение существует, то в первой строке выходного файла выведите минимальное число перемещений костяшек, которое нужно сделать, чтобы достичь выигрышной конфигурации, а во второй строке выведите соответствующую последовательность ходов:
- L означает, что костяшка сдвинулась влево
- R – вправо
- U – вверх
- D – вниз
Если таких последовательностей несколько, то выведите любую из них. Если же выигрышная конфигурация недостижима, то выведите в выходной файл одно число −1.
1 2 3 4
5 6 7 8
9 10 11 0
13 14 15 12
1
U
Найдите приближенное решение метрической неориентированной задачи коммивояжера в полном графе (на плоскости) с помощью минимального остовного дерева.
- Оцените качество приближения на случайном наборе точек, нормально распределенном на плоскости с дисперсией 1.
- Нормально распределенный набор точек получайте с помощью преобразования Бокса-Мюллера.
- При фиксированном N (количестве вершин графа) несколько раз запустите оценку качества приближения.
- Вычислите среднее значение и среднеквадратичное отклонение качества приближения для данного N.
- Запустите данный эксперимент для всех N в некотором диапазоне, например, [2, 10].
- Автоматизируйте запуск экспериментов.
- В решении требуется разумно разделить код на файлы. Каждому классу - свой заголовочный файл и файл с реализацией.
Вариант 1. Для построения минимального остовного дерева используйте алгоритм Крускала.
Вариант 2. Для построения минимального остовного дерева используйте алгоритм Прима.
В контесте протестируйте работу алгоритма построения минимального остовного дерева.
Примечание: Варианты в контесте - не те, который описаны здесь. Правильные варианты - здесь.
Обязательная задача
Реализуйте структуру данных типа "множество строк" на основе динамической хеш-таблицы с открытой адресацией. Хранимые строки непустые и состоят из строчных латинских букв.
- Хеш-функция строки должна быть реализована с помощью вычисления значения многочлена методом Горнера.
- Начальный размер таблицы должен быть равным 8-ми.
- Перехеширование выполняйте при добавлении элементов в случае, когда коэффициент заполнения таблицы достигает 3/4.
- Структура данных должна поддерживать операции добавления строки в множество, удаления строки из множества и проверки принадлежности данной строки множеству.
- В таблице запрещено хранение указателей на описатель элемента.
- Квадратичное пробирование. i-ая проба g(k, i) = g(k, i-1) + i (mod m). m - степень двойки.
- Двойное хеширование.
Каждая строка входных данных задает одну операцию над множеством. Запись операции состоит из типа операции и следующей за ним через пробел строки, над которой проводится операция.
Тип операции – один из трех символов:
+означает добавление данной строки в множество;-означает удаление строки из множества;?означает проверку принадлежности данной строки множеству.
Примечание: При добавлении элемента в множество НЕ ГАРАНТИРУЕТСЯ, что он отсутствует в этом множестве. При удалении элемента из множества НЕ ГАРАНТИРУЕТСЯ, что он присутствует в этом множестве.
Программа должна вывести для каждой операции одну из двух строк: OK или FAIL, в зависимости от того, встречается ли данное слово в нашем множестве.
+ hello
+ bye
? bye
+ bye
- bye
? bye
? hello
OK
OK
OK
FAIL
OK
FAIL
OK
Обязательная задача
Дано число N < 10^6 и последовательность целых чисел из [-2^31..2^31] длиной N.
Требуется построить бинарное дерево, заданное наивным порядком вставки. Т.е., при добавлении очередного числа K в дерево с корнем root:
- если root→Key ≤ K, то узел K добавляется в правое поддерево root;
- иначе в левое поддерево root.
Требования:
- Рекурсия запрещена.
- Решение должно поддерживать передачу функции сравнения снаружи.
Вход:
3
2 1 3
Выход:
1 2 3
Вход:
3
1 2 3
Выход:
1 2 3
Вход:
3
3 1 2
Выход:
1 2 3
Вход:
3
2 1 3
Выход:
2 1 3
Вход:
3
1 2 3
Выход:
1 2 3
Вход:
3
3 1 2
Выход:
3 1 2
Вход:
4
3 1 4 2
Выход:
3 1 2 4
Вход:
3
2 1 3
Выход:
1 3 2
Вход:
3
1 2 3
Выход:
3 2 1
Вход:
3
3 1 2
Выход:
2 1 3
Вход:
3
2 1 3
Выход:
2 1 3
Вход:
3
1 2 3
Выход:
1 2 3
Вход:
3
3 1 2
Выход:
3 1 2
Вход:
4
3 1 4 2
Выход:
3 1 4 2
Во всех задачах из следующего списка следует написать структуру данных, обрабатывающую команды 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.
Требования: Очередь должна быть реализована в виде класса.
Input:
3
3 44
3 50
2 44
Output:
YES
Input:
2
2 -1
3 10
Output:
YES
Input:
2
3 44
2 66
Output:
NO
Требования: Дек должен быть реализован в виде класса.
Input:
3
1 44
3 50
2 44
Output:
YES
Input:
2
2 -1
1 10
Output:
YES
Input:
2
3 44
4 66
Output:
NO
Требования: Очередь должна быть реализована в виде класса. Стек тоже должен быть реализован в виде класса.
Input:
3
3 44
3 50
2 44
Output:
YES
Input:
2
2 -1
3 10
Output:
YES
Input:
2
3 44
2 66
Output:
NO
Постройте B-дерево минимального порядка t и выведите его по слоям. В качестве ключа используются числа, лежащие в диапазоне 0..2^32 -1
- B-дерево должно быть реализовано в виде шаблонного класса.
- Решение должно поддерживать передачу функции сравнения снаружи.
Сначала вводится минимальный порядок дерева t. Затем вводятся элементы дерева.
Программа должна вывести B-дерево по слоям. Каждый слой на новой строке, элементы должны выводится в том порядке, в котором они лежат в узлах.
2
0 1 2 3 4 5 6 7 8 9
3
1 5 7
0 2 4 6 8 9
4
0 1 2 3 4 5 6 7 8 9
3
0 1 2 4 5 6 7 8 9
Обязательная задача
Решение должно поддерживать передачу функции сравнения снаружи.
В одной военной части решили построить в одну шеренгу по росту. Т.к. часть была далеко не образцовая, то солдаты часто приходили не вовремя, а то их и вовсе приходилось выгонять из шеренги за плохо начищенные сапоги. Однако солдаты в процессе прихода и ухода должны были всегда быть выстроены по росту – сначала самые высокие, а в конце – самые низкие. За расстановку солдат отвечал прапорщик, который заметил интересную особенность – все солдаты в части разного роста. Ваша задача состоит в том, чтобы помочь прапорщику правильно расставлять солдат, а именно для каждого приходящего солдата указывать, перед каким солдатом в строе он должен становится.
Требования: скорость выполнения команды - O(log n).
Первая строка содержит число N – количество команд (1 ≤ N ≤ 30 000). В каждой следующей строке содержится описание команды: число 1 и X если солдат приходит в строй (X – рост солдата, натуральное число до 100 000 включительно) и число 2 и Y если солдата, стоящим в строе на месте Y надо удалить из строя. Солдаты в строе нумеруются с нуля.
На каждую команду 1 (добавление в строй) вы должны выводить число K – номер позиции, на которую должен встать этот солдат (все стоящие за ним двигаются назад).
Ввод:
5
1 100
1 200
1 50
2 1
1 150
Вывод:
0
0
2
1
Дано число N и N строк. Каждая строка содержит команду добавления или удаления натуральных чисел, а также запрос на получение k-ой порядковой статистики. Команда добавления числа A задается положительным числом A, команда удаления числа A задается отрицательным числом "-A". Запрос на получение k-ой порядковой статистики задается числом k.
Требования: скорость выполнения запроса - O(log n).
Ввод:
5
40 0
10 1
4 1
-10 0
50 2
Вывод:
40
40
10
4
50
Напишите две функции для создания архива из одного файла и извлечения файла из архива.
Требования: коэффициент сжатия < 1.
// Метод архивирует данные из потока original
void Encode(IInputStream& original, IOutputStream& compressed);
// Метод восстанавливает оригинальные данные
void Decode(IInputStream& compressed, IOutputStream& original);где:
typedef unsigned char byte;
#define interface struct
interface IInputStream {
// Возвращает false, если поток закончился
virtual bool Read(byte& value) = 0;
};
interface IOutputStream {
virtual void Write(byte value) = 0;
};В архиве сохраняйте дерево Хаффмана и код Хаффмана от исходных данных. Дерево Хаффмана требуется хранить эффективно - не более 10 бит на каждый 8-битный символ.
В контест необходимо отправить .cpp файл содержащий функции Encode, Decode, а также включающий файл Huffman.h. Тестирующая программа выводит размер сжатого файла в процентах от исходного.
Лучшие 3 решения с коэффициентом сжатия < 1 из каждой группы оцениваются в 10, 7 и 4 баллов соответственно.
#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.
4
5
0 1
0 2
1 2
1 3
2 3
0 3
2
Обязательная задача
Требуется отыскать самый выгодный маршрут между городами.
Требования: время работы O((N+M)logN), где N-количество городов, M-известных дорог между ними.
- Первая строка содержит число N – количество городов.
- Вторая строка содержит число M - количество дорог.
- Каждая следующая строка содержит описание дороги (откуда, куда, время в пути).
- Последняя строка содержит маршрут (откуда и куда нужно доехать).
Вывести длину самого выгодного маршрута.
6
9
0 3 1
0 4 2
1 2 7
1 3 2
1 4 3
1 5 3
2 5 3
3 4 4
3 5 6
0 2
9
Написать алгоритм для решения игры в "пятнашки". Решением задачи является приведение к виду:
[ 1 2 3 4 ]
[ 5 6 7 8 ]
[ 9 10 11 12]
[ 13 14 15 0 ]
где 0 задает пустую ячейку.
Достаточно найти хотя бы какое-то решение. Число перемещений костяшек не обязано быть минимальным.
Начальная расстановка.
Если решение существует, то в первой строке выходного файла выведите минимальное число перемещений костяшек, которое нужно сделать, чтобы достичь выигрышной конфигурации, а во второй строке выведите соответствующую последовательность ходов:
- L означает, что костяшка сдвинулась влево,
- R – вправо,
- U – вверх,
- D – вниз.
Если таких последовательностей несколько, то выведите любую из них. Если же выигрышная конфигурация недостижима, то выведите в выходной файл одно число −1.
1 2 3 4
5 6 7 8
9 10 11 0
13 14 15 12
1
U
Найдите приближенное решение метрической неориентированной задачи коммивояжера в полном графе (на плоскости) с помощью минимального остовного дерева.
- Оцените качество приближения на случайном наборе точек, нормально распределенном на плоскости с дисперсией 1.
- Нормально распределенный набор точек получайте с помощью преобразования Бокса-Мюллера.
- При фиксированном N (количестве вершин графа) несколько раз запустите оценку качества приближения.
- Вычислите среднее значение и среднеквадратичное отклонение качества приближения для данного N.
- Запустите данный эксперимент для всех N в некотором диапазоне, например, [2, 10].
- Автоматизируйте запуск экспериментов.
- В решении требуется разумно разделить код на файлы. Каждому классу - свой заголовочный файл и файл с реализацией.
- Для построения минимального остовного дерева используйте алгоритм Крускала.
- Для построения минимального остовного дерева используйте алгоритм Прима.
В контесте протестируйте работу алгоритма построения минимального остовного дерева. (Варианты в контесте - не те, который описаны здесь. Правильные варианты - здесь.)