Алгоритмы и структуры данных. Подгруппа 103-1 — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(→‎Второе домашнее задание)
Строка 33: Строка 33:
 
| 12 || Шафаростов || Артем ||<center><big>*</big></center>||  ||  || <center><big>*</big></center> ||<center><big>*</big></center>
 
| 12 || Шафаростов || Артем ||<center><big>*</big></center>||  ||  || <center><big>*</big></center> ||<center><big>*</big></center>
 
|}
 
|}
 +
 +
 +
В дополнение к задачам контекста необходимо решить одну "теоретическую" задачу. Те, кому досталась задача 2.1. RadioStation, решают первую из двух приведенных ниже задач, прочие — вторую.
 +
 +
(1) В задаче 2.1. RadioStation допустим, что каждая из ''n'' = 2''m'' радиостанций находится в радиусе действия не менее чем ''m'' других радиостанций. Докажите, что в этом случае существует возможность передачи сигнала между любыми двумя радиостанциями, или постройте пример, когда это не так.
 +
 +
(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.

Источник — «http://wiki.cs.hse.ru/index.php?title=Алгоритмы_и_структуры_данных._Подгруппа_103-1&oldid=1725»