Конкурсы и Олимпиады по Машинному программированию (КОМП) Разбор уровня 2
Началась последняя неделя конкурса. Заявки на участие уже не принимаются. Лидеры по-прежнему штурмуют уровень 5. Посмотрим, как выглядит рейтинг участников на данный момент.
Текущий рейтинг
Уровень 4
Палевич Владимир Александрович, Урбанович Дмитрий Владимирович, Прозоров Илья Сергеевич, Молодых Вадим Анатольевич, Белоусов Аркадий Владимирович.
Уровень 3
Остапенко Денис Александрович.
Уровень 2
Шуликин Илья Викторович, Бикмаматов Ильдар Тагирович, Коровкин Михаил Георгиевич, Федотова Анастасия Олеговна, Литвинов Владимир Александрович.
Уровень 1
Рура Виталий Александрович, Бусоргин Николай Рудольфович.
Разбор задачи уровня 2
Задача этого уровня называлась "Видимость". Видимость - свойство не симметричное, значит, если из одного дома видно другой, то наоборот не обязательно. Получается, что нужно найти последовательность украшений домов от A до заданного. Если переформулировать задачу на языке теории графов получается следующее. В направленном графе нужно найти путь между вершинами. Это одна из самых стандартных задач теории графов и её решение есть во всех книга посвящённых графам.