Page 1 of 4

Posted: Mon Mar 25, 2002 4:59 am
by FlyDeath
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]);
}

123 Searching Quickly

Posted: Tue Apr 30, 2002 8:54 pm
by C8H10N4O2
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]

Re: 123 Searching Quickly

Posted: Mon May 06, 2002 6:12 pm
by bodq
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!

Posted: Mon May 06, 2002 9:48 pm
by C8H10N4O2
Thanks, I will look into it:)

Posted: Sat Jun 15, 2002 7:48 pm
by Rossi
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]

Posted: Sun Jun 16, 2002 12:34 am
by C8H10N4O2
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.

123 - Searching Quickly

Posted: Sun Jul 21, 2002 11:49 pm
by Archangel
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:

Posted: Sat Dec 07, 2002 10:32 pm
by PMNOX
you shouldn't use arrays, rb-trees are much faster.
And you should use quicksort instead of bubble sort .

Posted: Sun Dec 08, 2002 7:40 am
by Archangel
Thanks for your great help! :D

Posted: Sun Dec 08, 2002 11:02 am
by PMNOX
to solve this problem I used stl (set), if you don't know it i can sent you a tutorial

123 input format

Posted: Sat Jan 18, 2003 6:18 pm
by route
how to determine the number of lines for one set of input? how to code for the inputs ?

Posted: Sat Jan 18, 2003 6:23 pm
by yiuyuho
There is only one set of input

What do you mean how to code?

123 input format

Posted: Sat Jan 18, 2003 6:29 pm
by route
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 -

Posted: Sat Jan 18, 2003 6:43 pm
by yiuyuho
All Title and key word is only on one line, I think

#123 - WA (122 strings of code)

Posted: Sat Mar 01, 2003 6:39 am
by minskcity
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. :(