### COCI 2008/2009, Contest #4

## Task SLIKAR

Josip is a strange painter. He wants to paint a picture consisting of NxN pixels, where N is a power of two (1, 2, 4, 8, 16 etc.). Each pixel will be either black or white. Josip already has an idea of how each pixel will be coloured.This would be no problem if Josip's painting process wasn't strange. He uses the following recursive process:

- If the picture is a single pixel, he colours it the way he intended.
- Otherwise, split the square into four smaller squares and
then:
- Select one of the four squares and colour it white.
- Select one of the three remaining squares and colour it black.
- Consider the two remaining squares as new paintings and use the same three-step process on them.

### Input

The first line contains an integer N (1 ≤ N ≤ 512), the size of the picture Josip would like to paint. N will be a power of 2.Each of the following N lines contains N digits 0 or 1, white and black squares in the target picture.

### Output

On the first line, output the smallest possible difference that can be achieved.On the next N lines, output a picture that can be painted with Josip's process and achieves the smallest difference. The picture should be in the same format as in the input.

Note: The second part of the output (the picture) may not be unique. Any correct output will be accepted.

### Scoring

In test cases worth 50% points, N will be at most 8.### Examples

## Input4 ## Output1 |
## Input4 ## Output6 |
## Input8 ## Output16 |

All Submissions

Best Solutions

**Point Value:** 20 (partial)

**Time Limit:** 2.00s

**Memory Limit:** 16M

**Added:** Jan 19, 2009

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

javicon Apr 16, 2009 - 7:13:16 am UTC lolSourSpinachon Apr 17, 2009 - 3:03:24 am UTC Re: lolint supersmashbrosbrawl[515][515];

javicon Apr 17, 2009 - 3:15:48 am UTC Re: Re: lola while ago I tried to make a struct with the name Mod_2147483647_Integer_I_Have_To_Do_This_Because_Of_the_Evil_Hanson_XD

but later I was annoyed at the mess it created when debugging, so I changed it back to EvilInteger haha

bbi5291on Apr 18, 2009 - 12:47:19 am UTC Re: Re: Re: lol