Для начала можно решить частный случай, а потом общую задачу.
Частный случай: Как заняться любовью с каждой из 3 (трех) женщин, имея только 2 (два) презерватива при условии, что никто нечем ни от кого заразиться не должен?
P.S. и еще одна для разминки, она очень, очень простая. Мама Игоря старше его на 21 год. А через шесть лет она станет его старше в пять раз. Вопрос: чем в данный момент занимается отец Игоря?
facepalm А любителям поломать голову вдогонку еще (не исключено, что баян): Дано: - Мужчина — 2шт. - Женщина — 2шт. - Презерватив — 2шт. - Кто-то из них болен триппером Найти: Способ заняться любовью каждому мужчине с каждой женщиной и чтоб никто не заразился :)
Решение в первой правке
Вопрос.
Ответ
Спасибо, ступил.
решение c предподсчетом за O(n): всем сходить к врачу и сдать анализы
решение с предподсчетом за О(1), требующее О(n-m) памяти: сходить и купить недостающие презервативы
Нагугленный и видимо подразумевающийся правильным ответ я рассматривал, но не нашел там строгого доказательства отсутствия путей между парами стоков, и поэтому не рискнул бы отправлять его на сис. тесты
У решения с предпосчетом константа большая, а в российских клиниках это решение упадет даже при n = 1.
Спойлер и дополнение по разминочной задаче.