Решение задачи Шахматная доска с Codeforces
С пояснением   Просмотров: 90
Однажды Магнус решил разыграть одну классическую шахматную партию. Но открыв чулан, Магнус пришел в ужас! Его любимая доска была разломлена на 4 части, каждая размера n на n, причем n обязательно нечетно. Хуже того, некоторые клетки имели неправильный цвет. j-я клетка i-й строки k-й части доски имеет цвет a k, i, j; 1 соответствует черному цвету, а 0 — белому.
Магнусу стало интересно, какое минимальное количество клеток нужно перекрасить, чтобы из частей доски можно было составить правильную доску. В правильной доске любая пара соседних по стороне клеток должна иметь различный цвет, и размер правильной доски должен быть 2n на 2n. Части доски разрешено переставлять, но нельзя поворачивать или переворачивать.
Магнусу стало интересно, какое минимальное количество клеток нужно перекрасить, чтобы из частей доски можно было составить правильную доску. В правильной доске любая пара соседних по стороне клеток должна иметь различный цвет, и размер правильной доски должен быть 2n на 2n. Части доски разрешено переставлять, но нельзя поворачивать или переворачивать.
Пояснение к задаче
Заметим, что при данных ограничениях 2 части доски будут иметь левый верхний угол белого цвета, а другие 2 — черного. Переберем, у каких частей доски левый верхний угол будет белым, соответственно, у оставшихся частей он будет черным. Все, что осталось — посчитать количество клеток, которые покрашены не в свой цвет, и вывести минимум по всем возможным перестановкам частей доски.