Алгоритмы и структуры данных. Подгруппа 103-1

Преподаватель — Сергей Объедков.

Учебный ассистент — Рамиль Яруллин.

Первое домашнее задание

Ссылка на контест:
https://official.contest.yandex.ru/contest/1002

Второе домашнее задание

Сроки проведения: 24 февраля 17:00 – 9 марта 23:59.
Ссылка на контест:
https://official.contest.yandex.ru/contest/1085

Распределение задач

	Фамилия	Имя	1-1. Минимальный путь	1-2. Количество путей	2-1. RadioStations	2-2. Maze	3. Segments
1	Аветисян	Кристина	*		*		*
2	Атанов	Андрей		*		*	*
3	Баишев	Альберт		*	*		*
4	Гадецкий	Артем	*			*	*
5	Дубов	Дмитрий	*		*		*
6	Каглинская	Мария		*		*	*
7	Касаткин	Степан		*	*		*
8	Кириченко	Полина	*			*	*
9	Николич	Стефан	*		*		*
10	Слинкин	Николай		*		*	*
11	Фадеева	Анастасия		*	*		*
12	Шафаростов	Артем	*			*	*

Теоретические задачи

В дополнение к задачам контеста необходимо решить одну "теоретическую" задачу. Те, кому досталась задача 2.1. RadioStations, решают первую из двух приведенных ниже задач, прочие — вторую.

(1) В задаче 2.1. RadioStations допустим, что каждая из n = 2m радиостанций находится в радиусе действия не менее чем m других радиостанций. Докажите, что в этом случае существует возможность передачи сигнала между любыми двумя радиостанциями, или постройте пример, когда это не так.

(2) Обоснуйте корректность алгоритма, реализованного вами при решении задачи 3. Segments.

Решение теоретической задачи необходимо прислать (в формате PDF) по электронной почте преподавателю и учебному ассистенту до окончания контеста или принести в распечатанном виде на семинар 10 марта в 10:30. Рукописные решения (сканы рукописных решений и т.п.) не принимаются.

Третье домашнее задание

Ссылка на контест:
https://official.contest.yandex.ru/contest/1196

Первый вариант (задачи I-1, I-2 и 3): Аветисян Кристина, Атанов Андрей, Баишев Альберт, Гадецкий Артем, Дубов Дмитрий, Каглинская Мария

Второй вариант (задачи II-1, II-2 и 3): Касаткин Степан, Кириченко Полина, Николич Стефан, Слинкин Николай, Фадеева Анастасия, Шафаростов Артем

Решение третьей задачи нужно сопроводить доказательством корректности предложенного алгоритма.

Оценки

	Фамилия	Имя	д/з 1	д/з 2	д/з 3	д/з 4	д/з 5	к/р
1	Аветисян	Кристина	6	7	7	0		7
2	Атанов	Андрей	10	10	10	10		10
3	Баишев	Альберт	8	7	8	3		3
4	Гадецкий	Артем	10	10	10	10		4
5	Дубов	Дмитрий	9	9	7	3		4
6	Каглинская	Мария	10	10	10	3		6
7	Касаткин	Степан	5	6	7	10		2
8	Кириченко	Полина	10	10	10	7		6
9	Николич	Стефан	6	6	0	0		0
10	Слинкин	Николай	3	0	0	0		2
11	Фадеева	Анастасия	9	9	7	0		3
12	Шафаростов	Артем	10	10	7	3		4