Problems
Jaewoo is studying divide and conquer.
So he solved problem 1335: Making Colored Paper.
Wanting to study more, Jaewoo thought of the following problem.
Given a square with a side length that is a power of 2, if all numbers in the square are 0, it is represented as 0; if all numbers are 1, it is represented as 1.
Otherwise, if the square contains both 0 and 1, the area is represented by an uppercase X, and the area is divided into four equal parts, recursively applying the same rule.
The order of calling the four divided areas is top-left, top-right, bottom-left, and bottom-right.
For example, if the following information is given:
8
1 0 1 1 1 1 1 1
0 1 1 1 1 1 1 1
0 0 0 0 1 1 1 1
0 0 0 0 1 1 1 1
1 1 0 0 0 0 0 0
1 1 0 0 0 0 0 0
0 0 1 1 0 0 0 0
0 0 1 1 0 0 0 0
Following the rules above, the following result is produced.
XXX10011001X10010
Input
The length of one side, N, is entered in the first row.
(8 <= N <= 1024, N is a power of 2) Information is entered in the next single row.
Output
Outputs a string created according to the rules.
Example
8
1 0 1 1 1 1 1 1
0 1 1 1 1 1 1 1
0 0 0 0 1 1 1 1
0 0 0 0 1 1 1 1
1 1 0 0 0 0 0 0
1 1 0 0 0 0 0 0
0 0 1 1 0 0 0 0
0 0 1 1 0 0 0 0
XXX10011001X10010
You must sign in to write code.