Slikar

Josip은 특이한 화가이다. 그는 \(N \times N\)개의 픽셀로 이루어진 그림을 그리려고 하는데, 여기서 \(N\)은 2의 거듭제곱(\(1, 2, 4, 8, 16\) 등)이다. 각 픽셀은 검은색 또는 흰색이다. Josip은 각 픽셀을 어떤 색으로 칠할지 이미 구상해 두었다.

Josip의 그림 그리는 과정이 특이하지 않았다면 아무 문제도 없었을 것이다. 그는 다음과 같은 재귀적 과정을 사용한다:

• 그림이 픽셀 하나라면, 구상한 대로 그 픽셀을 칠한다.
• 그렇지 않다면, 정사각형을 네 개의 더 작은 정사각형으로 나눈 뒤:
  1. 네 정사각형 중 하나를 골라 흰색으로 칠한다.
  2. 남은 세 정사각형 중 하나를 골라 검은색으로 칠한다.
  3. 남은 두 정사각형을 새로운 그림으로 보고 같은 세 단계 과정을 적용한다.

곧 그는 이 과정으로는 자신이 구상한 모든 그림을 그릴 수 없다는 것을 깨달았다. 여러분의 과제는 원하는 그림과의 차이가 최대한 작은 그림을 그리는 프로그램을 작성하는 것이다. 두 그림의 차이는 같은 위치에 있으면서 색이 다른 픽셀 쌍의 개수이다.

첫째 줄에 Josip이 그리려는 그림의 크기인 정수 \(N\) (\(1 \le N \le 512\))이 주어진다. \(N\)은 \(2\)의 거듭제곱이다.

다음 \(N\)개의 줄에는 각각 \(N\)개의 숫자 \(0\) 또는 \(1\)이 주어진다. 이는 목표 그림의 흰색과 검은색 칸을 나타낸다.

첫째 줄에 얻을 수 있는 가장 작은 차이를 출력한다.

다음 \(N\)개의 줄에 Josip의 과정으로 그릴 수 있으면서 가장 작은 차이를 얻는 그림을 출력한다. 그림은 입력과 같은 형식이어야 한다.

참고: 출력의 둘째 부분(그림)은 유일하지 않을 수 있다. 올바른 출력이면 무엇이든 정답으로 인정된다.

채점: 전체 점수의 \(50\%\)에 해당하는 테스트 케이스에서는 \(N\)이 최대 \(8\)이다.

riseoj 작성

출처 COCI 2008/2009 Contest 4