URAL 1614. National Project “Trams” [ 构造欧拉回路 ]

1614. National Project “Trams”

Time limit: 0.5 second
Memory limit: 64 MB

President has declared the development of tram service a priority national project. As a part of this project, Yekaterinburg will receive enough budget funds to carry out a complete reconstruction of the city's tram network.

There are 2n tram stops in Yekaterinburg. In the course of reconstruction, the stops will be left in their places and no new stops will be built, but new tram railways will be laid so that it will be possible to go by tram from every tram stop to any other tram stop without any intermediate stops.

Having studied messages at the tram forum, the city authorities found out that citizens would be satisfied with the reconstruction only if for every pair of tram stops there would be a tram route connecting these stops without any intermediate stops. It is clear that the network of n(2n − 1) routes consisting of only two stops each satisfies this requirement. However, Yekaterinburg Mayor wants exactly n routes to be left after the reconstruction, and each tram must make exactly 2n stops (including the final ones) on its route. Trams must go along these routes in both directions. Suggest a plan of reconstruction that will satisfy both citizens and Mayor.

Input

The only input line contains the integer n, 1 ≤ n ≤ 100.

Output

Output n lines describing tram routes. Each route is a sequence of integers in the range from 1 to 2n separated by a space. A route may go through a stop several times. If the problem has several solutions, you may output any of them. If there is no solution, output one line containing the number −1.

Sample

input	output
3	1 6 2 1 3 4 2 3 6 5 4 6 5 1 4 2 5 3

Problem Author: Alexander Ipatov (idea — Magaz Asanov)
Problem Source: The 12th Urals Collegiate Programing Championship, March 29, 2008

Tags: tricky problem ()

Difficulty: 732 Printable version Submit solution Discussion (4)
My submissions All submissions (1013) All accepted submissions (480) Solutions rating (382)

题意：

1-2*n个车站，两两之间要连一条边，即 2*n*(2*n-1)/2条边。

现在让你设计n条路线，每个路线包括2*n个车站，即每条路线你能连出2*n-1条边。

求一种满足题意的设计方案。

题解：

一开始试图设计如：

1 2 3 4 5 6

2 4 6 1 3 5

3 6 2 5 1 4

的设计，不过，在n=4的时候就蹦了。

找了好久的规律，设计出如：

1 6 2 5 3 4

2 1 3 6 4 5

3 2 4 1 5 6

的设计，就能满足所有条件了。（第一次从 1 2 3 4 5 6取首尾首尾，第二次从 2 3 4 5 6 1 取首尾首尾。。。）

6160974

16:53:31
16 Mar 2015

njczy2010

1614. National Project “Trams”

G++ 4.9

Accepted

0.046

414 KB

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <stack>
 4 #include <vector>
 5 #include <algorithm>
 6 #include <queue>
 7 #include <map>
 8 #include <string>
 9 
10 #define ll long long
11 int const N = 105;
12 int const M = 205;
13 int const inf = 1000000000;
14 ll const mod = 1000000007;
15 
16 using namespace std;
17 
18 int n;
19 int ans[N][2*N];
20 int b[N][2*N];
21 
22 void ini()
23 {
24     int i,j;
25     int p=2*n;
26     for(i=1;i<=n;i++){
27         for(j=1;j<=2*n;j++){
28             b[i][j]=(i+j-1)%p;
29             if(b[i][j]==0){
30                 b[i][j]=p;
31             }
32         }
33     }
34     /*
35     printf("  b
");
36     for(i=1;i<=n;i++){
37         printf("%d",b[i][1]);
38         for(j=2;j<=2*n;j++){
39             printf(" %d",b[i][j]);
40         }
41         printf("
");
42     }*/
43 }
44 
45 void solve()
46 {
47     int i,j;
48     for(i=1;i<=n;i++){
49         for(j=1;j<=2*n;j++){
50             ans[i][j]=b[i][j/2+1];
51             j++;
52             ans[i][j]=b[i][2*n-j/2+1];
53         }
54     }
55 
56 }
57 
58 void out()
59 {
60     int i,j;
61     for(i=1;i<=n;i++){
62         printf("%d",ans[i][1]);
63         for(j=2;j<=2*n;j++){
64             printf(" %d",ans[i][j]);
65         }
66         printf("
");
67     }
68 }
69 
70 int main()
71 {
72    // freopen("data.in","r",stdin);
73     //freopen("data.out","w",stdout);
74     //scanf("%d",&T);
75     //for(cnt=1;cnt<=T;cnt++)
76     while(scanf("%d",&n)!=EOF)
77     {
78         ini();
79         solve();
80         out();
81     }
82 }