| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 148 | 83 | 68 | 56.198% |
Albert는 아래와 같은 3x3 격자판에서 하는 미니 빙고를 (mini BINGO) 즐겨한다. 이 문제를 풀기 위해 BINGO가 무슨 게임인지 알 필요는 없다.
Albert가 고안한 "미니 빙고" 놀이는 위와 같이 3x3 격자판에 서로 다른 영대문자 알파벳 9개를 적는 것으로 시작한다. 그리고 이 9개의 알파벳을 임의로 섞어서 길이 9인 문자열 $S$를 하나 고르는데 이를 seed (시드) 문자열이라 부른다.
시드 문자열 S에 등장하는 알파벳 순서대로 격자판의 칸을 색칠하는데, 아래 조건에 따라 해당 칸의 점수를 매긴다.
이 방법을 통해 얻은 각 칸의 점수는 언제나 0이상 4이하이며, 이를 시드문자열과 같은 순서대로 적어 길이가 9인 문자열을 얻을 수 있다 - 이렇게 얻은 점수 문자열을 $T(S)$라 하자.
예를 들어 시드 문자열 $S$ = "JGFACKIEB" 인 경우를 살펴보자. 아래 그림에서 상단 1열부터 5열까지, 그리고 하단 1열부터 4열까지의 격자판은 시드 문자열에 따라 알맞은 칸을 순서대로 칠한 모습을 보여준다.
J", "G", "F", "A", "C"이며 각각 0점씩 점수를 부여한다.K"를 칠한 후 주-대각선과 3열 때문에 2점의 점수를 부여한다.I"를 칠한 후 3행과 반-대각선 때문에 2점의 점수를 부여한다.E"를 칠한 후 1열과 2행 때문에 2점의 점수를 부여한다.B"를 칠한 후 1행과 2열 때문에 2점의 점수를 부여한다.000002222"가 된다.같은 격자판에서 시드 문자열이 $S$ = "ABEGKCFIJ" 일 때, 아래와 같은 순서로 격자를 칠하고, 이때의 점수 문자열은 "000002222"가 된다.
위 예제에서 보이듯 서로 다른 시드 문자열의 점수 문자열이 같을 수 있다.
Albert는 임의의 격자판과 임의의 시드 문자열 $S$가 있을 때 $T(S)$ 를 구하는 것이 너무 쉽다고 생각한다. 따라서 $S$의 점수 문자열을 구한 후, $S$와 같은 점수 문자열을 ($T(S)$) 만들어내는 모든 시드 문자열 중 사전순으로 가장 앞서는 시드 문자열을 찾고 싶다. Albert를 도와주자.
입력 첫 줄에 테스트 케이스의 수 $T$가 주어진다.
각 테스트 케이스의 첫 줄에는 길이 9인 시드 문자열 $S$가 주어진다. 다음 세 줄에 걸쳐 3x3 격자판의 상태가 주어지는데 각 줄에 3개의 문자가 공백 없이 주어진다.
각 테스트 케이스의 정답인 $T(S)$와 해당 점수 문자열을 얻게 하는 시드 문자열 중 사전순으로 가장 앞서는 문자열을 공백으로 구분하여 각 줄에 출력한다.
A'-'Z' 만을 포함한다. $S$에 중복된 알파벳은 입력으로 주어지지 않는다.4 JGFACKIEB ABC EFG IJK ADSFGHJKL ASD FGH JKL QPWOEIRUT QWE RTU IOP AZSXDCFVG ZFC DGX ASV
000002222 ABEGKCFIJ 001001213 ADSFGHJKL 000011114 EIOQPRUWT 000010124 ACDSVFXZG
예제 1: 본문에서 다루었다.
예제 2: 입력으로 주어진 시드 문자열이 사전순으로 가장 앞설 수도 있다.
예제 3-4: 추가 설명 없음.
문자열의 사전순 정의: 길이가 $K$인 서로 다른 두 문자열 $A$와 $B$가 있을 때, 이 두 문자열이 처음 달라지는 위치가 $i$번째라 하고 이 위치의 문자를 각각 $A[i],ドル $B[i]$라 했을 때, $A$와 $B$의 사전식 순서는 두 알파벳 $A[i],ドル $B[i]$의 사전식 순서를 따른다.