Кубики
Содержание
Задача
Дано $n$ кубиков, у каждого из них 6 граней и на каждой гране написана какая-то буква, дано слово $s$, требуется каждой букве слова $s$ сопоставить уникальный кубик, так чтобы мы могли повернуть этот кубик и получить нужную нам букву.
Пример
Даны три кубика у одного на гранях написаны буквы (a, a, a, a, a, a), у другого - (а, а, а, а, а, б), у третьего (а, а, а, б, б, с) и дано слово acb, тогда ответ - ровно один : 132.
Решение
Сделаем двудольный граф, одна доля которого - номера кубиков, а другая - номер буквы в слове $s$, проведем ребра из номера кубика в номер буквы только если мы можем взять этот кубик на эту позицию в строке. Теперь ответ - просто паросочетание.
Доказательство
По определению паросочетания мы не сопоставим один кубик нескольким буквам, но так как наше паросочетание - максимально, то мы покроем максимально количество букв.
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin