패스
문제
N명의 사람들이 원형으로 앉아있고, i번째 오른쪽 사람은 i+1번째, N번째 사람 오른쪽엔 1번째가 앉는다.
1번이 처음에 공을 가지고 있고, 둘러앉은 사람 가운데에는 1~N의 카드가 있다.
둘러앉은 사람들은 다음과 같은 게임을 N차례 진행했다.
- 공을 가진 사람이 나와서 카드 한 장을 뽑은 다음 자기 자리로 돌아간다.
- 카드를 뽑은 사람은 자신으로부터 카드에 적힌 수만큼 오른쪽에 있는 사람에게 공을 패스한다.
- 뽑은 카드는 버리며, 다른 사람들은 이 카드를 더 이상 뽑을 수 없다.
게임이 끝난 후, 사람들은 자신들 모두가 공을 정확히 한 번 패스받았다는 사실을 깨달았다.
신은 사람들이 어떤 순서로 공을 패스했는지 알아내야 한다.
입력
첫째 줄에 사람의 수 N이 입력된다. (1 <= N <= 1,000,000)
출력
만약 모든 사람이 정확히 한 번 공을 받게 되는 상황이 발생할 수 없다면 -1을 출력한다.
그렇지 않다면, 뽑힌 카드를 순서대로 N개 출력하라.
1
2
3
4
5
6
7
8
9
예제 입력 1
4
예제 출력 1
4 3 2 1
예제 입력 2
3
예제 출력 2
-1
풀이
코포를 안한지 좀 됐지만 Div2 B번에서 본 것 같은 기분이 든다.
수학 관계보다는 애드 훅 성향이 더 강하긴하지만 뭐..
해보면 1을 제외한 홀수면 안되고, 짝수면 된다.
가장 간단한 방법은 양끝을 채워나가는 것인데 짝수면 깔끔하게 나눠진다.
8이면 8 7 2 5 4 3 6 1.. 이렇게. 규칙이 보이니 그걸 짜면 된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <functional>
#include <algorithm>
#include <math.h>
#include <map>
using namespace std;
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
int n, m, k, t;
cin >> n;
//애드 훅인듯. 짝수면 가능 홀수면 불가능
if(n!=1 && n%2==1){
cout << "-1";
}
else{
cout << n << ' ';
for(int i=1;i<n;i++){
if(i%2==1){
cout << n-i << ' ';
}
else cout << i << ' ';
}
}
return 0;
}