11387 - The 3-Regular Graph

Moderator: Board moderators

andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

11387 - The 3-Regular Graph

Can somebody tell me what is a possible correct output for this input?

Input

Code: Select all

``````7
8
``````
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. Maybe that's why I'm getting Wrong Answer?

Thanks!
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
The output is:

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
``````
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.
When a graph is 3 regular, it must have exactly n*3/2 edges.
-----
Rio

turcse143
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm

i don't know whats the problem of my code.
ples, help me to find out the error of my code.

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;
}
}
}

}
}
}
``````
ples,check it.
''I want to be most laziest person in the world''

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Your output for n=2 is wrong.

turcse143
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm
Thanks a lot, mf
i got AC. i overlooked it.
''I want to be most laziest person in the world''

acao11
New poster
Posts: 1
Joined: Thu May 08, 2008 4:49 pm

11387 - The 3-Regular Graph

I dont know why it is wrong... What case doesnt it get ?...

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 ;

}

}

}``````

lnr
Experienced poster
Posts: 142
Joined: Sat Jun 30, 2007 2:52 pm

Re: 11387 - The 3-Regular Graph

Code: Select all

``````turcse 143
``````

lnr
Experienced poster
Posts: 142
Joined: Sat Jun 30, 2007 2:52 pm

Re: 11387 - The 3-Regular Graph

Code: Select all

``````acao 11
``````

@li_kuet
New poster
Posts: 44
Joined: Fri May 25, 2012 6:22 pm

Re: 11387 - The 3-Regular Graph

Who r getting WA can try this Input
Input :

Code: Select all

``````1
2
3
6
22
100
0
``````
Output :

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
``````