Комментарии 3
Спасибо за задачку. На листочке решал не так, как вам подсказали – она хорошо решается строка за строкой:
Первую клетку красим в произвольный цвет (назовём его A), вторую в один из оставшихся (B), третья – либо A, либо третий цвет (C). Итого всего два принципиально различающихся расклада (ABA и ABC), по 6 случаев каждого. Обозначим эти количества x1=6, y1=6
Под строкой ABA можно написать BAB, BAC, BCB, CAB, CAC – из них три варианта (BAB, BCB, CAC) принципиально не отличаются от ABA, два (BAC, CAB) не отличиются от ABC. Под строкой ABC выбор ещё меньше – две строки типа ABA, две типа ABC.
Посчитаем полное количество раскладов для двух строк:
x2 = x1*3+y1*2, y2 = x1*2+y1*2Третья строка аналогично второй, расклады смотреть не надо, сразу считаем:
x3 = x2*3+y2*2, y3 = x2*2+y2*2
Число у меня сошлось с ответом). Бонус – довольно легко обобщить на прямоугольник 3*N.
Так же решил. Первая мысль при подсчете разскрасок/замощений матрицы — динамическое программирование по профилю. Чуть порисовав ясно, что принципиально профилей 2 различных, как вы и сказали — ABC,ABA. А дальше получается динамическое программирование — сколько вариантов раскрасить матрицу k*3 с заданным профилем на конце.
APL прикольный. Как регэкспы с красивыми значками. "Но очень интересно."
Считаем комбинации мозаик при помощи APL