Problems
As shown in <Figure 1> below, a square-shaped piece of paper consisting of several square cells is given,
and each square is colored either white or blue.
We want to cut the given paper according to a certain rule to create white or blue square-shaped colored papers of various sizes.
If the size of the entire paper is N×N (N=2k, where k is a natural number between 1 and 7 inclusive), the rules for cutting the paper are as follows.
If the entire paper is not colored in the same color, cut the middle part horizontally and vertically
to divide it into four N/2 × N/2 colored papers of the same size, as shown in I, II, III, and IV of <Figure 2>.
For each of the divided papers I, II, III, and IV, if they are not all colored in the same color as before,
divide them into four colored papers of the same size in the same way.
This process is repeated until the cut paper is all colored white or all blue,
or until it becomes a single square cell and can no longer be cut.
When cut according to the above rules, <Figure 3> shows the state after the first division of the paper in <Figure 1>,
<Figure 4> shows the state after the second division,
and <Figure 5> shows the 9 white colored papers and 7 blue colored papers of various sizes that were finally created.
Given the length N of one side of the paper and the color (white or blue) of each square cell as input,
write a program to find the number of cut white colored papers and blue colored papers.
Input
The first line of the input file contains the length N of one side of the entire paper. N is one of 2, 4, 8, 16, 32, 64, or 128.
The colors of the square cells in each row of the colored paper are given from the second line to the last line of the input file, starting from the top row.
Cells painted white are given as 0, cells painted blue are given as 1, and there is a single space between each number.
Output
Print the number of white colored papers in the first line and the number of blue colored papers in the second line.
Example
8
1 1 0 0 0 0 1 1
1 1 0 0 0 0 1 1
0 0 0 0 1 1 0 0
0 0 0 0 1 1 0 0
1 0 0 0 1 1 1 1
0 1 0 0 1 1 1 1
0 0 1 1 1 1 1 1
0 0 1 1 1 1 1 1
9
7
You must sign in to write code.