9920번 - Image 다국어

문제

This task concerns the output length of the quadtree image compression scheme. Only $L \times L$ images consisting of $L^2$ pixels are considered. An image pixel is either a 0ドル$-pixel or a 1ドル$-pixel.

The quadtree image compression scheme is as follows:

1. If the image consists of both 0ドル$-pixels and 1ドル$-pixels, encode a 1ドル$ to indicate that the image will be partitioned into 4ドル$ sub-images as described in Step (2). Otherwise, encode the entire image as 00ドル$ or 01ドル$ to indicate that the image consists of only 0ドル$-pixels or only 1ドル$-pixels respectively.

2. An image $I$ is partitioned into 4ドル$ equal size sub-images $A,ドル $B,ドル $C,ドル $D$ as shown:

   Step (1) is then performed on each of the four sub-images in the order of $A,ドル $B,ドル $C,ドル $D$.

Let $(I)$ be the encoding of the image $I$. The following examples show the encoding process to compress an image.

Example 1. This example shows the encoding process of a 4ドル \times 4$ image.

$$\begin{align*} \begin{bmatrix} 1&1&1&1\1円&1&0&1 \\ 0&1&0&0 \\ 0&0&1&1\end{bmatrix} & = 1 \begin{bmatrix}0&1\0円&0\end{bmatrix} \begin{bmatrix}1&1\1円&1\end{bmatrix} \begin{bmatrix}0&0\1円&1\end{bmatrix} \begin{bmatrix}1&1\0円&1\end{bmatrix} \\ & = 1 ,円 1\begin{bmatrix}0\end{bmatrix}\begin{bmatrix}0\end{bmatrix}\begin{bmatrix}0\end{bmatrix}\begin{bmatrix}1\end{bmatrix} ,円 01 ,円 1\begin{bmatrix}1\end{bmatrix}\begin{bmatrix}0\end{bmatrix}\begin{bmatrix}1\end{bmatrix}\begin{bmatrix}0\end{bmatrix} ,1円\begin{bmatrix}0\end{bmatrix}\begin{bmatrix}1\end{bmatrix}\begin{bmatrix}1\end{bmatrix}\begin{bmatrix}1\end{bmatrix} \\ & = 1,1円,00円,00円,00円,01円,01円,1円,01円,00円,01円,00円,1円,00円,01円,01円,01円\end{align*}$$

Since there are 30ドル$ bits (0ドル$’s and 1ドル$’s) in the encoding, the length of the compressed image is 30ドル$.

Example 2. This example shows the encoding process of an 8ドル \times 8$ image.

$$\begin{align*} \begin{bmatrix} 0&0&0&0&1&1&1&1\0円&0&0&0&1&1&1&1\0円&0&0&0&1&1&1&1\0円&0&0&0&1&1&1&1\1円&1&1&1&1&1&1&1\1円&1&1&1&1&1&1&1\1円&1&1&1&1&1&1&1\1円&1&1&1&1&1&1&1\end{bmatrix} & = 1 \begin{bmatrix}1&1&1&1\1円&1&1&1\1円&1&1&1\1円&1&1&1\end{bmatrix} \begin{bmatrix}0&0&0&0\0円&0&0&0\0円&0&0&0\0円&0&0&0\end{bmatrix} \begin{bmatrix}1&1&1&1\1円&1&1&1\1円&1&1&1\1円&1&1&1\end{bmatrix} \begin{bmatrix}1&1&1&1\1円&1&1&1\1円&1&1&1\1円&1&1&1\end{bmatrix} \\ & = 1,01円,00円,01円,01円\end{align*}$$

Thus the length of the compressed image is 9ドル$ (bits).

1. Read an $L \times L$ image (1ドル \le L \le 64$ and $L$ is a power of 2ドル$) from the input.
2. Compute the length (the number of bits) of the compressed image encoded by the quadtree compression scheme.
3. Write the length to the output.

입력

For an $L \times L$ square image, the input file contains $L + 1$ lines. The first line consists of the single integer $L$. Each line of the subsequent $L$ lines consists of $L$ bits (a bit is either a 0ドル$ or a 1ドル$) with a blank between two adjacent bits.

출력

The output file consists of one integer which is the length (the number of bits) in the compressed image.

제한

힌트