В круг выстроено N человек, пронумерованных числами от 1 до N. Будем исключать каждого k-ого до тех пор,
пока не уцелеет только один человек. (Например, если N=10, k=3, то сначала умрет 3-й, потом 6-й,
затем 9-й, затем 2-й, затем 7-й, потом 1-й, потом 8-й, за ним - 5-й, и потом 10-й.
Таким образом, уцелеет 4-й.) Необходимо определить номер уцелевшего.
N, k ≤ 10000.
Требования: Решить перебором.
2) Бинарный поиск
Дан отсортированный массив различных целых чисел A[0..n-1] и массив целых чисел B[0..m-1].
Для каждого элемента массива B[i] найдите минимальный индекс элемента массива A[k], ближайшего
по значению к B[i].
Требования: Время работы поиска для каждого элемента B[i]: O(log(k)).
Внимание! В этой задаче для каждого B[i] сначала нужно определить диапазон для бинарного поиска
размером порядка k, а потом уже в нем делать бинарный поиск.
n ≤ 110000, m ≤ 1000.
3) Очередь с помощью двух стеков.
Использовать стек, реализованный с помощью динамического буфера.
Требования: Очередь должна быть реализована в виде класса.
Стек тоже должен быть реализован в виде класса.
4) Двоичная куча
Скользящий максимум
Дан массив натуральных чисел A[0..n), n не превосходит 10^8. Так же задан размер некоторого окна
(последовательно расположенных элементов массива) в этом массиве k, k<=n. Требуется для каждого
положения окна (от 0 и до n-k) вывести значение максимума в окне.
Требования: Скорость работы O(n log n), память O(n).
Формат входных данных. Вначале вводится n - количество элементов массива. Затем вводится n строк
со значением каждого элемента. Затем вводится k - размер окна.
Формат выходных данных. Разделенные пробелом значения максимумов для каждого положения окна.
5) Merge sort
В супермаркете решили оптимизировать показ рекламы. Известно расписание прихода и ухода
покупателей (два целых числа). Каждому покупателю необходимо показать минимум 2 рекламы.
Рекламу можно транслировать только в целочисленные моменты времени.
Покупатель может видеть рекламу от момента прихода до момента ухода из магазина.
В каждый момент времени может показываться только одна реклама. Считается,
что реклама показывается мгновенно. Если реклама показывается в момент ухода или прихода,
то считается, что посетитель успел её посмотреть. Требуется определить минимальное число показов рекламы.
6) Порядковая статистика
Даны неотрицательные целые числа n,k и массив целых чисел из [0..10^9] размера n.
Требуется найти k-ю порядковую статистику, т.е. напечатать число,
которое бы стояло на позиции с индексом k (0..n-1) в отсортированном массиве.
Требования: к дополнительной памяти: O(n). Среднее время работы: O(n).
Должна быть отдельно выделенная функция partition.
Рекурсия запрещена. Решение должно поддерживать передачу функции сравнения снаружи.
Функцию Partition реализуйте методом прохода двумя итераторами от начала массива к концу.
7) Binary MSD для long long.
Дан массив неотрицательных целых 64-разрядных чисел. Количество чисел не больше 106.
Отсортировать массив методом MSD по битам (бинарный QuickSort).
Модуль 2
1) Хеш таблица
Реализуйте структуру данных типа “множество строк” на основе динамической хеш-таблицы с открытой адресацией.
Хранимые строки непустые и состоят из строчных латинских букв. Хеш-функция строки должна быть реализована с
помощью вычисления значения многочлена методом Горнера. Начальный размер таблицы должен быть равным 8-ми.
Перехеширование выполняйте при добавлении элементов в случае, когда коэффициент заполнения таблицы достигает 3/4.
Структура данных должна поддерживать операции добавления строки в множество, удаления строки из множества и
проверки принадлежности данной строки множеству. Для разрешения коллизий используйте двойное хеширование.
2) Бинарное дерево
Дано число N < 106 и последовательность целых чисел из [-231..231] длиной N. Требуется построить
бинарное дерево, заданное наивным порядком вставки. Т.е., при добавлении очередного числа K в
дерево с корнем root, если root→Key ≤ K, то узел K добавляется в правое поддерево root; иначе
в левое поддерево root.
Требования: Рекурсия запрещена. Решение должно поддерживать передачу функции сравнения снаружи.
Выведите элементы в порядке level-order (по слоям, “в ширину”).
3) AVL дерево
Порядковые статистики.
Дано число N и N строк. Каждая строка содержит команду добавления или удаления натуральных
чисел, а также запрос на получение k-ой порядковой статистики. Команда добавления числа
A задается положительным числом A, команда удаления числа A задается отрицательным
числом “-A”. Запрос на получение k-ой порядковой статистики задается числом k.
Требования: скорость выполнения запроса - O(log n).
Модуль 3
1) Графы
Реализовать 4 представления графа, удовлетворяющие заданному интерфейсу.
2) Алгоритм Дейкстра
Дан невзвешенный неориентированный граф. В графе может быть несколько кратчайших путей между какими-то вершинами.
Найдите количество различных кратчайших путей между зад анными вершинами.
Требования: сложность O(V+E).
Формат ввода.
v: кол-во вершин (макс. 50000),
n: кол-во ребер (макс. 200000),
n пар реберных вершин,
пара вершин u, w для запроса.
Формат вывода.
Количество кратчайших путей от u к w.
3) Алгоритм Дейкстра для взмешенного графа
Требуется отыскать самый выгодный маршрут между городами.
Требования: время работы O((N+M)logN), где N-количество городов, M-известных дорог между ними.
Формат входных данных:
Первая строка содержит число N – количество городов.
Вторая строка содержит число M - количество дорог.
Каждая следующая строка содержит описание дороги (откуда, куда, время в пути).
Последняя строка содержит маршрут (откуда и куда нужно доехать).
Формат выходных данных:
Вывести длину самого выгодного маршрута.