시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1.5 초 512 MB 120 56 49 52.128%

문제

신형이네 학교 식당 앞에는 서로 다른 N개의 숫자가 적혀 있고, 세로 7칸, 가로 6 x N칸으로 이루어진 직사각형 모양의 전광판이 있다. 이 전광판의 각 칸에는 전구가 하나씩 들어 있으며, 세로 7칸, 가로 6칸 크기의 전구들을 이용해서 숫자를 표현한다. 아래 그림은 0부터 9까지의 숫자가 순서대로 적혀 있는 전광판의 모습이다. 검정색 칸은 켜져 있는 전구, 비어있는 칸은 꺼져있는 전구를 의미하며, 같은 숫자를 표현하는 다른 방법은 없다고 가정한다.

전광판에 적힌 숫자들을 앞에서부터 순서대로 읽었을 때 나오는 순열을 P라고 하자. 신형이는 문득 순열 P의 원소의 순서를 바꿔서 얻을 수 있는 순열 중 사전순으로 P 다음에 오는 순열이 어떤 것일지 궁금했고, 또 그 순열이 표현된 전광판은 어떤 모습일 지 알고 싶었다.

예를 들어, 위 그림에 적힌 숫자들을 순서대로 읽으면 {1, 4, 2}가 되고. 이 숫자들의 순서를 바꿔서 만들 수 있는 순열을 사전순으로 나열하면 아래와 같다.

{1, 2, 4}, {1, 4, 2}, {2, 1, 4}, {2, 4, 1}, {4, 1, 2}, {4, 2, 1}

이 중, 사전순으로 {1, 4, 2} 다음에 오는 순열은 {2, 1, 4}이므로 신형이가 궁금해하는 순열은 {2, 1, 4}가 된다. 그리고 이를 전광판으로 표현한 모습은 위와 같다. 학교 식당 앞 전광판의 모습이 주어졌을 때, 신형이가 궁금해하는 순열을 표현한 전광판의 모습을 출력하는 프로그램을 작성하시오.

입력

N(1 ≤ N ≤ 10)개의 숫자를 표현하고 있는 세로 7칸, 가로 6 x N칸 크기의 전광판의 모습이 7줄에 걸쳐 주어진다. 여기서 1은 켜져 있는 전구, 0은 꺼져 있는 전구를 의미한다.

출력

학교 식당 앞 전광판의 모습이 주어졌을 때, 전광판 숫자들의 순서를 바꿔서 만들 수 있는 순열 중 사전순으로 다음에 있는 순열을 전광판에 표현한 모습을 출력하라. 만약, 사전순으로 다음에 있는 순열이 없다면 "The End"를 출력하라.

예제 입력 1

000000000000000000
000100000100011110
001100001100000010
000100010100011110
000100111110010000
000100000100011110
000000000000000000

예제 출력 1

000000000000000000
011110000100000100
000010001100001100
011110000100010100
010000000100111110
011110000100000100
000000000000000000

예제 입력 2

000000
011100
000010
000100
000010
011100
000000

예제 출력 2

The End

출처

Contest > 네블컵 > 제2회 네블컵 L번