nikolay-8981

Для решения задачи можно использовать метод динамического программирования. Пусть 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. Котиков три