Задания

1. Реализуйте АТД Стек на односвязном списке (forward_list).

1. Реализуйте АТД Очередь на односвязном списке (forward_list).

1. Реализуйте АТД Очередь на vector, используя циклический буфер, с расширением размера в 2 раза при переполнении. Операция pop() должна выполняться за $O(1)$ , push() за $O(1)$ (амортизированная оценка).

1. Реализуйте АТД Массив на списке (list). Определите операцию [] и итератор с операциями it+=n и it-=n, имеющие оценку эффективности $O(n)$ .

2. Используя класс stack из STL решите следующую задачу.
Напишите функцию с использованием стека для проверки корректности XML-строки. XML-строка называется корректной, если она может быть получена по следующим правилам:

Пустая строка является корректной XML-строкой.
Если A и B — корректные XML-строки, то строка AB, получающаяся приписыванием строки B в конец строки A, также является корректной XML-строкой.
Если A — корректная XML-строка, то строка <X>A</X>, получающаяся приписыванием в начало A открывающегося тега, а в конец — закрывающегося с таким же именем, также является корректной XML-строкой. Здесь X — любая непустая строка из строчных букв латинского алфавита.

Например, представленные ниже строки:

<a></a>
<a><ab></ab><c></c></a>
<a></a><a></a><a></a>

являются корректными XML-строками, а такие строки как:

<a></b>
<a><b>
<a><b></a></b>

не являются корректными XML-строками.

2. Используя класс queue из STL решите следующую задачу.
(2736) Вывести простые числа среди чисел от 2 до $N$ , используя следующий алгоритм:
Первоначально очередь все числа от 2 до $N$ .

Взять первый элемент $X$ из входной очереди и напечатать.
В выходную очередь поместить числа из очереди, которые не кратны $X$ .
Поменять входную и выходную очередь (swap).
Пока очередь не пуста, то повторять дествия с шага 2.

Ввод содержит одно целое число $N$ ( $2 <= N<=100000$ ).

2. Используя класс stack из STL решите следующую задачу.
(2565) В новом процессоре PDP-1 (Prime Data Processor) есть специальная операция $"dec"(i,j,k)$ , которая уменьшает все ячейки памяти с $i$ -й по $j$ -ю включительно на целое положительное число $k$ . Разработчики процессора не сделали операцию для очистки (обнуления) памяти. Необходимо, используя только указанную операцию, очистить $n$ ячеек памяти, имеющих заданные начальные значения.
Напишите программу, которая определит наименьшее количество операций для обнуления памяти.
Первая строка ввода содержит одно целое число $n$ ( $1 <= n <= 10^5$ ) – количество обнуляемых ячеек. Вторая строка ввода содержит $n$ целых чисел $a_i$ ( $0 <= a_i <= 10^9$ , $0<= i < n$ ) – начальные значения ячеек памяти.
Вывести одно целое число – минимальное количество операций для обнуления памяти.

2. Используя класс queue из STL решите следующую задачу.
(2735) В игре в пьяницу карточная колода из $N$ карт ( $N$ – четное число) раздается поровну двум игрокам. Далее они вскрывают по одной верхней карте, и тот, чья карта старше, забирает себе обе вскрытые карты, которые кладутся под низ его колоды (верхней в этой паре становится карта победившего игрока). Тот, кто остается без карт - проигрывает.
Первая строка содержит одно целое четное число $N$ ( $2 <=N <= 100$ ). Первая строка содержит $N//2$ чисел, разделенных пробелами — номера карт первого игрока, вторая – аналогично $N//2$ карт второго игрока. Все числа различны. Карты перечислены сверху вниз, то есть каждая строка начинается с той карты, которая будет открыта первой.
Программа должна определить, кто выигрывает при данной раздаче, и вывести слово first или second, после чего вывести количество ходов, сделанных до выигрыша. Если на протяжении $10^6$ ходов игра не заканчивается, программа должна вывести слово error.

3. Определите АТД для хранения структуры XML-документа. Каждый элемент хранит имя тега, список атрибутов (пара имя-значение), последовательность вложенных элементов и указатели на родительский элемент, предыдущий и следующий. Перечислите методы АТД, обеспечивающие последовательный доступ к информации и её изменение, аргументы и возвращаемые значения каждого метода с комментариями.

3. Определите АТД для хранения информации об неориентированном графе: количество вершин $N$ , количество ребер, список всех ребер (пара из номеров вершин от 0 до $N-1$ ), списки номеров соседних вершин для каждой вершины. Перечислите методы АТД, обеспечивающие последовательный доступ к информации и её изменение, аргументы и возвращаемые значения каждого метода с комментариями.

3. Определите АТД для хранения информации о таблице базы данных: столбцы (количество и названия столбцов), строки со значениями (все значения в строке таблицы имеют тип string), ключи для получения строк таблицы в некотором порядке (для упрощения ключ включает только один столбец, т.е. ключ - это имя или номер столбца, а строки таблицы можно получать последовательно по одной в порядке возрастания значения в указанном столбце). Перечислите методы АТД, обеспечивающие последовательный доступ к информации и её изменение, аргументы и возвращаемые значения каждого метода с комментариями.

3. Определите АТД для хранения информации об электронной таблице: ячейки (идентифицируется номером столбца и строки), числовые значения или формулы в них, связи с другими ячейками, зависящих от её значения. Перечислите методы АТД, обеспечивающие последовательный доступ к информации и её изменение, аргументы и возвращаемые значения каждого метода с комментариями.

5. Напишите функцию для прямого (pre-order) обхода бинарного дерева, заданного следующей структурой:
struct node { int value; node *left, *right; };
К каждому значению, хранящемуся в дереве, функция применяет функцию, указанную в качестве аргумента:
void preorder(node *n, void (*f)(int));

5. Напишите функцию для обратного (post-order) обхода бинарного дерева, заданного следующей структурой:
struct node { int value; node *left, *right; };
К каждому значению, хранящемуся в дереве, функция применяет функцию, указанную в качестве аргумента:
void postorder(node *n, void (*f)(int));

5. Напишите функцию для симметричного (in-order) обхода бинарного дерева, заданного следующей структурой:
struct node { int value; node *left, *right; };
К каждому значению, хранящемуся в дереве, функция применяет функцию, указанную в качестве аргумента:
void inorder(node *n, void (*f)(int));

5. Напишите функцию обхода бинарного дерева по возрастанию глубины (с помощью очереди), заданного следующей структурой:
struct node { int value; node *left, *right; };
К каждому значению, хранящемуся в дереве, функция применяет функцию, указанную в качестве аргумента:
void BFSorder(node *n, void (*f)(int));

6. Используя декартово дерево из лекций решите следующую задачу.
(2379) Будем называть $i$ -й элемент последовательности $a_1, a_2, ..., a_N$ медианным, если количество элементов, меньших или равных $a_i$ среди элементов $a_1, a_2, ..., a_{i-1}$ , больше или равно количеству элементов, больших или равных $a_i$ среди элементов $a_{i+1}, a_{i+2}, ..., a_N$ . В последовательности может быть несколько медианных элементов.
Напишите программу, которая находит минимальный индекс медианного элемента.

6. Используя декартово дерево с неявным ключом из лекций решите следующую задачу.
(1442) Центральным элементом набора из $k$ чисел называется такой элемент, который после сортировки набора будет занимать в нём центральную позицию (то есть позицию номер $|~ k//2 ~|$ , считая с единицы). Числа добавляются в изначально пустой набор в заданном порядке. Требуется определить значения центрального элемента после добавления каждого числа.
Входной файла содержит количество чисел $n$ , за которым следуют $n$ целых чисел $a_i$ в порядке их добавления в набор. Выходной файл должен содержать $n$ целых чисел - значения центрального элемента после каждого добавления.

6. Используя декартово дерево из лекций и vector из STL решите следующую задачу.
(2374) На соревнования на программированию прибыло слишком много команд, чтобы их можно было показать на мониторе. Поэтому Пете приходится отслеживать успехи своей любимой команды, используя информацию о принятых задачах команд. Команды в рейтинге сортируются в порядке уменьшения успешно сданных задач, а при равенстве количества задач - в порядке увеличения штрафного времени. Если равны и количество задач и время, то команды упорядочиваются по их номеру. Любимая команда Пети имеет номер 1.
Первая строка ввода содержит два целых числа — количество команд $N$ ( $1 <= N <= 100000$ ) и количество событий $M$ ( $1 <= M <= 100000$ ). Далее следует $M$ строк, содержащих по два целых числа – информацию о произошедшем событии: номер команды $t$ ( $1 <= t <= N$ ), успешно сдавшей очередную задачу, и добавляемое штрафное время $p$ ( $1 <= p <= 1000$ ).
Вывести $M$ строк - в $i$ -й строке выводится рейтинг команды 1 после $i$ -го события.

6. Используя декартово дерево из лекций решите следующую задачу.
(2117) В магазине есть $N$ ювелирных украшений, каждое из них имеет некоторую массу $M_i$ и ценность $V_i$ . Мирко имеет $K$ мешков для хранения награбленного, и каждый мешок может содержать некоторую максимальную массу $C_i$ . Мирко планирует унести всю свою добычу в этих мешках, но не более одного ювелирного изделия в каждом мешке, с тем чтобы уменьшить вероятность их повреждения во время побега. Найти максимальную общую стоимость ювелирных изделий, которые Мирко может "освободить".
Первая строка ввода содержит два целых числа $N$ и $K$ ( $1 <= N, K <= 300 000$ ). Каждая из следующих $N$ строк содержит пару целых чисел $M_i$ и $V_i$ ( $1 <= M_i, V_i <= 1 000 000$ ). Каждая из следующих $K$ строк содержит одно целое число $C_i$ ( $1 <= C_i <= 100 000 000$ ).
Первая и единственная строка вывода должна содержать максимально возможную суммарную стоимость драгоценностей.

7. Используя дерево отрезков решите следующую задачу.
Есть массив, содержащий 100000 элементов, первоначально все элементы равны 0. В массиве производятся изменения элементов и требуется находить суммы части массива с $i$ -го по $j$ -ый элементы.
В первой строке содержится число $K$ ( $1<=K<=50000$ ) -- количество запросов. Далее следует $K$ строк, в каждой строке содержится либо команда "S $i$ $j$ $v$ ", где $1<=i≤j<=100000$ , $-100<=v<=100$ , заменяющая значения элементов с $i$ -го по $j$ -й массива на $v$ , либо команда "Q $i$ $j$ ", где $1<=i<=j<=100000$ , требующая вывести сумму части массива с $i$ -го по $j$ -ый элементы.
Для каждой команды 'Q' вывести на отдельной строке результат запроса

7. Используя дерево отрезков решите следующую задачу.
(2040) Мебибайту необходимо рассчитать энергетические нагрузки во время светомузыкального шоу. Управление $2^20$ лампочками происходит следующим образом. Для каждого такта музыкального сопровождения указаны два целых числа, определяющих диапазон номеров лампочек, состояние которых должно измениться на противоположное. Если лампочка была выключена, она должна загореться, а горящая лампочка -- погаснуть. В начальный момент времени все лампочки выключены. Напишите программу, определяющую количество горящих лампочек после выполнения каждой команды.
Первая строка ввода содержит одно целое число $N$ ( $1 <= N <= 100 000$ ) -- количество команд на переключение состояния лампочек. Далее следует $N$ строк, каждая строка содержит два целых числа $a_i$ и $b_i$ ( $1 <= a_i <= b_i <= 2^20$ ) - команда на переключение.
Вывести $N$ строк, в $i$ -ой строке вывести количество горящих лампочек после $i$ -ой команды.

7. Используя дерево отрезков решите следующую задачу.
(1969) Дана последовательность из $N$ целых неотрицательных чисел. Ваша задача заключается в том, чтобы уметь выполнять три вида запросов:
1. + $l$ $r$ $d$ -- прибавить ко всем числам на отрезке от $l$ до $r$ число $d$ ( $1 <= l <= r <= N$ , $0 <= d <= 10^9$ );
2. * $l$ $r$ $d$ -- умножить все числа на отрезке от $l$ до $r$ число $d$ ( $1 <= l <= r <= N$ , $0 <= d <= 10^9$ );
3. ? $p$ -вывести значение $p$ -го элемента в этой последовательности по модулю $10^9+7$ ( $1 <=p <= N$ ).
В первой строке входного файла задано целое число $N$ . В следующей строке задано $N$ целых неотрицательных чисел, элементы последовательности. Каждое из этих чисел не превосходит $10^9$ . В третьей строке задано число $М$ -- количество запросов. В последующих $M$ строках заданы запросы, соответствующие описанию из условия.
Для каждого запроса третьего вида выведите ответ на одной строке, в том порядке, в котором заданы запросы.

7. Используя дерево отрезков решите следующую задачу.
(876) Банки с красками нумеруются числами от 0 до 999999. Краски на склад поступают наборами, в каждом наборе содержится по одной банке для каждого номера краски от $a$ до $b$ включительно. Время от времени на склад приходит покупатель и забирает все банки с номерами большими или равными $k$ . В начале дня склад пустой.
Напишите программу для кладовщика, которая вычисляет количество банок, взятых покупателями.
Во входном файле журнал действий кладовщика. Строка "ADD $a$ $b$ ", где $a$ и $b$ -- целые числа ( $0 <= a <= b <= 999999$ ), означает, что на склад поступил набор с номерами банок от $a$ до $b$ . Строка "DEL $k$ ", где $k$ -- целое число ( $0 <= k <= 999999$ ), означает, что пришёл покупатель и забрал все банки с номерами большими или равными $k$ . Строка "END" является последней строкой в файле и означает конец рабочего дня кладовщика. Количество записей в файле не превышает 2000.
В выходной файл для каждой записи "DEL $k$ " в порядке их следования во входном файле вывести строку, содержащую одно число -- количество банок, взятых этим покупателем.

8. Используя map из STL напишите решение следующей задачи с эффективностью $O(N log N)$ .
Имеется список, первоначально пустой. Команда add $v$ добавляет $v$ в конец списка. Команда remove $v$ удаляет первое вхождение $v$ из списка. После каждой команды вывести "1", если в списке нет одинаковых элементов, или "2", если есть одинаковые.

8. Используя set из STL напишите решение следующей задачи с эффективностью $O(N log N)$ .
Дана последовательность из $n$ различных целых чисел, которые постепенно добавляются в множество. После каждого добавления числа выведите ближайшие числа из множества, меньшее и большее добавленного. Если какого-либо числа не существует, выведите символ '*'.

8. Используя map из STL напишите решение следующей задачи с эффективностью $O(N log N)$ .
Дана последовательность из $n$ целых чисел. Найти непрерывную подпоследовательность максимальной длины, в которой нет одинаковых элементов. Вывести длину и начальный индекс найденной подпоследовательности.

8. Используя set из STL напишите решение следующей задачи с эффективностью $O(N^2 log N)$ .
Дана последовательность $A$ из $n$ целых чисел. Найти количество различных значений для сумм, которые могут получиться при суммировании элементов с $i$ -го до $j$ -го ( $1<=i<=j<=n$ ): $sum_{k=i}^j A_k$ .

9. Сравните время работы set и unordered_set из STL для операций поиска с количеством элементов $N=100, 10000, 10^6, 10^7$ (например, измерить время поиска 10 существующих значений в наборе и 10 несуществующих). Ключами являются числа от 1 до $10^9$ . Результат оформить в виде таблицы, время в ns. Привести код, использованный для измерения времени для одного значения $N$ .

9. Сравните время работы set и unordered_set из STL для операций поиска с количеством элементов $N=100, 10000, 10^6, 10^7$ (например, измерить время поиска 10 существующих значений в наборе и 10 несуществующих). Ключами являются строки из случайных букв от a до z длиной ровно 16. Результат оформить в виде таблицы, время в ns. Привести код, использованный для измерения времени для одного значения $N$ .

9. Сравните время работы set и unordered_set из STL для операций добавления $N$ элементов, где $N=100, 10000, 10^6, 10^7$ . Ключами являются строки из случайных букв от a до z длиной ровно 16. Результат оформить в виде таблицы, время в ns. Привести код, использованный для измерения времени для одного значения $N$ .

9. Сравните время работы set и unordered_set из STL для операций добавления $N$ элементов, где $N=100, 10000, 10^6, 10^7$ . Ключами являются числа от 1 до $10^9$ . Результат оформить в виде таблицы, время в ns. Привести код, использованный для измерения времени для одного значения $N$ .

Реализовать полином через представление в виде вектора коэффициентов. В конструкторе задается набор коэффициентов $a_0, a_1, ..., a_{n-1}$ . Определить операции + и *.

Реализовать полином через представление на значениях в точках. В конструкторе задается набор пар точка-значение $(x_0,y_0), ..., (x_{n-1},y_{n-1})$ . Определить операцию +.

Реализовать полином через представление на значениях в точках. В конструкторе задается набор значений $y_0, ..., y_{n-1}$ , $x_0$ и $Delta x$ ( $x_i=x_0+i*Delta x$ ). Определить операцию +.

Реализовать полином через представление на значениях в точках. В конструкторе задается набор значений $y_0, ..., y_{n-1}$ , где в качестве $x_i=i$ . Определить операцию +.

Реализовать АТД через словарь по ключам map<pair<int,int>, double>. Определить эффективность операций + и * в зависимости от количества ненулевых элементов $K$ .

Реализовать АТД через список списков vector<list<pair<int,double>>>. Определить эффективность операций + и * в зависимости от количества ненулевых элементов $K$ . Рекомендуется поддерживать в методе set упорядочение списка по $j$ для повышения эффективности операций.

Реализовать АТД через список координат list<tuple<int,int,double>>. Определить эффективность операций + и * в зависимости от количества ненулевых элементов $K$ . Рекомендуется поддерживать в методе set упорядочение списка по $i,j$ для повышения эффективности операций.

Реализовать АТД через сжатое хранение строкой (см. лекции). Определить эффективность операций + и * в зависимости от количества ненулевых элементов $K$ .

Определить операцию *. Сравнить время умножения матриц размером $1000 xx 1000$ , меняя порядок циклов всеми 6 способами для уровня оптимизации O3. Результаты записать в таблицу, в которой будет указан порядок выполнения циклов и время выполнения в мкс.

Определить операцию *. Выполнить возведение матрицы $N xx N$ из целых чисел 0 и 1 в степень $K$ по модулю 2: $A^K (mod 2)$ . Для возведения матрицы в степень использовать метод уменьшения размера задачи в 2 раза.

Реализовать матрицу через vector размером $N*M$ . Определить операцию +. Сравнить время сложения матриц размером $1000 xx 1000$ , меняя порядок циклов (строки/столбцы и столбцы/строки) для уровня оптимизации O3. Результаты записать в таблицу, в которой будет указан порядок выполнения циклов и время выполнения в мкс.

Реализовать матрицу через vector из $N$ vector-ов размером $M$ . Определить операцию +. Сравнить время сложения матриц размером $1000 xx 1000$ , меняя порядок циклов (строки/столбцы и столбцы/строки) для уровня оптимизации O3. Результаты записать в таблицу, в которой будет указан порядок выполнения циклов и время выполнения в мкс.

Как матрица $N xx M$ из символов латинского алфавита. Клетки считаются связными, если в них находится одинаковая буква и они имеют общую границу.

(945) Как матрица $N xx M$ из клеток черного ('B') и белого ('W') цветов. Клетки считаются связными, если они имеют общую границу и цвета клеток отличаются (компонента раскрашена в черно-белую клетку как шахматная доска).

Как набор кругов с центром $(X_i,Y_i)$ диаметром $D$ . Круги считаются связными, если они накладываются друг на друга или соприкасаются краем.

Как набор натуральных чисел. Числа $a$ и $b$ считаются связанными, если $"gcd"(a,b)>1$ , т.е. у них есть какой-то общий делитель больше 1. Например, в наборе {1,3,7,9,14,15,16} три компоненты связности {1}, {7,14,16},{3,9,15}. Функция gcd определена в <numeric>

14. Используя поиск в ширину, решите задачу.
(1716) Стартовав с числа 1, нужно получить некоторое заданное число $N$ . На каждом шаге можно добавлять к текущему числу один из его делителей, чтобы получить новое число. Например, для первого шага у нас только один вариант: добавить 1 к 1 и получить 2. На втором шаге можно выбрать один из двух делителей и получить число 2+1=3 или 2+2=4. От числа 4 на третьем шаге можно перейти к числам 5, 6 или 8 в зависимости от выбранного делителя.
Напишите программу, определяющую минимальное количество шагов для получения заданного числа $N$ ( $2 ≤ N ≤ 10^5$ ).

14. Используя поиск в ширину, решите задачу.
(1310) Королевство Флатландия имеет форму прямоугольника размером $N xx M$ клеток. Для защиты Флатландия в нескольких клетках были построены крепости, в которых размещены войска. При нападении войско из крепостей пешим маршем отправляется к месту появления врага. Войско может переходить только в соседнюю клетку, имеющую общую границу с клеткой, где находится войско. Такой переход выполняется за 1 единицу времени. Некоторые клетки Флатландии, в которых находятся леса и озера, горы и равнины, являются непроходимыми для войск. Король хочет выяснить за какое минимальное время войска могут гарантированно добраться до остальных клеток страны.
Напишите программу, которая вычисляет это время для заданной карты Флатландии.
Первая строка ввода содержит два целых числа $N$ и $M$ – размеры Флатландии. Далее следует $N$ строк, содержащих по $M$ символов '#' (непроходимая для войск клетка), '.' (удобная для передвижения войск клетка) и '*' (клетка с крепостью). Гарантируется, что войска могут добраться до всех клеток, обозначенных символом '.', из какой-либо крепости.
Вывести одно целое число – минимальное время для достижения войсками любой клетки страны, обозначенной символом '.'.

14. Используя поиск в ширину, решите задачу.
(1343) На доске 8x8 некоторые клетки произвольным образом покрашены в черный цвет (кроме верхнего левого и правого нижнего угла доски). Требуется определить имеется ли путь для шахматного коня из верхнего левого в правый нижний угол доски, не проходящий по черным клеткам, и минимальное количество ходов, требующееся для этого.

14. Используя поиск в ширину, решите задачу.
(2340) Шерлок обнаружил за картиной сейф и хочет его открыть, чтобы узнать секретные планы Мориарти. У сейфа есть дисплей, на котором выводится числовой код, но вместо обычной клавиатуры только четыре кнопки: 2, 3, 5 и 7. Шерлок выяснил, что кнопка 2 делит число на дисплее на 2 нацело, кнопка 3 – умножает на 3, кнопка 5 – увеличивает на 5, а кнопка 7 – уменьшает на 7. Все операции, кроме деления, выполняются по модулю 101111. Также Шерлок нашел код, который должен высвечиваться на дисплее, чтобы сейф открылся, У Шерлока мало времени, поэтому ему нужно найти минимальную последовательность нажатий на кнопки, позволяющую получить код для открытия.
Ввод содержит два целых числа – код на дисплее $K$ и код для открытия $N$ ( $0 ≤ K, N < 101111$ , $K≤N$ ).
В первой строке вывести одно целое число – минимальное количество нажатий. Во второй строке вывести найденную последовательность без пробелов. Если существует несколько минимальных вариантов, то можно вывести любой из них.

15. Напишите функцию для проверки отсутствия циклов в орграфе, заданном через матрицу смежности.

15. Напишите функцию для проверки отсутствия циклов в орграфе, заданном через списки смежных вершин.

15. Напишите функцию для проверки, что в орграфе, заданном через матрицу смежности, существует эйлеров путь (путь, проходящий по всем дугам графа). Сам путь находить не нужно.

15. Напишите функцию для проверки, что в орграфе, заданном через списки смежных вершин, существует эйлеров путь (путь, проходящий по всем дугам графа). Сам путь находить не нужно.

16. Есть $n$ ( $2 ≤ n ≤ 10000$ ) городов, заданных своими координатами $(x_i, y_i)$ , $i in 1 ... n$ , а также $m$ ( $2 ≤ m ≤ 100000$ ) дорог, соединяющих города. Нужно построить дополнительное число дорог (возможно, нулевое), так чтобы из любого города можно было доехать в любой другой, двигаясь по дорогам. При этом сумма длин построенных дорог должна быть минимально возможной.
Укажите какой алгоритм построения минимального остовного дерева является более эффективным для решения этой задачи и обоснуйте свой выбор.

16. Есть $n$ ( $2 ≤ n ≤ 10000$ ) городов, заданных своими координатами $(x_i, y_i)$ , $i in 1 ... n$ . Нужно построить дороги, каждая из которых соединяет два города (без промежуточных ответвлений), так чтобы из любого города можно было доехать в любой другой, двигаясь по дорогам. При этом сумма длин построенных дорог должна быть минимально возможной.
Укажите какой алгоритм построения минимального остовного дерева является более эффективным для решения этой задачи и обоснуйте свой выбор.

16. На предприятии есть $n$ ( $2 ≤ n ≤ 10000$ ) отделов, между которыми которыми нужно проложить сеть. Есть $m$ ( $2 ≤ m ≤ 100000$ ) вариантов для соединения отделов между собой, описываемых тройкой $a_i, b_i, d_i$ , где $a_i, b_i$ - номера отделов, $d_i$ - длина кабеля. Для построения сети необходимо, чтобы все отделы прямо или косвенно через другие отделы были соединены между собой.
Укажите какой алгоритм построения минимального остовного дерева является более эффективным для решения этой задачи и обоснуйте свой выбор.

16. На предприятии есть $n$ ( $2 ≤ n ≤ 10000$ ) отделов, между отделами проложены кабели. Информация о проложенных кабелях представлена в виде части матрицы над основной диагональю. В $i$ -й строке $n-i$ чисел. Число -1, то отделы не соединены, положителльное число - длину кабеля, соединяющего отделы. Системный администратор решил убрать часть кабелей, чтобы, с одной стороны, все отделы прямо или косвенно через другие отделы остались соединены между собой, а, с другой стороны, длина сданного в металлом ненужного кабеля была максимальной.
Укажите какой алгоритм построения минимального остовного дерева является более эффективным для решения этой задачи и обоснуйте свой выбор.

17. Укажите какой алгоритм нужно использовать для решения задачи и обоснуйте свой выбор. Из каких вершин и ребер граф будет состоять?
Ферзь обошел шахматную доску и вернулся в стартовую клетку, побывав в каждой клетке ровно один раз. Заданы номер стартовой клетки и номера клеток, в которых ферзь побывал, на четных ходах. Необходимо найти номера клеток, в которых ферзь был на нечетных ходах, в порядке выполнения ходов.

17. Укажите какой алгоритм нужно использовать для решения задачи и обоснуйте свой выбор. Из каких вершин и ребер граф будет состоять?
О последовательности $A_1,..., A_N$ ( $1 ≤ N ≤ 200$ ), в которой каждое число от 1 до $N$ встречается ровно один раз, известно $M$ ( $0 ≤ M ≤ 40000$ ) ограничений вида:
1 $i$ $j$ $x$ – наибольшее число в позициях между $i$ и $j$ (включительно) равно $x$
2 $i$ $j$ $y$ – наименьшее число в позициях между $i$ и $j$ (включительно) равно $y$
Выведите любой вариант для такой последовательности.

17. Укажите какой алгоритм нужно использовать для решения задачи и обоснуйте свой выбор. Из каких вершин и ребер граф будет состоять?
Джон решил украсить дом иллюминацией к Рождеству. Он соединил проводами несколько ламп и подключил их к электросети. Затем Джон повернул рубильник, но некоторые лампы не загорелись. Напишите программу, которая определит, используя информацию о выполненных соединениях, какие лампы будут гореть.
В первой строке ввода содержатся два целых числа, разделенных пробелом – количество ламп $N$ ( $1≤N≤100$ ) и количество проводов $K$ ( $1≤K≤1000$ ). Далее следует $K$ строк, в каждой строке сначала указывается номер элемента (0 для электросети, от 1 до $N$ для лампы), к которому был присоединен один из концов провода, потом через пробел – номер контакта 1 или 2 (все элементы имеют два контакта), затем указывается элемент и контакт, к которому был присоединен другой конец провода, в том же формате.
В выходной файл в первой строке вывести $N$ целых чисел, разделяя их пробелами – если $i$ -ая лампа будет гореть, то $i$ -ое число должно быть равно 1, иначе 0. Лампа будет гореть, только если ее контакты подсоединены к вершинам с различными потенциалами. Провод имеет нулевое сопротивление, поэтому разность потенциалов на вершинах, соединенных между собой проводами без нагрузки в виде других ламп будет равна 0.

17. Укажите какой алгоритм нужно использовать для решения задачи и обоснуйте свой выбор. Из каких вершин и ребер граф будет состоять?
В парламенте есть комиссии. Каждый депутат может быть членом некоторых комиссий, в частности ни одной из них. Председатель каждой комиссии является ее членом. Никто из депутатов не может быть председателем более чем одной комиссии одновременно. В результате очередных выборов состав парламента не меняется. Комиссии были реформированы. Интересно, что все старые председатели снова стали председателями, но, может быть, и других комиссий. Напишите программу, определяющую председателей комиссий на основе состава комиссий старого и нового парламентов.
Первая строка входного файла содержит два целых числа $N$ и $K$ ( $2 ≤ N ≤ 100$ , $1 ≤ K ≤ N//2$ ), разделенные пробелом, где $N$ — количество депутатов в парламенте, а $K$ — количество комиссий. Следующие $K$ строк описывают состав старых комиссий. $i$ -я строка содержит целое число $P_i$ ( $1 ≤ P_i ≤ N$ ), равное количеству членов $i$ -й комиссии, а затем $P_i$ номеров. Все целые числа разделяются пробелами. Следующие $K$ строк описывают новые комиссии аналогичным образом. Запишите в выходной файл $K$ строк; $i$ -я строка должна содержать два целых числа, первое из которых — номер нового председателя $i$ -й комиссии, а второе — номер комиссии в старом парламенте, председателем которого он был.

18. Модифицируйте алгоритм Дейкстры для решения задачи:
В городе есть $N$ площадей, соединенных $M$ дорогами. Известна длина каждой дороги и номера площадей $a_i$ , $b_i$ ( $1<=a_i, b_i<=N$ ), соединенных этой дорогой. Посчитайте количество способов добраться с площади $A$ до площади $B$ так, чтобы пройденный путь был минимален.

18. Модифицируйте алгоритм Дейкстры для решения задачи:
В городе есть $N$ площадей, соединенных $M$ дорогами с односторонним движением. В городе прошел снегопад. Задана скорость движения по неубранной дороге $S_1$ и скорость движения по убранной дороге $S_2$ ( $S_2>S_1$ ). Известна длина каждой дороги $L_i$ , время начала уборки $T_i$ и номера площадей $a_i$ , $b_i$ ( $1<=a_i, b_i<=N$ ), соединенных этой дорогой. Уборка дороги выполняется со скоростью $S_1$ . Путешественнику необходимо добраться с площади $A$ до площади $B$ так, чтобы время было минимальным.

18. Модифицируйте алгоритм Дейкстры для решения задачи:
В некоторой игре участвует $N$ игроков, каждому из которых принадлежит один город. Между городами проложено $M$ дорог, каждая из которых соединяет некоторые два города и принадлежит одному из игроков (не обязательно владельцу города, которые она соединяет). Чтобы захватить город противника, правитель города $S$ должен довести свою армию до города $T$ . Все дороги, по которым перемещаются войска, должны принадлежать игроку. По правилам игры игрок может купить любую дорогу у ее владельца за определенную плату. У игрока $S$ нет в казне денег, поэтому сначала ему придется продать некоторые свои дороги (разумеется, после этого он не сможет провести по ним войска). Помогите игроку $S$ выяснить, какие дороги следует продать, а какие купить, чтобы довести войска от города $S$ до города $T$ . Все операции продажи и покупки дорог надо осуществить до начала похода, пока другие игроки не догадались о воинственных намерениях правителя города S.
Для каждой дороги задаются номера городов $a_i$ , $b_i$ ( $1<=a_i, b_i<=N$ ), стоимость дороги $c_i$ ( $1 <=c_i<=10000$ ) и номер владельца $o_i$ ( $1<=o_i<=N$ ).

18. Модифицируйте алгоритм Дейкстры для решения задачи:
Финну нужно срочно встретиться с Принцессой Бубльгум, которая в данный момент совершает утреннюю пробежку по круговому маршруту. Напишите программу, которая найдет минимальное время до встречи Финна и Принцессы.
Первая строка ввода содержит одно целое число — количество дорог

$M$ (

$2 ≤ M ≤ 100000$ ). Далее следует

$M$ строк, содержащих по три целых числа — номера перекрестков

$a_i$ и

$b_i$ , которые соединяет дорога, и длина дороги

$c_i$ (

$1 ≤ a_i, b_i, c_i ≤ 5000$ ,

$a_i ≠ b_i$ ). Далее следует строка, содержащая два целых числа — скорость Принцессы

$V_P$ (

$1 ≤ V_P ≤ 100$ ) и количество дорог

$K$ (

$2 ≤ K ≤ 1000$ ), по которым пробегает Принцесса. Следующая строка содержит

$K+1$ целое число — последовательность номеров перекрестков в маршруте Принцессе. Первый и последний номера в маршруте совпадают. В начальный момент времени Принцесса находится на первом перекрестке маршрута. В следующей строке содержится два целых числа — скорость Финна

$V_F$ (

$1 ≤ V_F ≤ 100$ ) и номер перекрестка

$S$ (

$1 ≤ S ≤ 5000$ ), на котором находится Финн в начальный момент времени. Гарантируется, что маршрут Принцессы проходит по существующим дорогам, между перекрестками не более одной дороги, и есть путь от

$S$ до маршрута Принцессы.
Вывести одно вещественное число — время до встречи Финна с Принцессой с точностью

$10^{-2}$ .

19. Напишите функцию для поиска строки в большом текстовом файле. Функции передается имя файла с текстом и строка длиной до $10^6$ символов. Функция должна вернуть позицию в файле, с которой начинается искомая строка. Вы можете использовать не более $3*10^6$ байт дополнительной памяти и можете считывать файл только последовательно. Файл в этой задаче содержит последовательность символов без разделения на строки (без \n). Оцените эффективность вашего алгоритма.

19. Напишите функцию для поиска большой строки в большом текстовом файле. Функции передается имя файла с текстом и имя файла со строкой. Функция должна вернуть позицию в файле, с которой начинается искомая строка. Можно открывать один файл несколько раз и перемещать позицию чтения в файле. Нельзя загрузить в память полностью всю строку или текст. Файлы в этой задаче содержат последовательности символов без разделения на строки (без \n). Оцените эффективность вашего алгоритма.

19. Напишите функцию для получения $K$ -го в порядке возрастания числа из двоичного файла, содержащего $N$ ( $N > 10^9$ ) 64-битных беззнаковых целых чисел. Функции передается имя файла с числами и $K$ . Можно считывать файл несколько раз. В памяти можно хранить не более 66000 64-битных чисел. Оцените эффективность вашего алгоритма.

19. Напишите функции для внешней сортировки набора из координат $N$ точек $(x_i,y_i)$ ( $0 ≤ x_i, y_i ≤ 10^5$ ). Координаты должны упорядочены сначала по $x_i$ , затем по $y_i$ . Функции передается имя файла. В первой строке файле содержится $N$ -- количество точек. Можно создавать вспомогательные файлы, не более 10 одновременно. Оцените эффективность вашего алгоритма.

20. Сравните время сортировки с помощью sort, stable_sort, make_heap/sort_heap для вектора из $10^6$ случайных чисел. Результаты оформить в виде таблицы.

20. Сравните время сортировки с помощью sort и timsort для последовательности из $10^6$ случайных чисел. Результаты оформить в виде таблицы. Реализация timsort на С++

20. Сравните время сортировки с помощью sort и поразрядной сортировки для последовательности из $10^6$ случайных беззнаковых целых чисел (за 1 разряд брать 1 байт числа). Результаты оформить в виде таблицы. Реализация на С++

20. Сравните время сортировки с помощью sort, stable_sort, multiset для последовательности из $10^6$ чисел от 1 до N и от N до 1. Результаты оформить в виде таблицы.

21. Напишите функцию поиска подстроки турбо-методом Бойера-Мура. Сравните время работы вашей функции с методом find и алгоритмом search с использованием boyer_moore_searcher из <functional> для текста размером $10^6$ символов и шаблона $10^4$ символов. Результаты представить в виде таблицы. Строки: 3 указанных алгоритма (Для алгоритма Бойер-Мура указать время, включая создание boyer_moore_searcher, и отдельно, исключая). Столбцы: 1) для случайного текста и шаблона; 2) текст 00...00, шаблон 00...01; 3) текст 00...00, шаблон 10...00.

21. Напишите функцию поиска подстроки методом Хорспула. Сравните время работы вашей функции с методом find и алгоритмом search с использованием boyer_moore_searcher из <functional> для текста размером $10^6$ символов и шаблона $10^4$ символов. Результаты представить в виде таблицы. Строки: 3 указанных алгоритма (Для алгоритма Бойер-Мура указать время, включая создание boyer_moore_searcher, и отдельно, исключая). Столбцы: 1) для случайного текста и шаблона; 2) текст 00...00, шаблон 00...01; 3) текст 00...00, шаблон 10...00.

21. Напишите функцию поиска подстроки методом Кнута-Мориса-Пратта. Сравните время работы вашей функции с методом find и алгоритмом search с использованием boyer_moore_searcher из <functional> для текста размером $10^6$ символов и шаблона $10^4$ символов. Результаты представить в виде таблицы. Строки: 3 указанных алгоритма (Для алгоритма Бойер-Мура указать время, включая создание boyer_moore_searcher, и отдельно, исключая). Столбцы: 1) для случайного текста и шаблона; 2) текст 00...00, шаблон 00...01; 3) текст 00...00, шаблон 10...00.

21. Напишите функцию поиска подстроки с помощью z-функции. Сравните время работы вашей функции с методом find и алгоритмом search с использованием boyer_moore_searcher из <functional> для текста размером $10^6$ символов и шаблона $10^4$ символов. Результаты представить в виде таблицы. Строки: 3 указанных алгоритма (Для алгоритма Бойер-Мура указать время, включая создание boyer_moore_searcher, и отдельно, исключая). Столбцы: 1) для случайного текста и шаблона; 2) текст 00...00, шаблон 00...01; 3) текст 00...00, шаблон 10...00.

22. Постройте сжатое суффиксное дерево для строки "senselessness" и найдите количеcтво различных подстрок в этой строке. Объясните способ подсчета с использованием суффиксного дерева.

22. Постройте сжатое суффиксное дерево для строки "околоколаколокола" и найдите количеcтво различных подстрок в этой строке. Объясните способ подсчета с использованием суффиксного дерева.

22. Постройте сжатое суффиксное дерево для строки "течетречкапечетпечка" и найдите количеcтво различных подстрок в этой строке. Объясните способ подсчета с использованием суффиксного дерева.

22. Постройте сжатое суффиксное дерево для строки "shesellsseashells" и найдите количеcтво различных подстрок в этой строке. Объясните способ подсчета с использованием суффиксного дерева.

23. Определите необходимые геометрические объекты и напишите следующую функцию
В декартовой системе координат на плоскости заданы координаты вершин треугольника и ещё одной точки. Определить, принадлежит ли эта точка треугольнику.

23. Определите необходимые геометрические объекты и напишите следующую функцию
В декартовой системе координат на плоскости заданы координаты концов отрезка и ещё одной точки. Определить расстояние от точки до отрезка.

23. Определите необходимые геометрические объекты и напишите следующую функцию
В декартовой системе координат на плоскости заданы окружность и точка вне неё. Найдите касательные к окружности, проходящие через точку.

23. Определите необходимые геометрические объекты и напишите следующую функцию
В декартовой системе координат на плоскости заданы две окружности. Найдите все касательные к этим окружностям (их может быть до 4).

24. Напишите функцию для проверки принадлежности точки невыпуклому многоугольнику. В качестве параметров функции передаются координаты точки и вектор координат вершин многоугольника против часовой стрелки.

24. Напишите функцию для нахождения стороны выпуклого многоугольника, ближайшей к его центру тяжести. В качестве параметра функции передается вектор координат вершин многоугольника против часовой стрелки. Многоугольник является сплошной фигурой.

24. Напишите функцию для нахождения пересечения двух выпуклых многоугольников (как сплошных фигур). В качестве параметров функции передается два вектора координат вершин многоугольника против часовой стрелки.

24. Напишите функцию для нахождения прямой, проходящей через заданную точку, которая делит выпуклый многоугольник на две равные по площади части. В качестве параметров функции передаются координаты точки и вектор координат вершин многоугольника против часовой стрелки. Для нахождения использовать дихотомию (при повороте на 180 градусов разница между площадями фигур слева и справа меняет знак - следовательно, есть угол, при котором она равна 0).

25. Напишите функцию бинарного возведения в степень по модулю M.

25. Напишите функцию разложения числа на простые множители.

25. Напишите функцию для нахождения решения диофантового уравнения $A*x+B*y=C$ , где $x ≥0, y ≥ 0$ . Если существует несколько вариантов, функция должна вернуть вариант с наименьшим $x$ .

25. Напишите функцию для получения всех простых чисел в диапазоне от $A$ до $B$ ( $1<A<B<10^12$ , $|B-A|<10^6$ ). Подсказка: сначала найдите простые числа до $10^6$ и используйте их для вычеркивания с помощью решета Эратосфена чисел из диапазона от $A$ до $B$ .

Назад

Подразделы

Другие разделы

Дата и время

Авторизация

Задания

Семестровое задание