123 - Searching Quickly

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

Moderator: Board moderators

FlyDeath
Learning poster
Posts: 73
Joined: Wed Jan 02, 2002 2:00 am
Location: Taiwan

Post by FlyDeath » Mon Mar 25, 2002 4:59 am

My program can handle output with spaces between words.But I still always get WA.I really don't knwo why.Can someone tell me?

Code: Select all

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

char iword[50][11];
char title[200][15][101];
char mixtitle[200][201];
char print[1000][101];
int titleword[200];
int howiword=0;
int howtitle=0;
int howprint=0;

int prestrcmp(char *a,char *b)
{
	int i,j;
	int p;
	int t1,t2;
	int result=0;
	int flag=0;
	int flag1=0;
	char m1[101],m2[101];
	p=0;
	for(i=0;i<101;i++)
	{
		m1[i]=0;
		m2[i]=0;
	}
	for(i=0;i<strlen(a);i++)
	{
		if(a[i]>=65&&a[i]<=90)
		{
			m1[p]=a[i];
			p++;
		}
	}
	p=0;
	for(i=0;i<strlen(b);i++)
	{
		if(b[i]>=65&&b[i]<=90)
		{
			m2[p]=b[i];
			p++;
		}
	}
	result=strcmp(m1,m2);
	if(result!=0)
		return result;
	else
	{
		for(i=0;i<howtitle;i++)
		{
			if(strlen(a)==strlen(mixtitle[i]))
			{
				flag=0;
				for(j=0;j<strlen(a);j++)
				{
					if(labs(a[j]-mixtitle[i][j])!=0&&labs(a[j]-mixtitle[i][j])!=32)
					{
						flag=1;
						break;
					}
				}
				if(flag==0)
					t1=i;
				break;
			}
		}
		for(i=0;i<howtitle;i++)
		{
			if(strlen(b)==strlen(mixtitle[i]))
			{
				flag=0;
				for(j=0;j<strlen(b);j++)
				{
					if(labs(b[j]-mixtitle[i][j])!=0&&labs(b[j]-mixtitle[i][j])!=32)
					{
						flag=1;
						break;
					}
				}
				if(flag==0)
					t2=i;
				break;
			}
		}
		if(t1!=t2)
			return t1-t2;
		else
		{
			t1=0;
			t2=0;
			for(i=0;i<strlen(a);i++)
			{
				if(a[i]>=65&&a[i]<=90)
				{
					t1=i;
					break;
				}
			}
			for(i=0;i<strlen(b);i++)
			{
				if(b[i]>=65&&b[i]<=90)
				{
					t2=i;
					break;
				}
			}
			return t1-t2;
		}
	}
}

int sort(const void *a,const void *b)
{
	return prestrcmp((char *)a,(char *)b);
}

void main()
{
	int temp2=0;
	char temp;
	int result=0;
	int yesno=0;
	int ptr;
	int i=0,j=0,k=0,m=0,n=0;
	int flag;
	int flag1;
#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	for(i=0;i<50;i++)
		for(j=0;j<11;j++)
			iword[i][j]=0;
	for(i=0;i<200;i++)
	{
		for(j=0;j<201;j++)
			mixtitle[i][j]=0;
		for(j=0;j<15;j++)
			for(k=0;k<101;k++)
				title[i][j][k]=0;
		titleword[i]=0;
	}
	for(i=0;i<1000;i++)
		for(j=0;j<101;j++)
			print[i][j]=0;
	while(1)
	{
		scanf("%s",&iword[howiword]);
		howiword++;
		if(strcmp(iword[howiword-1],"::")==0)
		{
			howiword--;
			break;
		}
	}
	ptr=0;
	howtitle=0;
	fgets(mixtitle[howtitle],200,stdin);
	while(1)
	{
		if(fgets(mixtitle[howtitle],200,stdin)==NULL)
			break;
		if(mixtitle[howtitle][strlen(mixtitle[howtitle])-1]=='n')
			mixtitle[howtitle][strlen(mixtitle[howtitle])-1]=0;
		ptr=0;
		for(i=0;i<strlen(mixtitle[howtitle]);i++)
		{
			if(mixtitle[howtitle][i]>=65&&mixtitle[howtitle][i]<=90)
			{
				title[howtitle][titleword[howtitle]][ptr]=mixtitle[howtitle][i]+32;
				ptr++;
			}
			else if(mixtitle[howtitle][i]>=97&&mixtitle[howtitle][i]<=122)
			{
				title[howtitle][titleword[howtitle]][ptr]=mixtitle[howtitle][i];
				ptr++;
			}
			else if(mixtitle[howtitle][i]==' ')
			{
				if(strcmp(title[howtitle][titleword[howtitle]],"")!=0)
				{
					title[howtitle][titleword[howtitle]][ptr]=0;
					titleword[howtitle]++;
					ptr=0;
				}
			}
			else if(mixtitle[howtitle][i]==0)
			{
				if(strcmp(title[howtitle][titleword[howtitle]],"")!=0)
				{
					title[howtitle][titleword[howtitle]][ptr]=0;
					titleword[howtitle]++;
					ptr=0;
				}
				break;
			}
		}
		if(strcmp(title[howtitle][titleword[howtitle]],"")!=0)
		{
			title[howtitle][titleword[howtitle]][ptr]=0;
			titleword[howtitle]++;
			ptr=0;
		}
		howtitle++;
	}
	for(i=0;i<howtitle;i++)
		for(j=0;j<strlen(mixtitle[i]);j++)
			if(mixtitle[i][j]>=65&&mixtitle[i][j]<=90)
				mixtitle[i][j]=mixtitle[i][j]+32;
	for(i=0;i<howtitle;i++)
	{
		for(j=0;j<titleword[i];j++)
		{
			result=0;
			yesno=0;
			for(k=0;k<howiword;k++)
			{
				if(strcmp(iword[k],title[i][j])==0)
					result=1;
			}
			if(result==0)
				yesno=1;
			if(yesno==1)
			{
				flag=0;
				flag1=0;
				strcpy(print[howprint],mixtitle[i]);
				for(k=0;k<strlen(mixtitle[i]);k++)
				{
					if(print[howprint][k]>=97&&print[howprint][k]<=122)
					{
						if(flag1==0)
						{
							flag++;
							flag1=1;
						}
					}
					else if(print[howprint][k]==' ')
						flag1=0;
					if(flag-1==j&&flag1==1)
						print[howprint][k]=print[howprint][k]-32;
				}
				howprint++;
			}
		}
	}
	qsort(print,howprint,sizeof(char)*101,sort);
	for(i=0;i<howprint;i++)
		printf("%sn",print[i]);
}

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

123 Searching Quickly

Post by C8H10N4O2 » Tue Apr 30, 2002 8:54 pm

Does anyone know of any special cases? My code works for the example case but gives me WA.
[cpp]
#pragma warning (disable:4786)
#include <cstdio>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <cctype>
#include <cstring>

using namespace std;

void main()
{
char B[1000],*P;
int i,j,k,N;
bool Duplicate;
vector<string> Ignore;
vector<string> Titles;
map<string,vector<int> > Index;
map<string,vector<int> >::iterator Idx;
string Title,Word,UWord;

do
{
scanf("%s",B);
for(i=0;i<strlen(B);i++)
{
B=tolower(B);
}
Ignore.push_back(B);
}
while(strcmp(B,"::")!=0);
Ignore.pop_back();

scanf("\n");
N=0;
while(fgets(B,1000,stdin)!=NULL)
{
for(i=0;i<strlen(B);i++)
{
B=tolower(B);
}
P=strchr(B,'\n');
if(P)
*P='\0';
Titles.push_back(B);

Title="";
P=strtok(B," ");
Duplicate=false;
while(P)
{
if(find(Ignore.begin(),Ignore.end(),P)==Ignore.end())
{
if(Title=="")
{
Title+=P;
}
else
{
Title+=" ";
Title+=P;
}
if(find(Index[P].begin(),Index[P].end(),N)==Index[P].end())
{
Index[P].push_back(N);
}
}

P=strtok(NULL," ");
}
N++;
}

for(Idx=Index.begin();Idx!=Index.end();Idx++)
{
for(i=0;i<(*Idx).second.size();i++)
{
k=-1;
Word=(*Idx).first;
UWord=Word;
Title=Titles[(*Idx).second];
for(j=0;j<Word.size();j++)
{
UWord[j]=toupper(UWord[j]);
}
while(true)
{
k=Title.find(Word,k+1);
if(k!=string::npos)
{
printf("%s",Title.substr(0,k).c_str());
printf("%s",UWord.c_str());
printf("%s\n",Title.substr(k+Word.size(),Title.size()-k-Word.size()).c_str());
}
else
{
break;
}
}
}
}
}[/cpp]

bodq
New poster
Posts: 2
Joined: Fri May 03, 2002 8:35 am
Location: Vinnitsya, Ukraine.
Contact:

Re: 123 Searching Quickly

Post by bodq » Mon May 06, 2002 6:12 pm

C8H10N4O2 wrote:Does anyone know of any special cases? My code works for the example case but gives me WA.
I guess I'll spoil you the fun if I'd tell you what exactly is wrong, so here is just the test case:
foo
::
o a foozoobar
have a nice day!

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

Post by C8H10N4O2 » Mon May 06, 2002 9:48 pm

Thanks, I will look into it:)

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

Post by Rossi » Sat Jun 15, 2002 7:48 pm

runtime error?????

[cpp]
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<ctype.h>

typedef struct{
int len;
char *main;
}TITLE;

int compstr(const void *a,const void *b)
{return strcmp((char *)a,(char *)b);}

int compptr(const void *a,const void *b)
{return strcmp(*(char **)a,*(char **)b);}

void print(char *,char *);
void strlower(char *);
int searchkey(char *);
char *instr(char *,char *);

int knum;
char keys[52][16];

int main(void)
{
register int i,j;
int tnum,rnum;
char str[16384],*p;
char *arr[3200];
TITLE ttl[210];

for(knum=0;;knum++){
gets(str);
p=strtok(str," \t");
strcpy(keys[knum],p);
if(strcmp(keys[knum],"::")==0)
break;
strlower(keys[knum]);
}

qsort((void *)keys,knum,sizeof(keys[0]),compstr);

for(tnum=rnum=0;;tnum++){
if(gets(str)==NULL)
break;

ttl[tnum].len=strlen(str);
ttl[tnum].main=new char[ttl[tnum].len+1];
strlower(str);
strcpy(ttl[tnum].main,str);

p=strtok(str," \t");
for(;p;){
if(searchkey(p)==0){
arr[rnum]=new char[strlen(p)+1];
strcpy(arr[rnum],p);
rnum++;
}
p=strtok(NULL," \t");
}
}

qsort((void *)arr,rnum,sizeof(char *),compptr);

for(i=0;i<rnum;i++){
for(j=0;j<tnum;j++){
if((p=instr(ttl[j].main,arr))!=NULL){
print(ttl[j].main,p);
break;
}
}
}

for(i=0;i<tnum;i++)
delete []ttl.main;

for(i=0;i<rnum;i++)
delete []arr;

return 0;
}

void strlower(char *str)
{
while(*str){
*str=tolower(*str);
str++;
}
}

int searchkey(char *key)
{
int res,left,right,mid;

left=0;
right=knum-1;
while(left<=right){
mid=(left+right)/2;
res=strcmp(key,keys[mid]);
if(res<0)
right=mid-1;
else if(res>0)
left=mid+1;
else
return 1;
}
return 0;
}

void print(char *in,char *p)
{
strlower(in);
while(!isspace(*p)){
*p=toupper(*p);
p++;
}
printf("%s\n",in);
}

char *instr(char *src,char *sub)
{
register int i,j;
int lsrc,lsub;

lsrc=strlen(src);
lsub=strlen(sub);

for(i=0;i<lsrc;i++){
if((i==0||isspace(src[i-1]))&&src==sub[0]){
for(j=1;j<lsub;j++){
if(src[j+i]!=sub[j])
break;
}
if(j==lsub&&(src[j+i]==NULL||isspace(src[j+i]))){
return ((char *)&src);
}
}
}

return NULL;
}[/cpp]

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

Post by C8H10N4O2 » Sun Jun 16, 2002 12:34 am

The runtime error is probably due to the gratuitous use of pointers... :wink: Try running through it with a debugger. There is probably an indexOutOfBounds exception somewhere.

Archangel
New poster
Posts: 29
Joined: Wed Jun 26, 2002 9:00 am

123 - Searching Quickly

Post by Archangel » Sun Jul 21, 2002 11:49 pm

Here is my algorithm:

Code: Select all

          0.three array: ignore,title,keyword(also store "the title it come from"and                                  "keyword position in the title").
          1.Read in words to ignore and stored them in a array(ignore).
          2.Read in titles, one word at a time to a string.(If read in a upper
             case letter, it will be changed to lower case and store to the  
             string).
          3.compare the string with the ignore word's array to check if it is an ignore or not. 
          4.If it's not a ignore word, copy the string to the keyword array and
             title array;if it's a ignore word, just copy the string to the title array.
          5.use bubble sort to sort the keyword array.
          6.print the result character by character using keyword array.
Anybody can give me a suggestion to improve my program? I got Time Limit Exceeded! :cry:

PMNOX
New poster
Posts: 49
Joined: Wed Feb 13, 2002 2:00 am
Location: Poland
Contact:

Post by PMNOX » Sat Dec 07, 2002 10:32 pm

you shouldn't use arrays, rb-trees are much faster.
And you should use quicksort instead of bubble sort .
Last edited by PMNOX on Sun Dec 08, 2002 11:00 am, edited 1 time in total.

Archangel
New poster
Posts: 29
Joined: Wed Jun 26, 2002 9:00 am

Post by Archangel » Sun Dec 08, 2002 7:40 am

Thanks for your great help! :D

PMNOX
New poster
Posts: 49
Joined: Wed Feb 13, 2002 2:00 am
Location: Poland
Contact:

Post by PMNOX » Sun Dec 08, 2002 11:02 am

to solve this problem I used stl (set), if you don't know it i can sent you a tutorial

route
New poster
Posts: 39
Joined: Sat Dec 21, 2002 1:25 am

123 input format

Post by route » Sat Jan 18, 2003 6:18 pm

how to determine the number of lines for one set of input? how to code for the inputs ?

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Sat Jan 18, 2003 6:23 pm

There is only one set of input

What do you mean how to code?

route
New poster
Posts: 39
Joined: Sat Dec 21, 2002 1:25 am

123 input format

Post by route » Sat Jan 18, 2003 6:29 pm

I mean.... for a normal question....
Input:
1 <--- 1st set of input
2 <----2nd set of input

We can code:
If it is not the end-of-file
read one set of input for one line.

But for problem 123, we cannot determine the lines for one set of inputs,

Input:
XXXX -
XXXX |-- how many lines ?
XXXX -

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Sat Jan 18, 2003 6:43 pm

All Title and key word is only on one line, I think

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

#123 - WA (122 strings of code)

Post by minskcity » Sat Mar 01, 2003 6:39 am

Can anybody test my code or give me test cases that are likely to result in WA with my code.

Or find any mistakes in my code. :o

My algorithm description:

1:Read titles, creating an array of indexing words at the same time.
2:Sort the array of indexing words.
3:Take indexing words one by one from sorted array, look for that word in titles, print a string of answer when found.

My code ( :roll: :roll: :roll: :roll: :roll: :roll: ) :-?
[cpp]#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <conio.h>

char buffer[300];
char ignore[50][20];
char index[500][100];
int ignore_num;
int index_num;

struct my_title{
char word[15][100];
int word_num;
};

my_title title[200];

int same(char in1[100], char in2[100]){
for(int i = 0; i < 100; i++){
if(in1 != in2) return 0;
if((in1 == 0) && (in2 == 0)) return 1;
}
return 1;
}

int in_ignore(char in[100]){
for(int i = 0; i < ignore_num; i++)
if(same(in,ignore)) return 1;
return 0;
}

int in_index(char in[100]){
for(int i = 0; i < index_num; i++)
if(same(in,index)) return 1;
return 0;
}

int fcmp(const void *in1,const void *in2){
for(int i = 0; i < 100; i++){
if(((char *)in1) < ((char *)in2)) return -1;
if(((char *)in1) > ((char *)in2)) return 1;
if(!((char *)in1)[i]) return 0;
}
return 0;
}

void print_as_answer(int tn, int ind){
int j;
for(int i = 0; i < title[tn].word_num; i++){
if(ind == i){
for(j = 0; title[tn].word[i][j]; j++)
cout << char(title[tn].word[i][j] - 32);
} else cout << title[tn].word[i];
if(i != title[tn].word_num) cout << " ";
}
cout << "\n";
}

int main(){
ignore_num = 0;
index_num = 0;
cin >> ignore[ignore_num];
while(ignore[ignore_num][0] != ':'){
ignore_num++;
cin >> ignore[ignore_num];
}

int title_num = 0;
int kk = 0;
int bk;
while(gets(buffer)){
if(!buffer[0]) break;
for(int i = 0; buffer[i]; i++)
if(isalpha(buffer[i]))
if(!islower(buffer[i])) buffer[i] += 32;
bk = 0;
while(1){
if(buffer[bk] == ' '){
title[title_num].word[title[title_num].word_num][kk] = 0;
if(!in_ignore(title[title_num].word[title[title_num].word_num]))
if(!in_index(title[title_num].word[title[title_num].word_num])){
for(int i = 0; i <= kk; i++)
index[index_num][i] = title[title_num].word[title[title_num].word_num][i];
index_num++;
}
title[title_num].word_num++;
kk = 0;
bk++;
continue;
}
if(!buffer[bk]){
title[title_num].word[title[title_num].word_num][kk] = 0;
if(!in_ignore(title[title_num].word[title[title_num].word_num]))
if(!in_index(title[title_num].word[title[title_num].word_num])){
for(int i = 0; i <= kk; i++)
index[index_num][i] = title[title_num].word[title[title_num].word_num][i];
index_num++;
}
title[title_num].word_num++;
kk = 0;
break;
}
title[title_num].word[title[title_num].word_num][kk] = buffer[bk];
kk++;
bk++;
}
title_num++;
}

qsort(&index,index_num,100,&fcmp);

for(int i = 0; i < index_num; i++)
for(int j = 0; j < title_num; j++)
for(int k = 0; k < title[j].word_num; k++)
if(same(index[i],title[j].word[k]))
print_as_answer(j,k);

getch();
return 0;
}[/cpp]
I know it's too long. :(

Post Reply

Return to “Volume 1 (100-199)”