6270. Дети в Дружественном Классе
Кевин помнит свой класс в
начальной школе. В его классе Были девочки и мальчики. Некоторые из них были
друзьями, а некоторые и нет. Но если один человек является другом другому, то
обратное утверждение также верно.
Интересно, что каждая
девочка имеет в точности a друзей
среди девочек и точно b друзей среди
мальчиков, в то время как каждый мальчик имеет в точности с друзей среди девочек и ровно d
друзей среди мальчиков.
Кевин не помнит количество
детей в классе. Помогите ему восстановить класс с минимальным возможным числом
детей таким образом, чтобы все вышеуказанные условия были удовлетворены.
Вход. Четыре целых числа a,
b, c и d (1 ≤ a, b, c,
d ≤ 50).
Выход. Выведите пример
класса с минимальным количеством детей, удовлетворяющего выше перечисленным
условиям.
В первой строке выведите
два натуральных числа: m – количество
девочек, и n – количество мальчиков.
Присвоим числа от 1 до m девочкам, а от m + 1 до m + n - мальчикам.
Каждая следующая строка
должна содержать пару различных чисел, описывающих пару друзей. Каждую пару
друзей следует вывести только один раз.
Пример входа
1 2 1 2
Пример
выхода
2 4
1 2
1 3
1 5
2 4
2 6
3 4
3 5
4 6
5 6
математика + перебор
Пусть в классе имеется m девочек и n мальчиков.
Составим соотношения между указанными значениями.
1. Пусть между девочками и мальчиками имеется k ребер. Из каждой девочки к мальчикам
исходит b ребер (k = m * b). Из каждого мальчика к девочкам
исходит c ребер (k = n * c). Следовательно m * b = n * c.
2. Пусть между девочками имеется l ребер. Из каждой девочки к остальным девочкам исходит a ребер. При этом каждое ребро считается
дважды (l = m * a / 2). То есть
произведение m * a должно быть четным. Аналогично произведение n * d также будет четным.
3. Поскольку из каждой
девочки к остальным девочкам исходит a ребер, то m
≥ a + 1. Аналогично n ≥ d + 1.
Следует полным перебором
найти такие m и n, удовлетворяющие всем указанным условиям, и выбрать пару, для
которой m + n минимально.
Теперь следует найти хотя
бы один допустимый вариант дружбы.
1. Девочка – Девочка. В классе имеется m девочек, каждая девочка дружит с a другими.
·
Пусть a четно. Поставим в дружбу девочке с номером i девочек со всеми такими j, что i + 1 ≤ j
≤ i + 1 + (a / 2). Причем
если значение j становится большим m, то положим j = (j
– 1) % m + 1 (циклическая нумерация: i + 1, i + 2, …, m, 1, 2, …, (i + (a
/ 2)) % m + 1).
·
Пусть a нечетно. Тогда исходя из того, что m * a должно
быть четным, следует что m четно.
Построим граф как в случае четного a,
в результате чего получим что каждая девочка дружит с (a – 1) другой девочкой. Еще для каждой девочки не хватает по одной
для дружбы.
Поставим в дружбу девочке i (1
≤ i ≤ m / 2) девочку с номером i + m / 2.
2. Мальчик – Мальчик. Действуем аналогично девочкам, строя
симметричный граф.
3. Девочка – Мальчик. Пусть девочке с номером 1 поставили в соответствие
мальчиков из интервала [1; b]. Тогда
девочке с номером 2 поставим в соответствие мальчиков из интервала [b + 1; 2b]. Третьей девочке ставим мальчиков с номерами из интервала [2b + 1; 3b] и так далее. Номера мальчиков считаем циклически: 1, 2, …, n, 1, 2, …., n, 1, 2, … .
Реализация алгоритма
Читаем входные данные.
scanf("%d %d %d %d",
&a, &b, &c, &d);
Полным перебором ищем значения m
и n, минимизируя сумму m + n.
int ResM = 12345, ResN = 12345;
for (m = a + 1; m <= 52 * 52; m++)
for (n = d + 1; n <= 52 * 52; n++)
if (m * b == n * c)
if (((m * a) % 2 == 0) && ((n * d) % 2 == 0))
if ((m >= c) && (n >= b))
if (m + n < ResM + ResN)
{
ResM = m;
ResN = n;
}
int m = ResM, n = ResN;
Выводим количество девочек и мальчиков в классе.
printf("%d %d\n",
m, n);
Выводим отношения дружбы между девочками.
// Girl - Girl
for (i = 1; i <= m; i++)
for (j = i + 1; j <= i + (a / 2); j++)
printf("%d %d\n",
i, (j - 1) % m + 1);
if (a % 2 == 1)
for (i = 1; i <= m / 2; i++)
printf("%d %d\n", i, m / 2 + i);
Выводим отношения дружбы между мальчиками.
// Boy - Boy
for (i = 1; i <= n; i++)
for (j = i + 1; j <= i + (d / 2); j++)
printf("%d %d\n", m + i, m + (j - 1) % n + 1);
if (d % 2 == 1)
for (i = 1; i <= n / 2; i++)
printf("%d %d\n", m + i, m + n / 2 + i);
Выводим отношения дружбы между девочками и мальчиками.
// Girl - Boy
int BoyId = 0;
for (int
i = 1; i <= m; i++)
for (int j = 1; j
<= b; j++)
{
if (++BoyId > n) BoyId = 1;
printf("%d %d\n", i, m + BoyId);
}