Условие:
На вечеринку пришло 10 парней и 10 девушек. Известно, что каждому парню нравится разное целое положительное количество девушек, а также что каждой девушке нравится разное целое положительное количество парней. При каком наибольшем
Решение:
Рассмотрим следующую задачу. На каждом «парне» задано число – число девушек, которые ему нравятся, и эти числа различны, поэтому они равны 1, 2, …, 10 (в некотором порядке). Аналогично, у девушек числа – число парней, которые им нравятся, и они тоже – 1, 2, …, 10. Таким образом, если представить вечеринку в виде двудольного графа, то одна доля (парни) имеет степени 1, 2, …, 10, а другая (девушки) – степени 1, 2, …, 10 (но порядок назначений может быть любым). При этом суммарное число «симпатий» у парней равно 55, и у девушек тоже 55, так что условие возможности существования такого графа (в...
Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит
Попробуй решить по шагам
Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение
Что нужно знать по теме:
Что нужно знать по теме
Алгоритм решения
Топ 3 ошибок
Что спросит препод
Похожие задачи