출동! 특수 작전 부대

시간 제한3초메모리 제한512 MB

요약
9x9 격자에 9가지 직책 코드가 주어질 때, 열, 행, 3x3 블록 각각의 묶음이 9가지 직책을 모두 포함하는지 확인한다.
난이도

보통10점 중 4점

유형
구현, 행렬, 시뮬레이션, 해시맵
정답자
아직 제출이 없습니다

문제

당신은 훈련된 대원 81명으로 이루어진 특수 작전 부대를 지휘한다. 부대는 9×99 \times 9 대형으로 적을 향해 전진한다. 공격할 때 부대는 9명씩 9개 중대로 나뉘고, 한 중대의 대원 9명은 서로 다른 보직 9개를 맡아야 한다. 보직은 다음과 같다.

  • 장교 (O)
  • 준위 (WO)
  • 화기 부사관 (WS)
  • 공병 부사관 (ES)
  • 의무 부사관 (MS)
  • 통신 부사관 (CS)
  • 정보 부사관 (IS)
  • 작전 부사관 (OS)
  • 선임 부사관 (SS)

공격 전략은 침투, 측면 기동, 전개 3가지다.

침투에서는 맨 앞의 대원이 선두에 선다. 대형의 각 열이 한 줄로 전진해 한 중대가 되므로 9개 열이 9개 중대가 되고, 적진 후방에 거점 9곳을 세운다.

측면 기동에서는 대형의 각 행이 좌우로 번갈아 빠져나가 측면에서 공격한다. 9개 행이 9개 중대가 된다. 왼쪽 측면은 항상 4개 중대, 오른쪽 측면은 항상 5개 중대다.

전개에서는 대형이 3×33 \times 3 구역 9개로 쪼개진다. 가운데 구역이 지휘소가 되고 나머지 구역 8개가 위성 거점이 되므로 9개 구역이 9개 중대가 된다.

그림 1: 침투그림 2: 측면 기동그림 3: 전개

어떤 전략은 그 전략이 만드는 중대 9개가 모두 보직 9개를 빠짐없이 갖출 때만 쓸 수 있다. 대형이 주어지면 전략 3가지를 모두 쓸 수 있는지 판정하라.

입력

첫째 줄에 부대의 수 GG가 주어진다.

각 부대는 9줄로 주어진다. 각 줄에는 보직 코드 9개가 공백 하나로 구분되어 있다.

제한

  • 1≤G≤3501 \le G \le 350
  • 입력에 나오는 코드는 모두 위 보직 코드 9개 중 하나다.

출력

부대마다 한 줄씩 출력한다. 공격 전략 3가지를 모두 쓸 수 있으면 all 3을, 그렇지 않으면 not을 출력한다.

예제2

  1. 예제 1

    입력
    2
OS MS IS O WS CS SS ES WO
SS WO CS OS ES MS O IS WS
O ES WS SS IS WO MS OS CS
IS O WO MS CS ES OS WS SS
CS WS OS IS WO SS ES O MS
MS SS ES WS OS O WO CS IS
ES IS SS WO O WS CS MS OS
WS CS MS ES SS OS IS WO O
WO OS O CS MS IS WS SS ES
CS OS ES MS IS O WS WO SS
MS SS WS WO ES OS CS IS O
IS O WO SS WS MS OS ES MS
O WO OS WS CS IS MS SS ES
ES CS SS O OS MS IS WS WO
WS MS IS ES SS WO O OS CS
SS IS O CS WO WS ES MS OS
WO WS MS OS O ES SS CS IS
OS ES CS IS MS SS WO O WS
    예상 출력
    all 3
not

  2. 예제 2

    입력
    1
O WO WS ES MS CS IS OS SS
ES MS CS IS OS SS O WO WS
IS OS SS O WO WS ES MS CS
WO WS ES MS CS IS OS SS O
MS CS IS OS SS O WO WS ES
OS SS O WO WS ES MS CS IS
WS ES MS CS IS OS SS O WO
CS IS OS SS O WO WS ES MS
SS O WO WS ES MS CS IS OS
    예상 출력
    all 3