10129 - Play on Words

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

Moderator: Board moderators

Rossi
New poster
Posts: 20
Joined: Thu Mar 21, 2002 2:00 am
Location: Bangladesh

10129 - Play on Words

Post by Rossi » Tue Mar 26, 2002 1:19 pm

I think its simple Euler tour testing .
but getting wrong answer.....

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan

Post by LittleJohn » Tue Mar 26, 2002 2:39 pm

The graph may be disconnected, did you do this check?

Mohammad Mahmudur Rahman
Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

10129 - Play on words

Post by Mohammad Mahmudur Rahman » Thu Dec 02, 2004 12:57 am

I think this is an easy problem where all I need to do is to detect the presence of an euler path in a directed graph. But I am getting repeated WA :o for apparantly no reason. Can someone give me some tricky I/O please? Thanks in advance.
You should never take more than you give in the circle of life.

sidky
New poster
Posts: 50
Joined: Wed Nov 06, 2002 1:37 pm
Location: Planet Earth, Universe
Contact:

Post by sidky » Thu Dec 02, 2004 1:44 am

The problems doesn't have any tricky inputs. Have you checked whether the graph is connected?

Mohammad Mahmudur Rahman
Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

Post by Mohammad Mahmudur Rahman » Thu Dec 02, 2004 2:53 am

sidky wrote: Have you checked whether the graph is connected?
Yes, I did. The problem is somewhere else. I think I am missing something & hence should recode it from the scratch.
You should never take more than you give in the circle of life.

Mohammad Mahmudur Rahman
Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

Post by Mohammad Mahmudur Rahman » Thu Dec 02, 2004 3:24 am

Well, recoding worked. I've got AC though couldn't figure out the problem in the previous version. :roll:. Thanks to you, Sidky for your suggestion.
You should never take more than you give in the circle of life.

backjack02
New poster
Posts: 2
Joined: Fri Jan 21, 2005 9:07 pm

10129 Play on Words WA

Post by backjack02 » Fri Jan 21, 2005 9:11 pm

Here is my code, why do I always get wrong answer?
Where is my problem?


#include <stdio.h>
4 #include <stdlib.h>
5
6 int main(int argc, char **argv)
7 {
8 long long t, n;
9 int i, j, ctn, flag;
10 char c, link;
11 char *check;
12 check=(char *)malloc(sizeof(char)*1001);
13
14 scanf("%lld%c", &t, &c);
15 for(i=0; i<t; i++){
16 scanf("%lld%c", &n, &c);
17 if(n<1 || n>100000)
18 return 0;
19 flag=1;
20 for(j=0; j<n; j++){
21 ctn=0;
22 while((c=getchar())!='\n'){
23 if(c==EOF)
24 return 0;
25 check[ctn]=c;
26 ctn++;
27 }
28 check[ctn]='\0';
29 if(ctn<2 || ctn>1000)
30 return 0;
31
32 if(j>0){
33 if(check[0]!=link)
34 flag=0;
35 }
36
37 link = check[ctn-1];
38 }
39 if(flag==1)
40 printf("Ordering is possible.\n");
41 else
42 printf("The door cannot be opened.\n");
43 }
44 return 0;
45 }


..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Sat Jan 22, 2005 7:07 am

You have wrong understanding on the problem.
It is asked "whether it is possible to arrange all of the plates in a sequence"

You can arrange the order of word, so for
2
abc
xxa
The answer is "possible".
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

backjack02
New poster
Posts: 2
Joined: Fri Jan 21, 2005 9:07 pm

Post by backjack02 » Sat Jan 22, 2005 7:13 am

I got it!
Thank you:-)

akiha
New poster
Posts: 7
Joined: Sat Jan 22, 2005 6:43 pm

10129-SEGMENTATION FAULT

Post by akiha » Wed Jan 26, 2005 9:31 pm

All the variable and array are well defined
no pointer is used

why segmentation fualt?.............orz

THZ for any reply

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Thu Jan 27, 2005 6:49 am

There are many ways to get segmentation fault.
Although you say array are well defined, how do you ensure that without knowing judge input?
In my opinion, there is only one way to ensure it, when you access any array, say a, you check if i < 0 or i > max. bound, if yes, then you crash the program by i = 1 / 0 (floating point error)

Always check your program with boundray case, for either N = 1 or 100000, you have to check if your program can passes such case by TESTING. Don't just read your code and then think it will pass.

Some other way of segmentation fault is "stack overflow". Say for this C program:

Code: Select all

re() {
   int i;
   re();
}

main() {
   re();
}
The endless recursion will get stack overflow and give you segmentation fault. Check if your program will get endless recursion.
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

akiha
New poster
Posts: 7
Joined: Sat Jan 22, 2005 6:43 pm

Post by akiha » Thu Jan 27, 2005 3:35 pm

Code: Select all

#include <stdio.h>
#include <string.h>

main(void)
{       
	char in[1000];
	int head[26];
	int tail[26];
	int con[26][26];
	int check[26];
	int g[3];
	int n=0;
	int a,b,i,j,m,t,count,p,q;
	int s=0;
	int cb=0;
	char prichk='0';
	char secchk='0';
	char terchk='0';
	char finalchk='0';
	char finalchk2='0';
	char netio='0';
	
	scanf ("%d\n" ,&t);

	for (m=0;m<t;m++)
	{

		for (b=0;b<27;b++)
		{
			head[b]=0;
			tail[b]=0;
			check[b]=0;
		}
		printf("%d%d%d\n",head[26],tail[26],check[26]);

		for (b=0;b<27;b++)
		{
			for (a=0;a<27;a++)
			{
				con[b][a]=0;
			}
		}

		g[0]=-1;
		g[1]=-1;
		g[2]=0;
		
		scanf ("%d\n" ,&s);

		for (count=0;count<s;count++)
		{
			gets (in);
			n = strlen(in);

                                                  -SKIP-
                                 }
	}
	return 0;
}
I CHECK ALL THE BOUND
I SEEMS NO PROBLEM......OTZ

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Thu Jan 27, 2005 3:46 pm

akiha wrote:

Code: Select all

#include <stdio.h>
	int head[26];
	int tail[26];
	int con[26][26];
	int check[26];

		for (b=0;b<27;b++)
		{
			head[b]=0;
			tail[b]=0;
			check[b]=0;
		}
		printf("%d%d%d\n",head[26],tail[26],check[26]);
CERTAINLY IT HAS PROBLEM!
for "int tail[26]", the elements are numbered from 0 to 25
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

akiha
New poster
Posts: 7
Joined: Sat Jan 22, 2005 6:43 pm

Post by akiha » Thu Jan 27, 2005 6:00 pm

I KNOW THAT

BUT WHEN I SET B<26
IT ALSO SEGMENTATAION ERROR

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Thu Jan 27, 2005 6:04 pm

Similar mistake here:
char in[1000];
To hold a string of 1000 chars long, the array size should NOT be 1000.
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

Post Reply

Return to “Volume 101 (10100-10199)”