10815 - Andy's First Dictionary

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

Moderator: Board moderators

Sanny
Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET
Contact:

10815 - Andy's First Dictionary

Post by Sanny » Thu Jun 16, 2005 5:50 pm

Problem description says that number of distinct words will be less than 5000. But you're assuming total number of words to be less than 5000.

watershed
New poster
Posts: 13
Joined: Thu Aug 05, 2004 9:14 am

10815 wrong

Post by watershed » Sun Jul 17, 2005 4:03 pm

Who can help me solve this problem, thanks~

Code: Select all

#include<iostream>
#include<string>
#include<set>
using namespace std;
main()
{
	set<string> words;
	string buffer="", word="";
	while( cin >> buffer ) {
		int len = buffer.length();
		for(int i=0; i<=len; ++i) {
			if( buffer[i] >= 'A' && buffer[i] <= 'Z' )
					word+=tolower(buffer[i]);
			else if( buffer[i] >= 'a' && buffer[i] <= 'z' )
					word+=buffer[i];
			else if( word != "" ) {
					words.insert(word);
					word="";
			}
		}			
	}
	set<string>::iterator p;
	for(p=words.begin(); p!=words.end(); ++p)
		cout << *p << endl;
}

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: 10815 wrong

Post by Martin Macko » Fri Jul 29, 2005 7:51 am

watershed wrote:

Code: Select all

		int len = buffer.length();
		for(int i=0; i<=len; ++i) {
Shouldn't it be i < len ?

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

I got WA too :'(

Post by FAQ » Sun Jul 31, 2005 3:07 am

Code: Select all

ACed
Last edited by FAQ on Sun Aug 14, 2005 4:06 pm, edited 3 times in total.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: I got WA too :'(

Post by Martin Macko » Sun Jul 31, 2005 4:17 pm

Have you tried any really huge input? What about 5000 random words of length something about 200 chars?

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

Post by FAQ » Sun Jul 31, 2005 5:12 pm

Yes, I have tried an input with 5000 lines, and string[200] 'aaaaa..a' for each line, and it runs well

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Mon Aug 01, 2005 6:48 am

FAQ wrote:Yes, I have tried an input with 5000 lines, and string[200] 'aaaaa..a' for each line, and it runs well
Just try random strings. But do not forget to check you are not using more that 32MB ram, eg. by ulimit if you are using linux.

User avatar
_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

Limits. Re: I got WA too :'(

Post by _.B._ » Thu Aug 04, 2005 11:41 pm

Greetings FAQ!
For this problem I considered all words to be <= than 200 chars long, and no more than 50000 words in Andy's Dictionary (maybe a lot less than that would work).
Quick Sort did the work, and just don't print the repeated words.
Remember all words must be lowercase.
Ah!, and either tokenize lines, or build words char-by-char.

Hope it helps.
_.

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

ACed :)

Post by FAQ » Sun Aug 14, 2005 4:04 pm

Thanks a lot Martin, _.B._. I got AC now

User avatar
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

10815 RUNTIME ERROR!

Post by smilitude » Fri Oct 07, 2005 7:27 pm

Grrr....

runtime error!

Code: Select all

/*
10815 - andy's first dictionary
submission 1 runtime error!  2 output limit exceeded!
coded at 4:42 on 6th oct 05
*/

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


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

int main() {
	//declaration 
	char line[205];
	char words[5005][205];
	char current_word[205];
	int i,j,len,k;
	int total=0;

    while(1){
	//input taking 
	while(gets(line)!=NULL) {
		len=strlen(line);
	//choosing word - lowering and then saving them
		for(i=0;i<len;i++) {
			j=0;
			while(isalpha(line[i])) {
				current_word[j]=line[i];
				j++;i++;
			}

			current_word[j]=NULL;
			for(k=0;k<j;k++) 
				current_word[k]=tolower(current_word[k]);
            for(j=0;j<total;j++)
                if(strcmp(current_word,words[j])==0)break;
            if(j==total)
                strcpy(words[total++],current_word);
		}
	}
	

	//sorting the whole dictionary
		qsort(words,total,sizeof(words[0]),sort_function);

	//output routine
		for(i=1;i<total;i++) {
			//if(strcmp(words[i]," "));			
           if(words[i][0]!=' ')
            printf("%s\n",words[i]);
		}
}		
		return 0;
}
		
	
Last edited by smilitude on Wed Oct 12, 2005 2:44 am, edited 1 time in total.
fahim
#include <smile.h>

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET

Post by sunny » Tue Oct 11, 2005 11:53 pm

fahim
i didn't read your code fully. in this problem you should make your arraysize for the words much bigger. There are 5000 distinct words. but
more than 5000 words which are same to any others. one other thing you should declare large arrays globally unless there's a chance for RTE.

User avatar
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Post by smilitude » Wed Oct 12, 2005 2:46 am

code edited....
now what's wrong?

here it checks every single new word, whether they are really new or not
fahim
#include <smile.h>

jjtse
Learning poster
Posts: 80
Joined: Mon Aug 22, 2005 7:32 pm
Location: Nevada, US
Contact:

10815 Presentation Error (PE)

Post by jjtse » Fri Dec 09, 2005 11:54 pm

Hey fellas,

I've been working on this problem for a while now. Finally got it to work correctly. The only problem now is that it's getting a presentation error. I bet it's something trivial, it's just that I can't see it. I tried putting/removing the newline at the end of the output file. That didn't make a difference. Can someone run this on their machine with the correct version of the compiler and let me know where I presented my data wrong? Thanks. This is what I have:

Code: Select all


code removed...
Last edited by jjtse on Sun Dec 11, 2005 11:19 am, edited 1 time in total.

jjtse
Learning poster
Posts: 80
Joined: Mon Aug 22, 2005 7:32 pm
Location: Nevada, US
Contact:

Post by jjtse » Sat Dec 10, 2005 9:21 am

does anyone know what was wrong with watershed's code? Apparently, I'm having the same problem he used to have. I compared the output produce by my codes with the output produced by his codes, and it looks exactly the same. Mine, however, has presentation error instead of wrong answer, and I can't see where I'm presenting it wrong.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: 10815 Presentation Error (PE)

Post by Martin Macko » Sat Dec 10, 2005 3:48 pm

jjtse wrote:

Code: Select all

  while (!cin.eof()){
    s = "";
    while (isalpha(c)){
      s.push_back(c);
      if (cin.eof())
        break;
      c=cin.get();
    }
    insert(s);
If the input begins with a non-alpha character your output contains the empty word "".

Post Reply

Return to “Volume 108 (10800-10899)”