11387 - The 3-Regular Graph

[andmej]

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!

[rio]

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]

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.

[mf]

Your output for n=2 is wrong.

[turcse143]

Thanks a lot, mf
i got AC. i overlooked it.

[acao11]

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]

Code: Select all

turcse 143
Please remove your code if you got AC.

[lnr]

Code: Select all

acao 11
Your algorithm is wrong.
Please check it again.

[@li_kuet]

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