uva 11630 or hdu 2987 Cyclic antimonotonic permutations(構造水題)
9961 ワード
転載は出典を明記してください. http://www.cnblogs.com/fraud/ ——by fraud
Cyclic antimonotonic permutations
Time Limit: 20000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Problem Description
A permutation is a sequence of integers which contains each integer from 1 to n exactly once. In this problem we are looking for permutations with special properties:
1. Antimonotonic: for each consecutive 3 values p
i-1, p
i, p
i+1 (1 < i < n), p
i should either be the smallest or the biggest of the three values.
2. Cyclic: The permutation should consist of only one cycle, that is, when we use p
i as a pointer from i to p
i, it should be possible to start at position 1 and follow the pointers and reach all n positions before returning to position 1.
Input
The input file contains several test cases. Each test case consists of a line containing an integer n, (3 ≤ n ≤ 10
6), the number of integers in the permutation. Input is terminated by n=0.
Output
For each test case print a permutation of the integers 1 to n which is both antimonotonic and cyclic. In case there are multiple solutions, you may print any one. Separate all integers by whitespace characters.
Sample Input
3 5 10 0
Sample Output
3 1 2 4 5 2 3 1 6 10 2 9 3 5 4 7 1 8
Source
2009/2010 Ulm Local Contest
奇数と偶数に分けて、勝手にやってください.
HDuはspecial judgeがないためACできません
コード君
Cyclic antimonotonic permutations
Time Limit: 20000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Problem Description
A permutation is a sequence of integers which contains each integer from 1 to n exactly once. In this problem we are looking for permutations with special properties:
1. Antimonotonic: for each consecutive 3 values p
i-1, p
i, p
i+1 (1 < i < n), p
i should either be the smallest or the biggest of the three values.
2. Cyclic: The permutation should consist of only one cycle, that is, when we use p
i as a pointer from i to p
i, it should be possible to start at position 1 and follow the pointers and reach all n positions before returning to position 1.
Input
The input file contains several test cases. Each test case consists of a line containing an integer n, (3 ≤ n ≤ 10
6), the number of integers in the permutation. Input is terminated by n=0.
Output
For each test case print a permutation of the integers 1 to n which is both antimonotonic and cyclic. In case there are multiple solutions, you may print any one. Separate all integers by whitespace characters.
Sample Input
3 5 10 0
Sample Output
3 1 2 4 5 2 3 1 6 10 2 9 3 5 4 7 1 8
Source
2009/2010 Ulm Local Contest
奇数と偶数に分けて、勝手にやってください.
HDuはspecial judgeがないためACできません
1 //#####################
2 //Author:fraud
3 //Blog: http://www.cnblogs.com/fraud/
4 //#####################
5 #include <iostream>
6 #include <sstream>
7 #include <ios>
8 #include <iomanip>
9 #include <functional>
10 #include <algorithm>
11 #include <vector>
12 #include <string>
13 #include <list>
14 #include <queue>
15 #include <deque>
16 #include <stack>
17 #include <set>
18 #include <map>
19 #include <cstdio>
20 #include <cstdlib>
21 #include <cmath>
22 #include <cstring>
23 #include <climits>
24 #include <cctype>
25 using namespace std;
26 #define XINF INT_MAX
27 #define INF 0x3FFFFFFF
28 #define MP(X,Y) make_pair(X,Y)
29 #define PB(X) push_back(X)
30 #define REP(X,N) for(int X=0;X<N;X++)
31 #define REP2(X,L,R) for(int X=L;X<=R;X++)
32 #define DEP(X,R,L) for(int X=R;X>=L;X--)
33 #define CLR(A,X) memset(A,X,sizeof(A))
34 #define IT iterator
35 typedef long long ll;
36 typedef pair<int,int> PII;
37 typedef vector<PII> VII;
38 typedef vector<int> VI;
39 #define MAXN 1000010
40 int a[MAXN];
41 int main()
42 {
43 int n;
44 while(scanf("%d",&n)&&n){
45 a[1]=3;
46 a[2]=1;
47 for(int i=3;i<=n;i++){
48 if(i&1)a[i]=i+2;
49 else a[i]=i-2;
50 }
51 if(n&1)a[n]=n-1;
52 else{
53 a[n]=n-2;
54 a[n-1]=n;
55 }
56 printf("%d",a[1]);
57 for(int i=2;i<=n;i++){
58 printf(" %d",a[i]);
59 }
60 printf("
");
61 }
62 return 0;
63 }コード君