35298번 - 책 정렬하기 서브태스크스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 222 | 78 | 71 | 43.293% |
문제
KSA 도서관에는 총 $N$권의 책이 일렬로 꽂혀 있다. 각 책의 높이는 왼쪽에서부터 길이가 $N$인 순열 $A = (A_1, A_2, \cdots, A_N)$을 이룬다. 즉, $A$는 $1$ 이상 $N$ 이하의 정수들이 정확히 한 번씩 등장하는 수열이다.
도서부원인 한범이는 아래 시행을 $0$회 이상 반복하여 책들을 높이가 오름차순이 되게끔 정렬하려고 한다.
- 연속한 책 2권을 선택한 뒤, 2권의 순서를 유지한 채로 맨 앞으로 이동시킨다.
$N^2$번 이하의 시행으로 정렬을 완료하기 위한 시행 순서를 찾아보자.
입력
첫 번째 줄에 정수 $N$이 주어진다.
두 번째 줄에 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다.
출력
첫 번째 줄에 $N^2$번 이하의 시행으로 책을 오름차순으로 정렬할 수 있는 방법이 존재한다면 YES를, 아니라면 NO를 출력한다.
만약 그러한 방법이 존재한다면, 필요한 시행 횟수를 $k$회라고 하자. 두 번째 줄에 정수 $k$를 출력한다. $0 \leq k \leq N^2$이어야 하지만, $k$를 최소화할 필요는 없음에 유의하라.
$k > 0$이라면 세 번째 줄에 $k$개의 정수 $x_1, x_2, \cdots, x_k$를 공백으로 구분하여 출력한다. $x_i$는 $i$번째 시행에서 왼쪽에서부터 $x_i$번째 책과 $x_i + 1$번째 책을 선택하여 맨 앞으로 이동시키는 것을 의미한다.
정답이 여러 개 존재한다면 그중 아무거나 출력해도 상관없다.
제한
- $2 \leq N \leq 100$
- $1 \leq A_i \leq N$
- $i \ne j$이면 $A_i \ne A_j$
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 5 | $N\leq 3$ |
| 2 | 30 | 책을 오름차순으로 정렬할 수 있는 방법이 존재 |
| 3 | 65 | 추가 제약 조건 없음 |
예제 입력 1
5 1 2 4 5 3
예제 출력 1
YES 4 4 3 4 3
예제 입력 2
3 3 2 1
예제 출력 2
NO
출처
School > 한국과학영재학교 > 2026 KSA Automata Winter Contest D번
- 문제를 만든 사람: sooahn07
- 문제를 검수한 사람: edward3378, eric00513, flakepowders, leejseo, mythofys, parkky, pkearth, raehwan0418, sadtreap, wizardrabbit
채점 및 기타 정보
- 예제는 채점하지 않는다.
- 이 문제의 채점 우선 순위는 2이다.