| Фамилия, имя | Гр. | Задание |
| Айзенберг Алена | 1 | [1] Найти все мосты в графе. Мост — это ребро, при удалении которого в графе увеличивается число компонент связности. |
| Басалаев Андрей | 1 | [2] Реализовать сложение и вычитание чисел в троичной уравновешенной системе. На вход подается два числа в троичной уравновешенной системе (цифра -1 записывается как I). Вывести два числа: сумму и разность введенных чисел. |
| Богаева Мария | 1 | [3] Реализация дурной игры с вычеркиванием чисел. |
| Буканов Данияр | 1 | [4] Найти все вершины графа, удаленные от данной на расстояние меньше N (граф неориентированный, веса всех ребер равны 1). |
| Дорош Татьяна | 1 | [5] Построение дерева. Входной файл состоит из строк вида string value. Каждая строка задает некоторую вершину двоичного дерева: value — целое число, хранящееся в этой вершине, а string — путь к вершине. Путь к корню дерева — строка O, путь к любой другой вершине — строка из букв L и R (например, правый сын левого сына корня — LR). Вывести слово NO, если входной файл не задает дерево (т.е. есть неопределенные вершины), в противном случае вывести значения, хранящиеся в вершинах дерева, в порядке обхода в ширину. |
| Евсеева Ирина | 1 | [6] Проверка списка на зацикленность. Реализовать две функции: первая принимает в качестве параметра два положительных числа N и k, создает в памяти динамический однонаправленный список длиной N, зацикливает его на k-й элемент списка, начиная с нуля (если k=0, список не зацикливается), и возвращает указатель на начало этого списка. Вторая принимает в качестве параметра указатель на начало списка и возвращает 1, если список является зацикленным, 0 в противном случае. Во второй функции запрещено изменять список любым образом (помечать вершины, изменять указатели и т.д.) и выделять новую память. |
| Зудилин Дмитрий | 1 | [7] Задача про паркет с семинара. |
| Калинников Павел | 1 | [8] Задача I с олимпиады в Барнауле (про машину времени). Реализовать алгоритм Форда. |
| Катериненко Роман | 1 | [9] Динамическое программирование. Найти наибольшую подпоследовательность двух данных последовательностей (т.е. подпоследовательность максимальной длины). Последовательность an назовем подпоследовательностью последовательности bn, если все элементы an входят в bn в том же порядке (но не обязательно подряд). |
| Кашников Юрий | 1 | [10]
Задача коммивояжера. Дан взвешенный ориентированный граф с неотрицательными весами, в котором существует
хотя бы один гамильтонов цикл. Найти гамильтонов цикл наименьшей стоимости при помощи метода ветвей и границ. //заменена на более простую задачу [5] (Дорош Татьяна) |
| Копляров Дмитрий | 1 | [11] Динамическое программирование. Известно, что для подсчета произведения матриц необходимо N*M*K операций умножения, где N*M — размер первой матрицы, а M*K — размер второй матрицы. Известно также, что умножение матриц ассоциативно, т.е. A*(B*C) = (A*B)*C. Пусть дана последовательность матриц A1, A2,..., AN размеров n1*n2, n2*n3, ..., nN*nN+1. Найти оптимальный порядок, в котором следует перемножать эти матрицы (такой, чтобы число операций умножения было минимальным). |
| Лохматов Алексей | 1 | [12] Дана матрица размера N*N, заполненная целыми числами. Найти путь из элемента (1,1) в элемент (N,N), такой, что сумма чисел на этом пути будет максимальной. Двигаться можно только вправо и вниз. |
| Подберезный Андрей | 1 | [13] Задача о почтальоне. Дан взвешенный ориентированный граф. Построить путь, который начинается в первой вершине, проходит по каждому ребру (не обязательно по одному разу) и возвращается в первую вершину. |
| Слободенюк Денис | 1 | [14] Переливания. Даны три ведра емкостью N, M и K литров, причем 12 ≥ N ≥ M ≥ K ≥ 1. Первоначально ведро емкостью N литров заполнено водой полностью, остальные ведра пустые. Можно ли в результате последовательности переливаний получить в каком-либо ведре ровно Q литров воды? Все числа целые. |
| Соколова Дарья | 1 | [15] Проверить, можно ли раскрасить вершины данного граф в два цвета (черный и белый) так, чтобы никакие две смежных вершины не были раскрашены в один цвет. Вывести цвет каждой вершины, если это возможно. |
| Дюков Евгений | 2 | [16] Проверить, существует ли в графе эйлеров цикл. Если да, построить его. |
| Левченко Наталья | 2 | [17] Задача о «рыбе» в домино. На вход подаются пары целых чисел из интервала 0..6, каждая пара встречается не более чем один раз (без учета порядка чисел в паре). Каждая пара описывает кость домино. Определить, образуют ли эти кости «рыбу», т.е. можно ли составить из них замкнутый цикл, использовав все кости. Если да, вывести этот цикл. |
| Лукашов Виктор | 2 | [18] Найти минимальное число ходов, которое необходимо шахматному коню для перехода с одного поля на другое. |
| Лыков Кирилл | 2 | [19] Переливания. Даны три ведра емкостью N, M и K литров, причем 12 ≥ N ≥ M ≥ K ≥ 1. Первоначально ведро емкостью N литров заполнено водой полностью, остальные ведра пустые. Можно ли в результате последовательности переливаний получить в каком-либо ведре ровно Q литров воды? Все числа целые. |
| Молчанов Максим | 2 | [20] Найти все вершины графа, удаленные от данной на расстояние больше N (граф неориентированный, веса всех ребер равны 1). |
| Монид Светлана | 2 | [21] Задача о ранце. Даны стоимости и массы N предметов (целые числа от 0 до 100) и максимальная масса, которую может выдержать ранец (целое число от 0 до 100). Необходимо заполнить ранец оптимально (таким образом, чтобы стоимость вошедших предметов была бы максимальной). |
| Наполов Сергей | 2 | [22] Расставить на шахматной доске 8 ферзей так, чтобы они не били друг друга. Подсчитать количество возможных вариантов такой расстановки. |
| Порываева Дарья | 2 | [23] Найти все вершины графа, находящиеся от данной на расстоянии N (граф неориентированный, веса всех ребер равны 1). |
| Семенов Иван | 2 | [24] Проверить, является ли данный граф двудольным, т.е. что его вершины можно разбить на две группы (доли) так, что никакие две вершины из одной доли не являлись бы смежными. |
| Таубер Надежда | 2 | [25] Во входном файле находится последовательность чисел произвольной длины, каждое из которых лежит в интервале от 0 до 400000. Вывести числа, которые встречаются в исходной последовательности более одного раза. Разрешено использовать не более 64К памяти. |
| Устинов Антон | 2 | [26] Найти максимальное паросочетание в двудольном графе. Граф задается списком ребер, нумерация вершин в каждой доле начинается с единицы. |
| Хворостинин Иван | 2 | [27] Найти диаметр графа (наибольшее растояние между вершинами графа). |
| Черенкова Ксения | 2 | [28] Выполнить правильную раскраску вершин графа (т.е. раскрасить вершины в несколько цветов таким образом, чтобы никакие две смежные вершины не были раскрашены в один цвет). |
| Шмаков Дмитрий | 2 | [29] Определить, существует ли в графе цикл. |