|
||||||||||||||||||
|
СодержаниеММ161Конкурсная задача ММ161 (РК-1) (3 балла) По мотивам задачи ММ132 (и ряда других) Граф G=<V,E> задан на множестве V = {1, 2, …, 1000000000000} по правилу: {a,b} ∈ E тогда и только тогда, когда сумма чисел a и b равна некоторой четной натуральной степени их разности. Найти число связных компонент G и диаметр наибольшей компоненты. Решение Приведу решение Дмитрия Пашуткина Обсуждение Соседние вершины цепочки длиной 1414212 - это, конечно же, последовательные треугольные числа. Подсчет числа связных компонент можно осуществить чуть проще. Для этого нет нужды находить число вершин в каждой компоненте. Достаточно убедиться отсутствии циклов и вычесть из числа вершин число ребер. Задача представлялась мне предельно легкой. Не зря же ее цена всего 3 балла (меньше в Марафоне не бывает). При этом неожиданно большим оказалось количество ошибок в присланных ответах. Полагаю, участники Марафона просто еще не обрели должную концентрацию после лета. Потому и ошибались: то, забывая о четности показателя степени; то, путаясь в арифметике; то, полагая диаметр цепи равным числу вершин… Поскольку цена задачи изначально невелика, самые незначительные ошибки остались безнаказанными. Награды за правильное решение задачи ММ161 Сергей Половинкин, Олег Полубасов, Евгений Гужавин и Дмитрий Пашуткин получают по 3 призовых балла. Алексей Волошин, Виктор Филимоненков, Николай Дерюгин и Анатолий Казмерчук получают по 2 призовых балла. Эстетическая оценка задачи - 4.1 балла
|
|||||||||||||||||
|
||||||||||||||||||
|