Кубики

Материал из Algocode wiki
Версия от 14:05, 19 марта 2020; Глеб (обсуждение | вклад) (Новая страница: «==Задача== Дано $n$ кубиков, у каждого из них 6 граней и на каждой гране написана какая-то бу...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Задача

Дано $n$ кубиков, у каждого из них 6 граней и на каждой гране написана какая-то буква, дано слово $s$, требуется каждой букве слова $s$ сопоставить уникальный кубик, так чтобы мы могли повернуть этот кубик и получить нужную нам букву.

Пример

Даны три кубика у одного на гранях написаны буквы (a, a, a, a, a, a), у другого - (а, а, а, а, а, б), у третьего (а, а, а, б, б, с) и дано слово acb, тогда ответ - ровно один : 132.

Решение

Сделаем двудольный граф, одна доля которого - номера кубиков, а другая - номер буквы в слове $s$, проведем ребра из номера кубика в номер буквы только если мы можем взять этот кубик на эту позицию в строке. Теперь ответ - просто паросочетание.

Доказательство

По определению паросочетания мы не сопоставим один кубик нескольким буквам, но так как наше паросочетание - максимально, то мы покроем максимально количество букв.



Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin