27363번 - 편지 돌리기 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 92 | 16 | 12 | 20.690% |
문제
Albert와 친구들은 편지 릴레이 놀이를 즐겨한다. 총 $N$명의 어린이들은 1번부터 $N$번까지 번호가 붙어있고 각자 편지를 한 장씩 쓴다 - 편지지에는 편지를 쓴 아이 자신의 번호를 써둔다. 모두 편지를 쓴 후, $i$번째 아이는 자신이 쓴 편지를 $F_i$번째 아이에게 전달한다. 만약 $F_i = i$인 경우 자신의 편지를 자신이 갖고 있으면 된다. 이때 공평한 놀이가 되도록 모든 아이가 반드시 한 장씩의 편지를 받아야 한다. 따라서 배열 $F$에는 $1$부터 $N$까지의 정수가 정확히 한 번씩 등장해야 한다. 편지 전달 방법을 표현한 배열 $F$를 "편지 돌리기 배열" 이라 부르자. N명의 아이가 모두 동시에 규칙대로 다음 아이에게 편지를 전달하면 "한 번" 편지를 돌렸다고 말한다. 이를 반복하다 보면 언젠가는 각자 자신이 처음에 썼던 편지를 받게 된다.
예를 들어 $N = 10$, $F = [2, 3, 1, 5, 6, 7, 4, 9, 8, 10]$ 라 하자. 편의상 $F$를 이용하여 편지 돌리기를 $k$번 마친 후 $i$번째 아이가 갖고 있는 편지에 쓰인 번호를 $L_{F}(k, i)$라 하자.
- $k = 0$: 아래 표에서 보이듯 편지 돌리기를 시작하기 전 모든 아이가 자신이 쓴 편지를 갖고 있다.
- $k = 1$: 한 번 편지 돌리기를 마친 후, 1번 아이는 2번 아이에게 자신의 편지를 전달하였으므로 2번 아이가 1번이 적힌 편지를 갖고 있다. 마찬가지로 8번과 9번 아이는 서로에게 자신이 갖고 있던 편지를 주었고, 10번 아이는 자신의 편지를 그대로 갖고 있다.
- $k = 2$: 1번부터 7번 아이는 자신의 편지를 갖고 있지 않지만 8, 9, 10번 아이는 두 번째 편지 돌리기를 마친 후 각자 자신의 편지를 갖고 있다.
- $k = 3$: 1, 2, 3, 10번 아이는 각자 자신의 편지를 갖고 있고 나머지 아이들은 다른 아이의 편지를 갖고 있다.
Albert와 아이들은 최소 몇 번의 편지 돌리기를 마치면 각자 자신의 편지를 손에 쥐게 되는지 쉽게 풀 수 있었고, 편의상 이를 $R(F)$라 표현하기로 했다. 이는 수학적으로 모든 $1 \le i \le N$인 $i$에 대해 $L_F(k, i) = i$를 만족하는 $k > 0$중 가장 작은 값을 나타낸다. 이를 $F$의 "편지 돌리기 점수"라 하자. 위 예제에서 $F$의 편지 돌리기 점수는 12이다.
새로운 문제 만들기를 좋아하는 Albert는 이보다 조금 더 어려운 문제를 생각해 냈다. 우선 임의의 두 정수 $1 \le x, y \le N$를 고른 후 $F_x$ 와 $F_y$ 값을 맞바꾸어 새로운 편지 돌리기 배열 $G_{F, x, y}$를 얻을 수 있다 ($F$의 나머지 원소 값은 바꾸지 않는다). 만약 $x = y$인 두 정수를 골랐다면 자명하게도 $G_{F, x, y} = F$인데, 이것도 허용한다. 이렇게 얻을 수 있는 모든 배열 $G_{F, x, y}$의 "편지 돌리기 점수"중 최솟값을 구해보고 싶다.
위의 예제에서 만약 $x = 1, y = 10$을 고른다면 $G_{F, x, y} = [10, 3, 1, 5, 6, 7, 4, 9, 8, 2]$가 된다. 이때 처음 네 번의 편지 돌리기를 마친 후 각자 아이가 들고 있는 편지의 번호는 아래와 같고, 이 배열의 편지 돌리기 점수는 4점이 됨을 알 수 있다.
이 예제에서 위와 같이 $F$ 배열의 두 원소 값을 교환하여 달성할 수 있는 편지 돌리기 점수의 최솟값은 4점이다.
입력으로 $N$, $F$가 주어졌을 때, $F$의 편지 돌리기 점수 그리고 $F$의 두 원소 값을 교환하여 달성할 수 있는 편지 돌리기 점수의 최솟값을 구해보자.
입력
첫 줄에 테스트 케이스의 수 $T$가 주어진다.
각 테스트 케이스의 첫 줄에는 $N$이 주어진다. 둘째 줄에는 배열 $F$의 원소 $N$개의 정수가 공백으로 구분되어 주어진다.
출력
각 테스트 케이스의 정답인 두 정수를 공백으로 구분하여 각 줄에 출력한다. 첫 정수는 $F$의 편지 돌리기 점수이고 두 번째 정수는 $F$의 원소 두 개를 교환하여 새 배열을 만들어서 얻을 수 있는 편지 돌리기 점수의 최솟값이다.
제한
- $1 \le T \le 10$
- $2 \le N \le 250000$
- $1 \le i \le N$ 인 $i$에 대하여 $1 ≤ F[i] ≤ N$ 이다.
- 배열 $F$의 원소들은 고유하다 (중복된 값이 주어지지 않는다).
- 각 테스트 케이스의 정답인 두 정수 값이 모두 $10^{13}$ 이하인 입력만 주어진다.
예제 입력 1
3 10 2 3 1 5 6 7 4 9 8 10 16 2 3 4 5 6 7 8 1 10 11 12 13 9 15 16 14 10 2 3 1 5 6 4 8 7 10 9
예제 출력 1
12 4 120 8 6 6
예제 1: 본문에서 다루었다.
예제 2: 추가 설명 없음.
예제 3: 얻을 수 있는 모든 $G[F]$중 $F$보다 편지 돌리기 점수가 낮은 경우가 없다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호