Page 1 of 1

11387 - The 3-Regular Graph

Posted: Wed Jan 16, 2008 3:08 am
by 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! :lol:

Posted: Wed Jan 16, 2008 4:20 am
by 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

11387 wa,please help

Posted: Fri Feb 22, 2008 9:08 am
by 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. :(

Posted: Fri Feb 22, 2008 1:13 pm
by mf
Your output for n=2 is wrong.

Posted: Fri Feb 22, 2008 8:30 pm
by turcse143
Thanks a lot, mf
i got AC. i overlooked it. :)

11387 - The 3-Regular Graph

Posted: Fri May 09, 2008 9:59 pm
by 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 ;

  }

}

}

Re: 11387 - The 3-Regular Graph

Posted: Sat Jun 21, 2008 12:40 pm
by lnr

Code: Select all

turcse 143
Please remove your code if you got AC.

Re: 11387 - The 3-Regular Graph

Posted: Sat Jun 21, 2008 12:45 pm
by lnr

Code: Select all

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

Re: 11387 - The 3-Regular Graph

Posted: Tue Aug 14, 2012 11:40 pm
by @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