Алгоритмы и структуры данных. Подгруппа 103-1 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
.obj (обсуждение | вклад) |
.obj (обсуждение | вклад) (→Распределение задач) |
||
Строка 35: | Строка 35: | ||
− | В дополнение к задачам | + | В дополнение к задачам контеста необходимо решить одну "теоретическую" задачу. Те, кому досталась задача 2.1. RadioStation, решают первую из двух приведенных ниже задач, прочие — вторую. |
(1) В задаче 2.1. RadioStation допустим, что каждая из ''n'' = 2''m'' радиостанций находится в радиусе действия не менее чем ''m'' других радиостанций. Докажите, что в этом случае существует возможность передачи сигнала между любыми двумя радиостанциями, или постройте пример, когда это не так. | (1) В задаче 2.1. RadioStation допустим, что каждая из ''n'' = 2''m'' радиостанций находится в радиусе действия не менее чем ''m'' других радиостанций. Докажите, что в этом случае существует возможность передачи сигнала между любыми двумя радиостанциями, или постройте пример, когда это не так. | ||
(2) Обоснуйте корректность алгоритма, реализованного вами при решении задачи 3. Segments. | (2) Обоснуйте корректность алгоритма, реализованного вами при решении задачи 3. Segments. |
Версия 17:18, 2 марта 2015
Второе домашнее задание
Сроки проведения: 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.