Частичные решения (0-100 баллов): Можно заметить, что случаев, когда в армии могут находится не только солдаты из Глиняного патруля всего 15. Некоторые из них довольно легко рассмотреть на листочке. Например, для x = 0 и y = 2 для k > 1 и наименьший, и наибольший ответ будут равны двум, а расстановка будет выглядеть примерно так:

000... 001

100... 000

Более того, разбором случаев можно набрать до 100 баллов включительно.

Полное решение (100 баллов): Будем решать задачу динамическим программированием по профилю.

dp[i][mask_prev][mask_cur] — минимальное/максимальное количество солдат из Зедд патруля, которые могут быть в расстановке из первых i столбцов, mask_cur — маска i-го столбца, а mask_prev — (i - 1)-го.

Затем переберем маску для (i + 1)-го столбца и проверим выполняются ли ограничения на соседей, для солдат из i-го столбца, так как теперь известны все их соседи.

Для первого и последнего столбца ограничения нужно проверять отдельно, потому что у них нет одного из соседей.

База: dp[2][mask_prev][mask_cur] равно количеству единиц в mask_prev и mask_cur, если mask_prev может стоять слева от mask_cur.

Переход: dp[i + 1][mask_cur][mask_next] = dp[i][mask_prev][mask_cur] + ones(mask_next), где ones(x) — количество единиц в маске x.

Ответ будет минимумом/максимумом среди всех dp[k][mask_prev][mask_cur], таких что mask_cur может находится справа от mask_prev.

Так как размерность маски константа и равна двум, данное решение будет работать за O(n).