Задачи с доминошками на собеседованиях

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

Пример 1

Имеется шахматная доска 8 на 8 клеток, левый нижний и правый верхний углы которой отрезаны.
image
Можно ли полностью покрыть такую доску доминошками размера 2×1 клетку?

На доске остается четное число клеток (62), так что на первый взгляд решение возможно. Однако, давайте сделаем одну очень простую вещь:
image
Мы раскрасили клетки через одну. Теперь все становится очевидным. Каждая доминошка может занимать строго две клетки: одну белую и одну черную. Других вариантов не дано. Смотрим, какие клетки на доске отрезаны – обе черные, соответственно мы имеем 32 белых и 30 черных клеткок и полностью покрыть такую доску не представляется возможным.

Условия задачи могут варьироваться, но в целом, задачи на возможность-невозможность сразу бросаются в глаза.

Пример 2

Имеется большой куб сыра 3x3x3 состоящий из 27 одинаковых кубиков сыра и мышонок, который съедая один кубик принимается за соседний с ним по грани кубик сыра. Сможет ли мышонок полностью съесть весь сыр, если центральный кубик заменить на несъедобный муляж?

Задача та же самая, только в пространстве, а не на плоскости. Считаем клеточки: в изначальном раскладе это 14 на 13, после удаления центрального кубика: 14 на 12 и как следствие, решения нет.

Следующими по популярности идут задачи на подсчет количества вариантов решений.

Пример 3

Даны две доски:
imageimage

На каждой вырезано по 2 клетке. Количество вариантов покрытия доминошками какой из досок больше? В обоих случаях вырезаны клетки разного цвета, так что все познания с раскраской из предыдущих примеров нам здесь не помогут. Времени на собеседованиях на задачи отводится мало, так что нужно искать какую-то зацепку. А она есть. Исключим из первого варианта все покрытия содержащие вырезанные клетки второй доски, а из второго варианта – первой. (Если так проще представить – то можно считать, что вырезанные клетки изначально покрыты доминошкой – которую нельзя двигать, и, очевидно, что таким образом мы приводим доски к идентичному состоянию и количество вариантов покрытий будет тоже идентичным). После этого рассмотрим нижний угол 3 на 2 клетки. Во втором варианте, левая нижняя клетка может быть покрыта только одним способом. Сопоставим этому покрытию вариант для первой доски:
imageimage

Оставшася часть за исключением этого угла идентична, соответственно и количество покрытий тоже идентично. Таким образом, каждому варианту покрытия второй доски, сопоставлен вариант покрытия первой доски. Однако в первом случае также еще возможен вариант, где все доминошки расположены вертикально, не соответветсвующий ни одному варианту второй доски. Следовательно, число вариантов покрытия доски с клетками, отрезанными в углу больше.

Пример 4

Найти количество вариантов покрытия доминошками доски 2хN клеток.

Пусть ее можно покрыть X(N) способов. Рассмотрим вариант покрытия левой верхней клетки:
image
Оставшуюся часть в первом случае можно покрыть X(N-1) способами, а во втором, очевидно, X(N-2).
Так как перечислены все варианты покрытия и никакие из них не будут совпадать, то получаем уравнение X(N) = X(N-1) + X(N-2)
X(1) = 1, X(2) = 2, а Х(N) будет равно N+1 числу последовательности Фибоначчи.

Пример 5

Написать программу, вычисляющую количество способов покрытия доски 3xN клеток доминошками.

Сразу скажу, возможно, для этого примера есть тоже оптимальное решение, но я перейду тут уже от частных решений к общему. По сути, все что стоит за такими задачами можно представить двудольным графом, одно из множеств вершин которого – черные клетки, а другое – белые. Покрытие доминошками – есть не что иное как максимальное паросочетание такого графа. Для его поиска могут применяться различные алгоритмы (например Куна), с подсчетом количества вариантов все несколько сложнее. В любом случае, это за пределами данной статьи.

В заключение, для демонстрации, реализация алгоритма “в лоб” на питоне:

from itertools import combinations
# формирование матрици инцидентности опущено для краткости
# оно тривиально
# Например, для доски 2x2 с номерами клеток:
# 1 2
# 3 4
# это:
# mat = [
# [0, 1, 1, 0],
# [0, 0, 0, 1],
# [0, 0, 0, 1],
# [0, 0, 0, 0]
#]
# 1 => 2, 1 => 3, 2 => 4, 3 => 4
# Обратные направления ( напр. 3 => 1 )
# не представляют для нас интереса
N = len(mat)
# создаем итератор со всеми парами вершин
all_edges = combinations(xrange(N), 2)
# фильтруем по матрице инцидентности
edges = [(x,y) for x,y in all_edges if mat[x][y]]
# отфильтровываем все максимальные варианты
matchings = [tuples for tuples in combinations(edges, N/2) \
if len(set(reduce(lambda x, y: x+y, tuples))) == N]
print len(matchings)
# осторожно, сложность O(N!)
Поделиться публикацией
Ой, у вас баннер убежал!

Ну. И что?
Реклама
Комментарии 4
  • 0
    Доминошки в первой задаче должны располагаться в какой-то обязательной последовательности относительно друг друга, или это просто юнит 2х1?
  • 0
    Задача из примера 5 решается динамикой по профилю, если кому-то еще актуально:
    void solve( )
    {   
        int N = 0;
        while (true) {
            cin >> N;
            if (N == -1) return;
            ll a[32][8];
            for (int i = 0; i < 8; ++i) a[0][i] = 0;
            a[0][0b00000111] = 1;
            for (int i = 1; i <= N+1; ++i) {
                a[i][0b00000001] = a[i-1][0b00000110];
                a[i][0b00000011] = a[i-1][0b00000100] + a[i-1][0b00000111];
                a[i][0b00000100] = a[i-1][0b00000011];
                a[i][0b00000110] = a[i-1][0b00000001] + a[i-1][0b00000111];
                a[i][0b00000111] = a[i-1][0b00000011] + a[i-1][0b00000110];
                if (i >= 2)
                    a[i][7] += a[i-2][7];
            }
            if (N%2==0)
                cout << a[N][7] << endl;
            else
                cout << 0 << endl;
        }
    }
    

    Аналогично решается задача «замостить доминошками поле N*M», только там все допустимые переходы нужно уже генерировать, а не просчитывать вручную как сделал я. Описание есть здесь
    • 0
      Когда на собеседовании начинают задавать задачи на логику, теорию вероятности и прочее, особенно когда не дают время спокойно подумать, хочется встать и уйти. Глупости это, не имеющие никакого отношения к уровню профессионализма разработчика.
      Как сказал один мой товарищ, умение решать ребусы говорит только о том, что человек умеет решать ребусы.

      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

      Самое читаемое