페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#3249

색종이 만들기3(압축해제) 1초 128MB

문제

도훈이는 분할정복을 공부중이다.

그래서 1335:색종이 만들기 문제를 풀었다.

좀 더 공부하고 싶은 도훈이는​ 다음과 같은 문제를 생각해 보았다.

 

한 변의 길이가 2의 제곱수인 정사각형에 주어질 때, 주어진 정사각형에 포함된 숫자가 모두 0이면 0, 주어진 정사각형에 포함된 숫자가 모두 1이면 1 로 나타낸다.

그렇지 않고 주어진 정사각형에 포함된 숫자가 0, 1이 함께 있다면 대문자 X로 그 영역을 나타내고 해당 영역을 4등분하여 재귀적으로 호출하여 같은 규칙을 적용한다.

4등분한 영역의 호출 순서는 좌상, 우상, 좌하, 우하 이다.

 

예를 들면 아래와 같은 정보가 주어지면

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​

 

위의 규칙을 따르면 다음과 같은 결과가 만들어진다.

8

XXX10011001X10010​ 

 

그런데 여기서 우리가 할 일은 

8

XXX10011001X10010​​ 

가 주어질때 원래의 정사각형을 복원하는 것이다.

 

도훈이와 함께 문제를 풀어보자.

 


입력

첫 행에 한 변의 길이 N이 입력된다. (8 <= N <= 1024) 다음 하나의 행에 정보가 입력된다.

정보의 길이는 2,000,000자를 넘지 않는다.


출력

첫 줄에 한 변이 길이 N을 출력한다. 둘째줄 부터 복원된 색종이를 출력한다.


예제1

입력
8

XXX10011001X10010
출력
8

10111111
01111111
00001111
00001111
11000000
11000000
00110000
00110000

출처

KOI 전국 2001 중1 | comkiwer

역링크