시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 406 | 237 | 197 | 63.548% |
욱제는 카드 게임에서 1부터 N까지의 정수가 중복되지 않게 하나씩 적혀있는 N개의 카드를 배정 받았다. 욱제는 배정 받은 카드를 책상 위에 일렬로 배열했다. 하지만 결벽증이 있는 욱제는 카드가 아무 순서대로 배열되는 걸 참을 수 없었다!
욱제는 카드 배열을 벗어나지 않는 어떤 구간 [L, R](1 ≤ L < R ≤ N)을 정해서 이 구간을 통째로 뒤집는(reverse) 연산을 할 수 있다. 예를 들어, 배열 {1, 5, 10, 15, 20, 25}에서 [2, 5]를 뒤집으면 {1, 20, 15, 10, 5, 25}가 된다.
욱제의 결벽증을 최대한 해소하려면, 이러한 연산을 잘 수행해서 어떤 상태에 최대한 가깝게 만들어야 한다. 왼쪽부터 카드에 인덱스를 부여했을 때, i번째 카드에 정수 i가 가장 많이 적힌 상태가 바로 그 상태이다.
“왼쪽 문짝이 오른쪽 문짝보다 0.256mm 정도 더 기울었잖아?!?!?!?!?”
욱제의 결벽증이 극에 달하고 있다! 욱제를 위해 최대한 많은 카드를 최적의 상태로 만들어주자!
첫째 줄에 카드 개수 N이 주어진다. (1 ≤ N ≤ 1,000)
둘째 줄에 초기의 카드 배열이 왼쪽부터 순서대로 주어진다.
첫째 줄에 주어진 조건에 맞게 카드를 배열하기 위해 필요한 연산의 횟수 op를 출력한다. op는 N×N보다 작거나 같아야 한다.
이후 op개의 줄에 걸쳐 연산에 필요한 [L, R]쌍을 순서대로 출력한다. op가 0이라면 아무것도 출력하지 않는다. L과 R은 하나의 공백을 사이에 두고 출력한다.
5 2 1 5 4 3
2 3 5 1 2
5 5 2 1 4 3
2 1 3 3 5
1 1
0
High School > 선린인터넷고등학교 > 제2회 천하제일 코딩대회 예선 C번