10352 - Count the eWords

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

Moderator: Board moderators

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

10352 - Count the eWords

Post by Adrian Kuegel » Wed Aug 28, 2002 10:21 pm

Can someone please give me the correct output for:
abc ab abcd abe abd #

Helal Md. Morshed Alam
New poster
Posts: 4
Joined: Fri Oct 19, 2001 2:00 am
Location: AIUB, BANGLADESH
Contact:

[b]May Be This Is The Output:[/b]

Post by Helal Md. Morshed Alam » Wed Aug 28, 2002 11:00 pm

ab 1
abd 3
abcd 1

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Thu Aug 29, 2002 2:21 am

Thank you. My program produces now the same output, but I always get WA. Can there be difficulties when reading the input? Because the processing should work, I have tested it very long. Or is there a special case?

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

Post by Dominik Michniewski » Thu Aug 29, 2002 8:04 am

I have the same problem like Adrian ....
I think, I miss something ...
I try to found special test cases ! Could anyone help us ?

Dominik

AlexandreN
New poster
Posts: 27
Joined: Sun Jul 07, 2002 6:46 pm
Location: Campina Grande - Brazil
Contact:

Post by AlexandreN » Thu Aug 29, 2002 1:18 pm

There is no especial cases.
There is no input problems, I use a array of size 30 to store each word in the input.

There is a statement in the problem that may be confuse.

"The lines are ordered in ascending (ASCII) order of the words. The 'ignored' (i.e. the 3rd) letter in the word should show the last 'ignored' letter. However, the sorting should be according to the first 'ignored' letter. For Example if the email contains the line

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Thu Aug 29, 2002 1:28 pm

Thank you very much, that was the problem. But what a bad problem description!

hongping
New poster
Posts: 11
Joined: Fri Jul 26, 2002 5:43 pm

WA...

Post by hongping » Sat Aug 31, 2002 3:37 am

I didnt use strcmp, just replaced all 3rd character with ~, and then use string operator >


wonder whats wrong, please help.









[cpp]



/* @JUDGE_ID: 3162CM 10352 C++ */













#include <stdio.h>






#include <string>






#include <map>






#include <iostream.h>






#include <stdlib.h>






#include <math.h>






#include <vector>






#include <algorithm>













using namespace std;













int n;






struct wtype{






string s,f;






int c;






};






void main (void)






{






string s;






int xxx=0;






while (cin >> s)






{






xxx++;






cout << "Set #" << xxx << endl;






map<string, wtype> a;






vector<wtype> b;






map<string, wtype>::iterator it;






while(s!="#")






{






char cs[200];






if (s.size()>5)s=s.substr(0,5);






string x=s;






if (x.size()>2)x[2]='~';






it=a.find(x);






if (it==a.end())






{






wtype w;






w.s = s;






w.c = 1;






w.f = x;






a.insert(make_pair(x,w));






} else{






(*it).second.s = s;






(*it).second.c ++;






}






cin>>s;






}






int i,j;






for (it=a.begin();it!=a.end();it++)






b.push_back((*it).second);













for (i=0;i<b.size();i++)






for (j=i+1;j<b.size();j++)






if (b.f>b[j].f)






{






swap (b, b[j]);






}






for (i=0;i<b.size();i++)






cout << b.s << " " << b.c << endl;






cout << endl;













}






}



[/cpp]

dwyak
New poster
Posts: 36
Joined: Sun Jul 28, 2002 5:16 am
Location: P.R.China
Contact:

Post by dwyak » Sat Aug 31, 2002 6:26 am

Is there a special case which has more than 4100 distinct words?
I've tested. I found it exists. But I'm not sure I tested correctly.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sat Aug 31, 2002 1:09 pm

I have also tested it, there is no such case. There is no special input (all words contain only characters where isgraph(c) returns true). There must be something wrong with your program.

dwyak
New poster
Posts: 36
Joined: Sun Jul 28, 2002 5:16 am
Location: P.R.China
Contact:

Post by dwyak » Mon Sep 02, 2002 7:10 pm

I still cannot understand what does this sentence mean.
However, the sorting should be according to the first 'ignored' letter

If there's a case,
abcde abddef aabaab aaaaaa #

What should I output?

thx...

AlexandreN
New poster
Posts: 27
Joined: Sun Jul 07, 2002 6:46 pm
Location: Campina Grande - Brazil
Contact:

Post by AlexandreN » Tue Sep 03, 2002 5:36 pm

Ignore it and ignore the 3rd letter when sorting.

Input:
abcde abddef aabaab aaaaaa #
Output:
Set #1:
aaaaa 2
abdde 2

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

Post by Dominik Michniewski » Wed Sep 04, 2002 8:16 am

Thanks for hints :-)))
I finally got Accepted too :-)
But I think, that I still can use strcmp() if I use struct like this

Code: Select all

typedef struct { char word[10]; char last; } WORD;
and set third letter to i.e. space ...

Greetings

dwyak
New poster
Posts: 36
Joined: Sun Jul 28, 2002 5:16 am
Location: P.R.China
Contact:

Post by dwyak » Wed Sep 04, 2002 8:16 am

I understand and get AC now. Thank you very much.
Wenyuan Dai, Shanghai Jiaotong University.

Eric3k
New poster
Posts: 29
Joined: Mon Apr 29, 2002 5:22 pm
Contact:

Post by Eric3k » Wed Sep 18, 2002 3:33 am

Hi,
I'm having problems understanding why my program won't run under 30 seconds under the same problem. Perhaps it's my input that doesn't end while (cin>>str). Could anyone please tell me if they find any problem or bad design. Thanks a lot.

[cpp]#include <iostream>
#include <list>
#include <string>
//#include <fstream>

using namespace std;
class wo{
public:
string str;
char let;
int amt;

};

void main(){


//ifstream in("in.txt");
//ofstream out("out.txt");


wo word;
string str;
list<wo>email;
int set=1;
while ((cin>>str){

if (str!="#"){ //old email
if (str.length()>5)str=str.substr(0,5);
word.let='#';
if (str.length()>=3){
word.let=str[2];
str[2]='#';
}
word.str=str;
word.amt=1;
list<wo>::iterator i=email.begin();
while (i!=email.end()){
if ((*i).str==str){
(*i).amt++;
(*i).let=word.let;
break;
}
else if ((*i).str>str){
email.insert(i,word);
break;
}
else i++;
}
if (i==email.end())email.push_back(word);
}
else {//new email found
if (set>1)cout<<endl;
cout<<"Set #"<<set<<":\n";
list<wo>::iterator i=email.begin();
while (i!=email.end()){
if ((*i).let!='#')(*i).str[2]=(*i).let;
cout<<(*i).str<<" "<<(*i).amt<<endl;
i++;
}
set++;
email.clear();

}

}

}
[/cpp][/cpp]

Picard
Learning poster
Posts: 96
Joined: Mon Jun 24, 2002 1:22 pm
Location: Hungary
Contact:

Post by Picard » Wed Sep 18, 2002 7:51 am

Eric3k: you shouldn't use linear search finding a word. use vector<> and binary search, or use map<string,wo>. btw you should print a blank line after every email (else you'll get PE). instead of "(*i)." you can use "i->" (it's just more readable)

Post Reply

Return to “Volume 103 (10300-10399)”