11387 - The 3-Regular Graph

All about problems in Volume 113. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

11387 - The 3-Regular Graph

Post by andmej » Wed Jan 16, 2008 3:08 am

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:
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

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

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Wed Jan 16, 2008 4:20 am

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
Location: (CSE,DU) Dhaka,Bangladesh

11387 wa,please help

Post by turcse143 » Fri Feb 22, 2008 9:08 am

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:

Post by mf » Fri Feb 22, 2008 1:13 pm

Your output for n=2 is wrong.

turcse143
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm
Location: (CSE,DU) Dhaka,Bangladesh

Post by turcse143 » Fri Feb 22, 2008 8:30 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

Post by acao11 » Fri May 09, 2008 9:59 pm

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: 141
Joined: Sat Jun 30, 2007 2:52 pm
Location: Dhaka,Bangladesh

Re: 11387 - The 3-Regular Graph

Post by lnr » Sat Jun 21, 2008 12:40 pm

Code: Select all

turcse 143
Please remove your code if you got AC.

lnr
Experienced poster
Posts: 141
Joined: Sat Jun 30, 2007 2:52 pm
Location: Dhaka,Bangladesh

Re: 11387 - The 3-Regular Graph

Post by lnr » Sat Jun 21, 2008 12:45 pm

Code: Select all

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

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

Re: 11387 - The 3-Regular Graph

Post by @li_kuet » Tue Aug 14, 2012 11:40 pm

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

Post Reply

Return to “Volume 113 (11300-11399)”