题目描述
Problem Background
Josip is a peculiar painter.
Problem Description
He wants to paint a picture composed of $n \times n$ pixels, where $n$ is a power of 2 (e.g., $1, 2, 4, 8, 16, \ldots$). Each pixel will be colored either black or white. Josip already knows his ideal painting.
He will paint according to the following steps:
- If the entire painting is a single pixel, he will color it black or white according to his goal.
- Otherwise, he will divide the square into four smaller squares and then:
1. Choose one square to paint entirely white.
2. Choose another from the remaining three squares to paint entirely black.
3. Treat the remaining two squares as a new painting and repeat the above steps.
He quickly realizes that it is impossible to paint the exact picture he has in mind. Therefore, he hopes you can write a program that will produce a painting with the smallest possible difference from his ideal painting.
The difference between two paintings is the number of pixels with different colors.
Input Format
The first line of input is an integer $n$, representing the side length of the painting.
The next $n$ lines, each containing $n$ digits (either 0 or 1), represent the ideal painting where 0 indicates a white pixel and 1 indicates a black pixel.
Output Format
The first line of output is an integer representing the minimum difference value.
The next $n$ lines, each containing $n$ digits (either 0 or 1), represent the actual colors of the pixels in the painting.
Note: There may be multiple valid coloring schemes; output any one of them. This problem uses a special judge (SPJ).
Sample Input and Output
Sample Input #1
4
0001
0001
0011
1110
Sample Output #1
1
0001
0001
0011
1111
Sample Input #2
4
1111
1111
1111
1111
Sample Output #2
6
0011
0011
0111
1101
Sample Input #3
8
01010001
10100011
01010111
10101111
01010111
10100011
01010001
10100000
Sample Output #3
16
00000001
00000011
00000111
00001111
11110111
11110011
11110001
11110000
Notes
Data Size and Constraints
- For $50\%$ of the test cases, $n \leq 8$.
- For $100\%$ of the test cases, $1 \leq n \leq 512$.
Translation Note
This problem is translated from COCI2008-2009 CONTEST #4 T4 SLIKAR.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分