Input
Code: Select all
7
8
Thanks!
![:lol:](./images/smilies/icon_lol.gif)
Moderator: Board moderators
Code: Select all
7
8
Code: Select all
Impossible
12
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 1
1 5
2 6
3 7
4 8
When a graph is 3 regular, it must have exactly n*3/2 edges.I think the graph is impossible to build when it has an odd (not pair) number of nodes, but I haven't been able to proof this yet.
Code: Select all
#include<stdio.h>
#include<string.h>
int data[101][101];
main()
{
int i,j,n,count,c;
freopen("11387.in","rt",stdin);
while(scanf("%d",&n)==1)
{
if(n==0)
break;
if(n%2!=0)
printf("Impossible\n");
else
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
data[i][j]=0;
c=0;
for(i=1;i<=n;i++)
{
count=0;
for(j=1;j<=n;j++)
{
if(j-i==1)
{
count++;
data[i][j]=1;
data[j][i]=1;
c++;
}
else if(j-i==3&&i%2!=0)
{
count++;
data[i][j]=1;
data[j][i]=1;
c++;
}
if(count==2)
break;
}
}
data[1][n-1]=1;
data[n-1][1]=1;
data[2][n]=1;
data[n][2]=1;
c+=2;
printf("%d\n",c);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(data[i][j]==1)
{
printf("%d %d\n",i,j);
data[j][i]=0;
}
}
}
}
}
}
Code: Select all
#include <iostream>
int main() {
int n ;
while (scanf("%d\n", &n)) {
if (n == 0)
break ;
if ( n >= 1 && n <= 100 ) {
int ** m = new int*[n] ;
int * d = new int[n] ;
for (int i = 0; i < n; i++) {
m[i] = new int[n] ;
d[i] = 0 ;
for (int j = 0; j < n ; j++)
m[i][j] = 0 ;
}
for(int i = 0; i < n; i++) {
int tmp = d[i] ;
for(int j = 1; j <= (3 - tmp); j++) {
if ((i + j) < n) {
d[i]++ ;
d[i+j]++ ;
m[i][i+j] = 1 ;
}
}
}
int e = 0 ;
for (int i = 0 ; i < n ; i++) {
for (int j = 0 ; j < n ; j++) {
if(m[i][j] == 1) {
e++ ;
m[j][i] = 0 ;
}
}
}
if (d[n-1] < 3)
printf("Impossible\n") ;
else {
printf("%d\n", e) ;
for (int i = 0 ; i < n ; i++) {
for (int j = 0 ; j < n ; j++) {
if(m[i][j] == 1) {
printf("%d %d\n", i+1, j+1) ;
}
}
}
}
delete d ;
delete m ;
}
}
}
Code: Select all
turcse 143
Please remove your code if you got AC.
Code: Select all
acao 11
Your algorithm is wrong.
Please check it again.
Code: Select all
1
2
3
6
22
100
0
Code: Select all
Impossible
Impossible
Impossible
9
1 2
1 3
1 4
2 5
2 6
3 4
3 5
4 6
5 6
33
1 2
1 3
1 4
2 5
2 6
3 7
3 8
4 9
4 10
5 11
5 12
6 13
6 14
7 15
7 16
8 17
8 18
9 19
9 20
10 21
10 22
11 12
11 13
12 14
13 15
14 16
15 17
16 18
17 19
18 20
19 21
20 22
21 22
150
1 2
1 3
1 4
2 5
2 6
3 7
3 8
4 9
4 10
5 11
5 12
6 13
6 14
7 15
7 16
8 17
8 18
9 19
9 20
10 21
10 22
11 23
11 24
12 25
12 26
13 27
13 28
14 29
14 30
15 31
15 32
16 33
16 34
17 35
17 36
18 37
18 38
19 39
19 40
20 41
20 42
21 43
21 44
22 45
22 46
23 47
23 48
24 49
24 50
25 51
25 52
26 53
26 54
27 55
27 56
28 57
28 58
29 59
29 60
30 61
30 62
31 63
31 64
32 65
32 66
33 67
33 68
34 69
34 70
35 71
35 72
36 73
36 74
37 75
37 76
38 77
38 78
39 79
39 80
40 81
40 82
41 83
41 84
42 85
42 86
43 87
43 88
44 89
44 90
45 91
45 92
46 93
46 94
47 95
47 96
48 97
48 98
49 99
49 100
50 51
50 52
51 53
52 54
53 55
54 56
55 57
56 58
57 59
58 60
59 61
60 62
61 63
62 64
63 65
64 66
65 67
66 68
67 69
68 70
69 71
70 72
71 73
72 74
73 75
74 76
75 77
76 78
77 79
78 80
79 81
80 82
81 83
82 84
83 85
84 86
85 87
86 88
87 89
88 90
89 91
90 92
91 93
92 94
93 95
94 96
95 97
96 98
97 99
98 100
99 100