ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1779. Великая команда

Вопрос по примеру
Послано LLd_team 9 окт 2010 14:16
Разве для 4 студентов будет всего 2 пары?
А чем не устраивает вариант:
3
1 2
2 3
1 4
Тогда 1 и 2 студенты имеют по 2 друга, а 3 и 4 по 1, что в свою очередь подходит под "крах критерия успеха".
Re: Вопрос по примеру
Послано Tural Vugar Gulmammadov 9 окт 2010 14:41
All three members of the team should have the same number of friends...
Re: Вопрос по примеру
Послано Iosif inf-10 9 окт 2010 14:48
The problem can has multiple correct answers.

Edited by author 09.10.2010 14:50
Re: Вопрос по примеру
Послано Tural Vugar Gulmammadov 9 окт 2010 15:10
Iosif inf-10 : Sən harda oxuyursan?
Re: Вопрос по примеру
Послано Anton Chupin 9 окт 2010 15:20
Достаточно и любой одной пары друзей - у них будет по 1, у других по 0.
Re: Вопрос по примеру
Послано rArow 9 окт 2010 16:41
я так понял нужно построить такой граф чтобы любые три вершины имели разную степень.

а в условии сказано что решение можно вывести любое.
Re: Вопрос по примеру
Послано Anton Papin 14 окт 2010 02:33
LLd_team, такой вариант вполне пройдёт. Для удобства, можно составить на бумажке матрицу вида:
1 2 3 4
2 2 1 1

надеюсь, суть матрицы понятна ;)

Собственно программно и нужно постоянно проверять количество людей с одинаковым количеством друзей и "не давать" этому количеству превышать 2 (эмпирически выяснили, что -1 в принципе может и никогда не вернуться).
Re: Вопрос по примеру
Послано ValenKof 13 окт 2011 22:41
У меня всегда есть ответ))
Пусть кол-во друзей четно. Пусть мы уже добавили 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.