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

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

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

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

Оценки

Кристина Аветисян 6

Андрей Атанов 10

Альберт Баишев 8

Артем Гадецкий 10

Дмитрий Дубов 9

Мария Каглинская 10

Степан Касаткин 5

Полина Кириченко 10

Стефан Николич 6

Николай Слинкин 3

Анастасия Фадеева 9

Артем Шафаростов 10

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

Сроки проведения: 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://www.dropbox.com/s/yiqyiinyn1ytx3c/jobs.txt?dl=0 Пример реализации алгоритмов поиска путей в графе: https://www.dropbox.com/s/npkdn70vouvuqkx/dirgraphs.py?dl=0