35296번 - 아침 점호 서브태스크스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 316 | 172 | 166 | 58.042% |
문제
KSA 아침 점호는 급식실에서 출석 체크 형식으로 진행된다. KSA에는 총 $N \cdot M$명의 학생이 있고, 각 학생에게는 $1$번부터 $N \cdot M$번까지의 번호가 부여되어 있다. 출석부에는 $N$행 $M$열로 학생들의 번호가 적혀 있고, 각 학생은 자신의 번호를 찾아서 그 위에 동그라미를 그리면 아침 점호에 참여한 것으로 간주된다. $i$행 $j$열에는 $i+N(j-1)$가 적혀 있으며, 각 번호에는 동그라미를 한 번만 그릴 수 있다.
하지만 아침 점호에 참여하기 게으른 일부 학생들이 친구에게 점호를 대신 맡기기 시작했다. 점호를 대신 맡은 학생은 사감 선생님께서 지켜보고 계시지 않는 틈을 타서 재빠르게 자신과 점호를 맡긴 학생, 총 두 명의 번호 위에 동그라미를 그린다. 단, 사감 선생님께 걸리지 않기 위해 번호의 차가 $1$이면서 출석부 칸의 한 변이 인접한 학생에게만 점호를 대신 맡길 수 있다.
현재까지 학생들의 점호 참여 상황이 주어질 때, 모든 학생의 점호 참여를 완료하기 위해 필요한 추가 인원의 최솟값과 그 방법을 구해보자.
입력
첫 번째 줄에 두 개의 정수 $N$, $M$이 공백으로 구분되어 주어진다.
다음 $N$개의 줄 중 $i$번째 줄에 문자열 $S_i$가 주어진다. $S_i$는 O와 X로 구성된 길이 $M$의 문자열이고, $j$번째 문자가 O이면 $i+N(j-1)$번 학생이 점호를 이미 완료한 상태고, X이면 $i+N(j-1)$번 학생이 점호를 아직 완료하지 않은 상태라는 뜻이다.
출력
첫 번째 줄에 모든 학생의 점호 참여가 완료되기 위해 급식실에 와야 하는 학생 수의 최솟값 $k$를 출력한다.
다음 $k$개의 줄에 걸쳐 각 줄에 다음을 출력한다. 만약 자신의 점호만 완료하는 학생이라면 $1$과 그 학생의 번호를 공백으로 구분하여 출력하고, 만약 점호를 대신 맡은 친구라면 $2$와 두 학생의 번호를 공백으로 구분하여 출력한다.
이때 학생의 번호를 출력하는 순서와 $k$개의 줄의 순서는 중요하지 않다. 정답이 여러 개 존재한다면 그중 아무거나 출력해도 상관없다.
제한
- $1 \le N, M \le 100$
- 적어도 하나의 $S_i$는
X를 포함
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 20 | $M = 1$ |
| 2 | 80 | 추가 제약 조건 없음 |
예제 입력 1
3 2 XO XX XO
예제 출력 1
3 1 3 2 1 2 1 5
예제 입력 2
5 1 O X X X O
예제 출력 2
2 1 2 2 4 3
예제 입력 3
1 4 XXXX
예제 출력 3
2 2 2 1 2 3 4
출처
School > 한국과학영재학교 > 2026 KSA Automata Winter Contest B번
- 문제를 만든 사람: eric00513
- 문제를 검수한 사람: bennyk0406, dinojaemin, flakepowders, parkky, pkearth, raehwan0418, sadtreap, utilforever, wizardrabbit
채점 및 기타 정보
- 예제는 채점하지 않는다.
- 이 문제의 채점 우선 순위는 2이다.