409 - Excuses, Excuses!

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

Moderator: Board moderators

User avatar
yahoo
Learning poster
Posts: 93
Joined: Tue Apr 23, 2002 9:55 am

Problem with 409

Post by yahoo » Tue Jun 04, 2002 7:51 pm

I can't find any problem in my program.But it gives me w.a.Can anybody help me?
#include <stdio.h>
#include <string.h>
#include <ctype.h>

main()
{
char a[20][20],b[21][71],c[21][71];
char *st;
int i,j,k,m,n,r,len,cnt,o,d[20],high,count=0;
while(1)
{
r=scanf("%d%d",&m,&n);
if(r==EOF) break;
count++;
for(i=0;i<m;i++)
scanf("%s",a);

for(i=0;i<20;i++)
d=0;
for(i=0;i<=n;i++)
for(j=0;j<70;j++)
b[j]=0;

for(i=0;i<=n;i++)
{
for(j=0;j<71;j++)
{
if(b[j]!='\n') scanf("%c",&b[j]);
if(b[j]=='\n') {b[j]=0; break;}
}
}

for(i=0;i<=n;i++)
{
len=strlen(b);
for(j=0;j<len;j++)
c[j]=tolower(b[j]);
c[i][j]=0;
}

for(i=1;i<=n;i++)
{
len=strlen(c[i]);
{
for(j=0;j<len;j++)
if(!((c[i][j]>='a' && c[i][j]<='z') || c[i][j]==' '))
{
for(k=j;k<len;k++)
c[i][k]=c[i][k+1];
len--;j--;
}
if(len==0) strcpy(c[i],"1");
c[i][k]=0;
}
}

cnt=o=0;

for(i=1;i<=n;i++)
{
st=strtok(c[i]," \n");
if(st==NULL) break;
for(j=0;j<m;j++)
if(strcmp(a[j],st)==0) cnt++;
while(1)
{
st=strtok(NULL," \n");
if(st==NULL) break;
for(j=0;j<m;j++)
if(strcmp(a[j],st)==0) cnt++;
}
d[o++]=cnt;
cnt=0;
}

high=0;
for(i=0;i<n;i++)
if(d[i]>high) high=d[i];

printf("Excuse Set #%d\n",count);
for(i=1;i<m;i++)
if(d[i-1]==high)
printf("%s\n",b[i]);

printf("\n");
}
return 0;
}

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

409

Post by htl » Sun Aug 11, 2002 4:01 am

I don't exactly understand the description of the problem. The
problem says 'A keyword ``occurs" in an excuse if and only if it
exists in the string in contiguous form and is delimited by the
beginning or end of the line or any non-alphabetic character or
a space.' But every excuse is independent. Is it possible that
the part of the keyword appear at the end of the excuse and the
other part is at the beginning of the next excuse? I don't think
so. And is it possible that in every excuse I can't find out any
keywords? The code got WA. I can't find out the bugs.
[c]
#include<stdio.h>
#include<string.h>
void main(void)
{
int k,e,x,y,z,data[30],lens[2][30],len,a,max,count,check;
char *keyword[30],*excuse[30],s[100],c;
for(count=1;scanf("%d %d",&k,&e)!=EOF;count++)
{
for(x=0;x<k;x++)
{
scanf("%s",s);
lens[0][x]=strlen(s);
keyword[x]=(char *)malloc(sizeof(char)*(lens[0][x]+1));
strcpy(keyword[x],s);
}
c=getchar();
for(x=0;x<e;x++)
{
gets(s);
len=strlen(s);
excuse[x]=(char *)malloc(sizeof(char)*(len+1));
strcpy(excuse[x],s);
lens[1][x]=len;
}
for(x=0;x<e;x++)
data[x]=0;
for(x=0;x<e;x++)
for(y=0;y<k;y++)
if(lens[0][y]<=lens[1][x])
for(z=0;z<=lens[1][x]-lens[0][y];z++)
{
for(a=0,check=0;z+a<lens[1][x] && a<lens[0][y];a++)
if(!(excuse[x][z+a]>='a' && excuse[x][z+a]<='z' && keyword[y][a]==excuse[x][z+a] || excuse[x][z+a]>='A' && excuse[x][z+a]<='Z' && excuse[x][z+a]+'a'-'A'==keyword[y][a]))
if(!check)
check++,a--;
else
break;
if(a==lens[0][y])
data[x]++;
}
printf("Excuse Set #%d\n",count);
for(x=0,max=-1;x<e;x++)
if(data[x]>max)
max=data[x];
for(x=0;x<e;x++)
if(data[x]==max)
printf("%s\n",excuse[x]);
printf("\n");
for(x=0;x<k;x++)
free(keyword[x]);
for(x=0;x<e;x++)
free(excuse[x]);
}
}
[/c]

sjn
Learning poster
Posts: 73
Joined: Mon Apr 08, 2002 8:22 am
Contact:

p409-C++ Runtime Error!!

Post by sjn » Tue Aug 13, 2002 11:39 am

I don't know why i always got RTE
every time the program run into "print()" it got RTE.
i have also used "cout",but the result is the same with above :cry:

Can u tell me why?
thx in advance~
Last edited by sjn on Mon Feb 02, 2004 5:45 pm, edited 1 time in total.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Tue Aug 13, 2002 1:12 pm

you have definition

char excuse[1][][] /.....

and you use it

printf(..... , excuse[1][] .....

but in C/C++ arrays are indexed from 0 to N-1 (you have N=1) ... and if you try to use excuse[1] you got ALWAYS RTE :-) try to change this line to

excuse[0][] ......

sjn
Learning poster
Posts: 73
Joined: Mon Apr 08, 2002 8:22 am
Contact:

Thanks~

Post by sjn » Tue Aug 13, 2002 4:18 pm

hi,Dominik Michniewski

Thank u :lol:

With ur help,i have got AC

i am so careless :-?

User avatar
the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

to htl

Post by the LA-Z-BOy » Tue Oct 22, 2002 1:05 pm

i've runned your prog and got something...

[c]
tatil
matil
jatil
katil
patil
my dog ate tatil908 with 9katil for fkatil
tatil matil katil
now dog kicks atatila with 99katil[/c]

with output
[c]
Excuse Set #1
my dog ate tatil908 with 9katil for fkatil
tatil matil katil
[/c]

this soln counts excuses as follows:
3 keywords: ``my dog ate tatil908 with 9katil for fkatil''
3 keywords: ``tatil matil katil''
2 keywords: ``now dog kicks atatila with 99katil''

so far reading the proc. of p409 i think for exucuse1, "fkatil" is never a keyword because it just exists in contiguos form but is NOT
``delimited by the beginning or end of the line or any non-alphabetic character or a space '' -> what you think isn't ('a'-'z' and 'A' - 'Z') are only alphabetic characters? so shouldn't the digits be delimitter? and just like that ``atatila'' is not a keyword in excuse3.
so the list of delimitters are: 0123456789[space]".,!?&


here is a example of my soln's output

[c]
5 5
judge
valladolid
acm
online
kontest
the valladolid2002judge is always right!
online contest ate my peanut with acm's kontest9 thinking
acma 9onlinea valladolid judge painful floating kontest errors
acm!acm&acmbacmacm?
a man is not dog but BUBBLESORT is GOD[/c]

my prog. calculates:
occurence of keywords in braces:
(2)the valladolid2002judge is always right!
(3)online contest ate my peanut with acm's kontest9 thinking
(3)acma 9onlinea valladolid judge painful floating kontest errors
(2)acm!acm&acmbacmacm?
(0)a man is not dog but BUBBLESORT is GOD

i was also getting wa previously when i was using `scanf' and `gets' together. i then used `gets' only and got accepted.
greetings
:)
___________
the LA-Z-BOY

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Mon Dec 16, 2002 9:35 am

Can someone give me the count for:

Code: Select all

2 2
a
a
a a
a a a
I keep getting WA.. maybe I'm understanding the problem wrong..

User avatar
the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

Post by the LA-Z-BOy » Tue Dec 17, 2002 6:34 am

You can be sure that in the input no keywords are identical to each other, i.e. you're input is not possible.
And my accepted prog doesn't konsider this fact as well, so my prog gives strange kounts of keywords to your input!!! 4 for the first eXcuse and 6 for the second one 8)
So i think there're some other mistakes in your prog...did you remember to match keywords regardless of case?
___________
the LA-Z-BOy

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Tue Dec 17, 2002 10:49 am

I've checked tons of stuff, including cases.. any more test cases? =(

User avatar
Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

409 , compile error

Post by Riyad » Fri Sep 26, 2003 8:17 am

can any one plizzzzzzzzzzzz tell me why the folloeing code fetches me compile error :

Code: Select all

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

char keyword[30][500];

struct Excuses{

	int freq;
	char sentence[5000];
	

};

struct Excuses object[30];

int indx_for_keyword;
int index_for_excuses;

void init(){

	register int i ;
	
	for(i=0;i<30;i++){
	
		object[i].freq=0;
		strcpy(object[i].sentence,"");
	}

}


int check(char word[]){

	register int i ;
	
	for(i=0;i<indx_for_keyword;i++){
	
		if(strcmpi(word,keyword[i])==0){
			
			return 1;
		}
		else
			
			continue;
	}

	return 0;


}
void swap(struct Excuses object[],int i,int j){
	
	struct Excuses temp;
	
	temp=object[i];
	object[i]=object[j];
	object[j]=temp;

}

void qsort(int left,int right){

	int i,last;
	
	if(left>=right)
		return;
	
	swap(object,left,(left+right)/2);
	
	last=left;
	
	for(i=left+1;i<=right;i++)
	
	{
	
		if((object[i].freq-object[left].freq)<0)
		
			swap(object,++last,i);
	}
	swap(object,left,last);
	qsort(left,last-1);
	qsort(last+1,right);
}

void print(){

	register int i,max ;
	
	max=object[index_for_excuses-1].freq;

	for(i=0;i<index_for_excuses;i++){
		
		if(object[i].freq==max)
		
		{
			puts(object[i].sentence);
		}

	}	

}


void calculate(){

	register int i,count;
	char *p;
	char temp[100];

	
	for(i=0;i<index_for_excuses;i++){
		
		count=0;
		
		strcpy(temp,object[i].sentence);
		
		p=strtok(temp," ,.?&!");

		while(p){
		
			if(check(p)==1){
				count++;
			}
			
			p=strtok(NULL," ,.?&!");
		
		}
		
		object[i].freq=count;
	
	}
	
	qsort(0,index_for_excuses-1);

	print();

}


int main(){

	register int i ,j ;
	
	
	
	int count ;
	
	count =1;
	init();

	//freopen("input.txt","rt",stdin);

	while(scanf("%d %d",&i,&j)==2){
		
		getchar();

		
		for(indx_for_keyword=0;indx_for_keyword<i;indx_for_keyword++){
		
			gets(keyword[indx_for_keyword]);
			
		}

		for(index_for_excuses=0;index_for_excuses<j;index_for_excuses++){
		
			gets(object[index_for_excuses].sentence);
			
		}

		
		

		printf("Excuse Set #%d\n",count);

		calculate();


		count++;	
	
	
	
	
	}


	return 0;

}

and could any one check if my logic is right about this prob >
plizzzzzzzzz help
Bye
Riyad
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Post by hank » Sat Sep 27, 2003 5:09 pm

Do not use '//' comments.
It will cause a compile error.

User avatar
Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

thanx

Post by Riyad » Sat Sep 27, 2003 7:16 pm

thanx friend ,
but i did not send the code using "//" comment . i am having compile error for other reasons i guess . i used c++ for my language .
i am sick and tired of compile error in this program , any thing to do with structure declaration ?????????????/
Bye
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

playerX
Learning poster
Posts: 63
Joined: Fri Apr 25, 2003 11:57 pm
Location: Coimbra, Portugal

Post by playerX » Mon Sep 29, 2003 11:14 pm

here's what my red hat box's gcc outputs:

[playerx@x-p3rt playerx]$ gcc nhie.c
nhie.c:62: conflicting types for `qsort'
/usr/include/stdlib.h:738: previous declaration of `qsort'
nhie.c: In function `main':
nhie.c:154: warning: address of register variable `i' requested
nhie.c:154: warning: address of register variable `j' requested
[playerx@x-p3rt playerx]$

hope it helps

User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Post by hank » Tue Sep 30, 2003 12:05 pm

There is a function named qsort in <stdlib.h> .
You should remove qsort() in your code.

User avatar
Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

getting compile error still

Post by Riyad » Tue Sep 30, 2003 4:41 pm

thanx for u r help . i dont have a gcc linux compiler as a result of which i cant check the code of mine . i have changed according to u have asked , but still getting compililation error.
here is my new code :

Code: Select all

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

char keyword[50][1500];

struct Excuses{

	int freq;
	char sentence[5000];
	

};

struct Excuses object[50];

int indx_for_keyword;
int index_for_excuses;


void init(){

	int i ;
	
	for(i=0;i<50;i++){
	
		object[i].freq=0;
		
		
	}

}


int check(char word[]){

	int i ;
	
	for(i=0;i<indx_for_keyword;i++){
	
		if(strcmpi(word,keyword[i])==0){
			
			return 1;
		}

		else
			
			continue;
	}

	return 0;


}
void swap(struct Excuses object[],int i,int j){
	
	struct Excuses temp;
	
	temp=object[i];

	object[i]=object[j];

	object[j]=temp;

}

void sort(int left,int right){

	int i,last;
	
	if(left>=right)
		return;
	
	swap(object,left,(left+right)/2);
	
	last=left;
	
	for(i=left+1;i<=right;i++)
	
	{
	
		if((object[i].freq ) - (object[left].freq)<0)
		
			swap(object,++last,i);
	}

	swap(object,left,last);

	sort(left,last-1);

	sort(last+1,right);
}

void print(){

	int i,max ;
	
	
	max=object[index_for_excuses-1].freq;

	for(i=0;i<index_for_excuses;i++){
		
		if(object[i].freq==max)
		
		{
			puts(object[i].sentence);
		}

	}	

}


void calculate(){

	int i,count;
	char *p;
	char temp[100];

	
	for(i=0;i<index_for_excuses;i++){
		
		count=0;
		
		strcpy(temp,object[i].sentence);
		
		p=strtok(temp," ,.?&!");

		while(p){
		
			if(check(p)==1){
				count++;
			}
			
			p=strtok(NULL," ,.?&!");
		
		}
		
		object[i].freq=count;
	
	}
	
	sort(0,index_for_excuses-1);

	print();

}


int main(){

	
	int i ,j ;
	int count ;
	
	count =1;
	init();

	/*freopen("input.txt","rt",stdin);*/

	while(scanf("%d %d",&i,&j)==2){
		
		getchar();

		
		for(indx_for_keyword=0;indx_for_keyword<i;indx_for_keyword++){
		
			gets(keyword[indx_for_keyword]);
			
		}

		for(index_for_excuses=0;index_for_excuses<j;index_for_excuses++){
		
			gets(object[index_for_excuses].sentence);
			
		}

		
		

		printf("Excuse Set #%d\n",count);

		calculate();


		count++;	
	
	
	
	
	}


	return 0;

}
Thanx once again for u r help
Bye
Riyad
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

Post Reply

Return to “Volume 4 (400-499)”