10073번 - 곤돌라 - 교체 수열 서브태스크스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 256 MB | 134 | 55 | 54 | 45.000% |
문제
마오공 곤돌라는 타이페이의 명소 중 하나이다. 곤돌라 시스템은 원형의 레일과, 하나의 정류장이 있고, 1 부터 n까지 순서대로 번호가 붙은 n개의 곤돌라가 모두 단일한 방향으로 레일을 따라 움직이는 형태이다. i번 곤돌라가 정류장을 지난 직후에는 i+1번 곤돌라가 정류장을 지나가게 된다. (단, i=n번 곤돌라가 지나간 직후에 1 번 곤돌라가 지나가게 된다.)
곤돌라들은 고장이 나기도 한다. 다행히 무제한으로 많은 곤돌라의 여분이 있고, 여분 곤돌라들은 n+1, n+2과 같이 순차적으로 번호가 붙어 있다. 특정한 곤돌라가 고장이 나면 고장난 곤돌라는 빼고, 동일한 위치에 여분 곤돌라를 배치한다. 여분 곤돌라는 작은 번호부터 사용된다. 예를 들어, 사용하는 곤돌라 수가 총 5 개이고, 1 번 곤돌라가 고장난다면, 그 곤돌라는 6번으로 교체된다.
당신은 정류장에 서서 곤돌라들이 지나가는 것을 즐겨 본다. 곤돌라 수열이라는 것은 임의의 시점에서 시작해서 정류장을 지나가는 n개의 곤돌라들의 번호를 순서대로 적은 것이다. 곤돌라 수열을 적기 시작하는 시점 이전에 이미 몇개의 곤돌라가 고장나서 교체되었을 수 있다. 하지만, 곤돌라 수열을 적는 도중에는 아무 곤돌라도 고장이 나지 않는다.
전체적으로 곤돌라들의 배치가 동일하더라도 어떤 시점에 곤돌라 수열을 적기 시작하느냐에 따라 서로 다른 곤돌라 수열이 나올수 있다는 점에 주의하자. 예를 들어, 총 5개의 곤돌라들 중 고장난 곤돌라가 없는 경우에 (2, 3, 4, 5, 1) 과 (4, 5, 1, 2, 3) 은 모두 가능한 곤돌라 수열들이다. 하지만, 이경우 (4, 3, 2, 5, 1) 은 가능한 곤돌라 수열이 아니다. (곤돌라 번호의 순서가 잘못되어 있다.)
만약 곤돌라 1번 만이 고장난 상황이라면, (4, 5, 6, 2, 3) 의 곤돌라 수열을 만들 수 있다. 만약 이후 4번 곤돌라가 고장난다면, 7번 곤돌라가 그 자리에 있게 되고, (6, 2, 3, 7, 5) 가 가능한 곤돌라 수열이 된다. 만약 7번 곤돌라가 이후에 고장이 난다면, 8번이 그 자리를 차지할 것이고 (3, 8, 5, 6, 2) 가 가능한 곤돌라 수열들 중 하나가 된다.
| 고장난 곤돌라 | 새 곤돌라 | 가능한 곤돌라 수열 중 하나 |
|---|---|---|
| 1 | 6 | (4, 5, 6, 2, 3) |
| 4 | 7 | (6, 2, 3, 7, 5) |
| 7 | 8 | (3, 8, 5, 6, 2) |
교체 수열이라는 것은 고장난 곤돌라들의 번호를 고장난 순서에 따라 쓴 것이다. 직전의 예에서 교체 수열은 (1, 4, 7) 이다. 교체 수열 e이 곤돌라 수열 g를 만든다고 말을 할 수 있는데, 그것은 초기 상황에서 시작해서 r에 해당하는 방법으로 곤돌라들이 고장난 직후에, g가 가능한 곤돌라 수열들 중 하나인 경우를 의미한다.
이 문제들에서는 주어진 곤돌라 수열을 만들 수 있는 교체 수열을 생성하여야 한다. 여러 개의 교체 수열이 가능한 경우 그 중 하나를 생성하면 된다. 다음과 같이 선언된 함수 replacement 를 구현해야 한다.
- replacement(n, gondolaSeq, replacementSeq)
- n: 입력 곤돌라 수열의 길이이다.
- gondolaSeq: 크기 n인 배열; gondolaSeq 는 항상 가능한 곤돌라 수열이며, gondolaSeq[i] 는 번 원소이다 (1 ≤ i ≤ n-1).
- 함수는 교체 수열의 길이 l을 리턴해야 한다.
- replacementSeq: 교체 수열을 저장하기에 충분한 크기의 배열; replacementSeq[i] 에는 계산된 교체 수열의 i번 원소가 저장되어야 한다 (0 ≤ i ≤ l-1).
입력
첫째 줄에 입력 수열의 길이 n이 주어진다.
둘째 줄에는 gondolaSeq[0], ..., gondolaSeq[n-1]이 주어진다.
출력
replacement함수의 리턴 값을 출력하고, 공백을 출력한 다음, replacementSeq를 공백으로 구분해 출력한다.
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 5 | n ≤ 100, 1 ≤ gondolaSeq[i] ≤ n+1 |
| 2 | 10 | n ≤ 1,000, 1 ≤ gondolaSeq[i] ≤ 5,000 |
| 3 | 20 | n ≤ 100,000, 1 ≤ gondolaSeq[i] ≤ 250,000 |
예제 입력 1
2 3 2
예제 출력 1
1 1
힌트
| 서브태스크 | gondolaSeq | 리턴 값 | replacementSeq |
|---|---|---|---|
| 1 | (3, 1, 4) | 1 | (2) |
| 1 | (5, 1, 2, 3, 4) | 0 | () |
| 2 | (2, 3, 4, 9, 6, 7, 1) | 2 | (5, 8) |
출처
Olympiad > International Olympiad in Informatics > IOI 2014 > Day 2 4-2번
- 문제의 오타를 찾은 사람: yclock
- 문제를 만든 사람: Michal Forišek
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호