Перед уроком по алгоритмам студенты рисуют на доске котиков. Условно доска - поле размером 2 на 3 из равных квадратов. Преподаватель не стирает котиков, но место для рассказываемого материала оставить надо. Поэтому студенты рисуют от 1 до 3 котиков, каждый из которых занимает целое число клеток: хотя бы одну, но не более двух, смежных по стороне. Причем в общем все котики не занимают более трех клеток. Различные котики могут находиться в смежных (и по стороне, и по углу) клетках. Сколькими способами студенты могут нарисовать котиков, где различными способами считаются те, в которых двух одинаковых по размеру котиков меняют местами?

Для решения задачи можно использовать метод динамического программирования. Пусть dp[i][j] - количество способов нарисовать котиков на поддоске размером i на j. Тогда dp[2][3] будет ответом на задачу.

Заметим, что котики могут занимать только 1 или 2 клетки. Рассмотрим все возможные варианты расположения котиков на поддоске и заполним массив dp соответствующими значениями:

1. Котик занимает 1 клетку:
- один котик: dp[2][3] = 6
- два котика: dp[2][3] = 0 (невозможно)

2. Котик занимает 2 клетки:
- один котик: dp[2][3] = 0 (невозможно)
- два котика:
- вертикально: dp[2][3] = dp[1][3] * dp[1][3] = 4
- горизонтально: dp[2][3] = dp[2][1] * dp[2][2] + dp[2][2] * dp[2][1] = 10

3. Котиков три:
- все котики занимают по одной клетке: dp[2][3] = 6
- два котика занимают по одной клетке, один - две клетки:
- один котик занимает две клетки по вертикали: dp[2][3] = dp[1][3] * 2 = 4
- один котик занимает две клетки по горизонтали: dp[2][3] = dp[2][1] * 2 = 4
- один котик занимает две клетки, два - по одной: dp[2][3] = 0 (невозможно)

Таким образом, dp[2][3] = 6 + 10 + 4 + 4 = 24. Ответ на задачу - 24.