Конкурсная задача ММ161 (РК-1) (3 балла)

По мотивам задачи ММ132 (и ряда других)

Граф G=<V,E> задан на множестве V = {1, 2, …, 1000000000000} по правилу: {a,b} ∈ E тогда и только тогда, когда сумма чисел a и b равна некоторой четной натуральной степени их разности. Найти число связных компонент G и диаметр наибольшей компоненты.

Решение

Приведу решение Дмитрия Пашуткина

Обсуждение

Соседние вершины цепочки длиной 1414212 - это, конечно же, последовательные треугольные числа.

Подсчет числа связных компонент можно осуществить чуть проще. Для этого нет нужды находить число вершин в каждой компоненте. Достаточно убедиться отсутствии циклов и вычесть из числа вершин число ребер.

Задача представлялась мне предельно легкой. Не зря же ее цена всего 3 балла (меньше в Марафоне не бывает). При этом неожиданно большим оказалось количество ошибок в присланных ответах. Полагаю, участники Марафона просто еще не обрели должную концентрацию после лета. Потому и ошибались: то, забывая о четности показателя степени; то, путаясь в арифметике; то, полагая диаметр цепи равным числу вершин… Поскольку цена задачи изначально невелика, самые незначительные ошибки остались безнаказанными.

Награды

за правильное решение задачи ММ161 Сергей Половинкин, Олег Полубасов, Евгений Гужавин и Дмитрий Пашуткин получают по 3 призовых балла. Алексей Волошин, Виктор Филимоненков, Николай Дерюгин и Анатолий Казмерчук получают по 2 призовых балла.

Эстетическая оценка задачи - 4.1 балла

---