# [Gold IV] 패스 [문제 링크](https://www.acmicpc.net/problem/25559) ## 문제 설명 <p>$N$명의 사람들이 원형으로 둘러앉아 있다. $i(1 \le i < N)$번째 사람의 오른쪽에는 $i + 1$번째 사람이, $N$번째 사람의 오른쪽에는 $1$번째 사람이 앉아 있으며, $1$번째 사람은 처음에 공을 가지고 있다.</p> <p>둘러앉은 사람들 가운데에는 $N$장의 카드가 있고, 각각의 카드에는 $1$부터 $N$까지의 정수가 하나씩 적혀 있다.</p> <p>둘러앉은 사람들은 다음과 같은 게임을 $N$차례 진행했다.</p> <ul> <li>공을 가진 사람이 나와서 카드 한 장을 뽑은 다음 자기 자리로 돌아간다.</li> <li>카드를 뽑은 사람은 자신으로부터 카드에 적힌 수만큼 오른쪽에 있는 사람에게 공을 패스한다.</li> <li>뽑은 카드는 버리며, 다른 사람들은 이 카드를 더 이상 뽑을 수 없다.</li> </ul> <p>게임이 끝난 후, 사람들은 자신들 모두가 공을 정확히 한 번 패스받았다는 사실을 깨달았다. 당신은 사람들이 어떤 순서로 공을 패스했는지 알아내야 한다.</p> ## 입력 <p>첫째 줄에 사람의 수 $N$이 입력된다. $(1 \le N \le 1\,000\,000)$</p> ## 출력 <p>만약 모든 사람이 정확히 한 번 공을 받게 되는 상황이 발생할 수 없다면 $-1$을 출력한다. 그렇지 않다면, $N$개의 정수 $A_1, A_2, \ldots, A_N$을 공백으로 구분하여 출력한다. $A_i$는 $i$번째 게임에서 뽑힌 카드에 적힌 수이다. 가능한 답이 여러 가지라면 아무거나 하나를 출력한다.</p> ## 풀이 * n이 1인 경우, 1 출력 * n이 홀수인 경우, 불가능 * n이 2인 경우, 2 1 출력 * n이 짝수인 경우, 1 -> n -> 2 -> n-1 -> 3 -> n-2 -> ... 순서대로 방문하도록 이동 거리 출력 ``` c++ #include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; if(n==1) { cout << "1"; } else if(n==2) { cout << "2 1"; } else if(n%2) { cout << -1; } else { int l=n-1, r=3; cout << n << ' ' << n-1 << ' ' << 2 << ' '; while(r<l) { cout << l - (r-1) << ' ' << (r+n) - l << ' '; l--; r++; } cout << 1; } } ```