|
|
вернуться в форумПоказать все сообщения Спрятать все сообщенияРазве для 4 студентов будет всего 2 пары?
А чем не устраивает вариант:
3
1 2
2 3
1 4
Тогда 1 и 2 студенты имеют по 2 друга, а 3 и 4 по 1, что в свою очередь подходит под "крах критерия успеха". All three members of the team should have the same number of friends... The problem can has multiple correct answers.
Edited by author 09.10.2010 14:50 Iosif inf-10 : Sən harda oxuyursan? Достаточно и любой одной пары друзей - у них будет по 1, у других по 0. я так понял нужно построить такой граф чтобы любые три вершины имели разную степень.
а в условии сказано что решение можно вывести любое. LLd_team, такой вариант вполне пройдёт. Для удобства, можно составить на бумажке матрицу вида:
1 2 3 4
2 2 1 1
надеюсь, суть матрицы понятна ;)
Собственно программно и нужно постоянно проверять количество людей с одинаковым количеством друзей и "не давать" этому количеству превышать 2 (эмпирически выяснили, что -1 в принципе может и никогда не вернуться). У меня всегда есть ответ))
Пусть кол-во друзей четно. Пусть мы уже добавили 2k друзей и их валентности 112233...kk.
Давайте соединять 2 новые вершины с уже добавленными, начиная с тех, у кого большая валентность. Получим у новых вершин валентность 11, а у старых 1122..(k-1)(k-1)(k+1)(k+1). Продолжаем процесс пока не получим у новых mm, а у старых 112233...(m-1)(m-1)(m+1)(m+1)..(k+1)(k+1). Если получили, что на каком-то шаге у новых mm, а у старых 1122..(m)(m)(m+2)(m+2)..(k+1)(k+1), то соединяем новые между собой. Если n нечетно, последнюю вершину оставляем одной. Кол-во дуг в графе (n/2) * ((n/2) + 1) / 2. |
|
|
