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

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

Сроки проведения: 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. RadioStation, решают первую из двух приведенных ниже задач, прочие — вторую.

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

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