123 Searching Quickly

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

Moderator: Board moderators

123 Searching Quickly

Postby 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[i]=tolower(B[i]);
}
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[i]=tolower(B[i]);
}
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[i]];
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]
C8H10N4O2
Experienced poster
 
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

Re: 123 Searching Quickly

Postby 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!
bodq
New poster
 
Posts: 2
Joined: Fri May 03, 2002 8:35 am
Location: Vinnitsya, Ukraine.

Postby C8H10N4O2 » Mon May 06, 2002 9:48 pm

Thanks, I will look into it:)
C8H10N4O2
Experienced poster
 
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

Postby 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[i]))!=NULL){
print(ttl[j].main,p);
break;
}
}
}

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

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

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[i]==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[i]);
}
}
}

return NULL;
}[/cpp]
Rossi
New poster
 
Posts: 20
Joined: Thu Mar 21, 2002 2:00 am
Location: Bangladesh

Postby 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.
C8H10N4O2
Experienced poster
 
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

Re: 123 Searching Quickly

Postby sefakilic » Thu Aug 06, 2009 5:45 pm

Hello, I am getting WA for the problem.
Here is my code, i can't find the error.

Code: Select all
#include <iostream>
#include <string>
#include <algorithm>
#include <sstream>
#include <vector>
using namespace std;
string ignores[50];
string titles[200];
struct x {
    string potential;
    int index;
    int indexintitle;
};
vector<struct x> potentials;
vector<string> titlewords;

string toLower(string x)
{
    // assuming string x contains only [A-Z] and [a-z]
    int len = x.length();
    for(int i = 0; i < len; ++i)
    {
        if(x[i] >= 'A' && x[i] <= 'Z')
            x[i] = x[i] + 32;
    }
    return x;
}

string toUpper(string x)
{
    // assuming string x contains only [A-Z] and [a-z]
    int len = x.length();
    for(int i = 0; i < len; ++i)
    {
        if(x[i] >= 'a' && x[i] <= 'z')
            x[i] = x[i] - 32;
    }
    return x;
}


bool cmp (struct x a, struct x b)
{
    if(toLower(a.potential) != toLower(b.potential))
        return (toLower(a.potential) < toLower(b.potential));
    else return (a.index < b.index);
}
int main()
{
    string tmp;
    int numberignores = 0;
    int numbertitles = 0;
    stringstream ss;
   
    while(cin >> tmp)
    {
        if(tmp == "::") break;
        else ignores[numberignores++] = tmp;
    }
    sort(ignores, ignores + numberignores);
    while(getline(cin, tmp))
    {
        if(tmp.length() == 0) continue;
        titles[numbertitles++] = tmp;
    }
    potentials.clear();
    for(int i = 0; i < numbertitles; ++i)
    {
        //cout << "|" << titles[i] << "|" << endl;
        titlewords.clear();
        ss.clear();
        ss.str(titles[i]);
        while(ss >> tmp)
            titlewords.push_back(tmp);

        for(vector<string>::iterator it = titlewords.begin(); it != titlewords.end(); ++it)
        {
            //cout << "x: " << *it << " " << toLower(*it) << endl;
            if(binary_search(ignores, ignores + numberignores, toLower(*it)) == false)
            {
                //cout << "potential: " << *it << endl;
                struct x tmpx;
                tmpx.potential = *it;
                tmpx.index     = i;
                tmpx.indexintitle = it - titlewords.begin();
                potentials.push_back(tmpx);
            }
        }
       
    }
    sort(potentials.begin(), potentials.end(), cmp);
   
    for(vector<struct x>::iterator it = potentials.begin(); it != potentials.end(); ++it)
    {
        struct x tmpx = *it;
        ss.clear();
        ss.str(titles[tmpx.index]);
        bool first = true;
        int wordcount  = 0;
        while(ss >> tmp)
        {
            wordcount += 1;
            if(first) { first = false; }
            else cout << " ";
            if(tmp == tmpx.potential && tmpx.indexintitle + 1 == wordcount) cout << toUpper(tmp);
            else cout << toLower(tmp);
        }
        cout << endl;
    }
   
    return 0;
}
   
sefakilic
New poster
 
Posts: 7
Joined: Wed Mar 11, 2009 8:12 pm

Re: 123 Searching Quickly

Postby Sedefcho » Wed Aug 12, 2009 10:47 pm

Here is a wikipedia article which was changed a little
bit in order to match this problem's requirements.

INPUT
Code: Select all
the
for
on
in
and
is
it
american
canadian
great
lakes
::
The Niagara Falls are voluminous waterfalls on the Niagara River
straddling the international border between the Canadian province
of Ontario and the U S  state of New York  The falls are
N miles BBBBBBSSSM kmBBBBBBSSS north northwest of Buffalo New York and
S miles BBBBBBSSSZ kmBBBBBBSSS south southeast of Toronto Ontario
between the twin cities of Niagara Falls Ontario
and Niagara Falls New York  Niagara Falls is composed
of two major sections separated by Goat Island:
Horseshoe Falls the majority of which lies on the
Canadian side of the border and American Falls on the
American side  The smaller Bridal Veil Falls are also
located on the American side separated from the main falls
by Luna Island  Niagara Falls were formed when glaciers
receded at the end of the Wisconsin glaciation BBBBBBSSSthe last ice ageBBBBBBSSS
and water from the newly formed Great Lakes carved a path through
the Niagara Escarpment en route to the Atlantic Ocean
While not exceptionally high the Niagara Falls are very wide
More than six million cubic feet BBBBBBSSSXYZKLM mSBBBBBBSSS of water falls
over the crest line every minute in high flow and almost
F million cubic feet BBBBBBSSSXYZKLM mSBBBBBBSSS on average  It is the most
powerful waterfall in North America

The Niagara Falls are renowned both for their beauty and
as a valuable source of hydroelectric power  Managing the
balance between recreational commercial and industrial uses
has been a challenge for the stewards of the falls since the TKLMs



OUTPUT
Code: Select all
and water from the newly formed great lakes carved A path through
as A valuable source of hydroelectric power  managing the
has been A challenge for the stewards of the falls since the tklms
receded at the end of the wisconsin glaciation bbbbbbsssthe last ice AGEBBBBBBSSS
over the crest line every minute in high flow and ALMOST
american side  the smaller bridal veil falls are ALSO
powerful waterfall in north AMERICA
the niagara falls ARE voluminous waterfalls on the niagara river
of ontario and the u s  state of new york  the falls ARE
american side  the smaller bridal veil falls ARE also
while not exceptionally high the niagara falls ARE very wide
the niagara falls ARE renowned both for their beauty and
AS a valuable source of hydroelectric power  managing the
receded AT the end of the wisconsin glaciation bbbbbbsssthe last ice agebbbbbbsss
the niagara escarpment en route to the ATLANTIC ocean
f million cubic feet bbbbbbsssxyzklm msbbbbbbsss on AVERAGE  it is the most
BALANCE between recreational commercial and industrial uses
n miles BBBBBBSSSM kmbbbbbbsss north northwest of buffalo new york and
receded at the end of the wisconsin glaciation BBBBBBSSSTHE last ice agebbbbbbsss
more than six million cubic feet BBBBBBSSSXYZKLM msbbbbbbsss of water falls
f million cubic feet BBBBBBSSSXYZKLM msbbbbbbsss on average  it is the most
s miles BBBBBBSSSZ kmbbbbbbsss south southeast of toronto ontario
the niagara falls are renowned both for their BEAUTY and
has BEEN a challenge for the stewards of the falls since the tklms
straddling the international border BETWEEN the canadian province
BETWEEN the twin cities of niagara falls ontario
balance BETWEEN recreational commercial and industrial uses
straddling the international BORDER between the canadian province
canadian side of the BORDER and american falls on the
the niagara falls are renowned BOTH for their beauty and
american side  the smaller BRIDAL veil falls are also
n miles bbbbbbsssm kmbbbbbbsss north northwest of BUFFALO new york and
of two major sections separated BY goat island:
BY luna island  niagara falls were formed when glaciers
and water from the newly formed great lakes CARVED a path through
has been a CHALLENGE for the stewards of the falls since the tklms
between the twin CITIES of niagara falls ontario
balance between recreational COMMERCIAL and industrial uses
and niagara falls new york  niagara falls is COMPOSED
over the CREST line every minute in high flow and almost
more than six million CUBIC feet bbbbbbsssxyzklm msbbbbbbsss of water falls
f million CUBIC feet bbbbbbsssxyzklm msbbbbbbsss on average  it is the most
the niagara escarpment EN route to the atlantic ocean
receded at the END of the wisconsin glaciation bbbbbbsssthe last ice agebbbbbbsss
the niagara ESCARPMENT en route to the atlantic ocean
over the crest line EVERY minute in high flow and almost
while not EXCEPTIONALLY high the niagara falls are very wide
F million cubic feet bbbbbbsssxyzklm msbbbbbbsss on average  it is the most
the niagara FALLS are voluminous waterfalls on the niagara river
of ontario and the u s  state of new york  the FALLS are
between the twin cities of niagara FALLS ontario
and niagara FALLS new york  niagara falls is composed
and niagara falls new york  niagara FALLS is composed
horseshoe FALLS the majority of which lies on the
canadian side of the border and american FALLS on the
american side  the smaller bridal veil FALLS are also
located on the american side separated from the main FALLS
by luna island  niagara FALLS were formed when glaciers
while not exceptionally high the niagara FALLS are very wide
more than six million cubic feet bbbbbbsssxyzklm msbbbbbbsss of water FALLS
the niagara FALLS are renowned both for their beauty and
has been a challenge for the stewards of the FALLS since the tklms
more than six million cubic FEET bbbbbbsssxyzklm msbbbbbbsss of water falls
f million cubic FEET bbbbbbsssxyzklm msbbbbbbsss on average  it is the most
over the crest line every minute in high FLOW and almost
by luna island  niagara falls were FORMED when glaciers
and water from the newly FORMED great lakes carved a path through
located on the american side separated FROM the main falls
and water FROM the newly formed great lakes carved a path through
receded at the end of the wisconsin GLACIATION bbbbbbsssthe last ice agebbbbbbsss
by luna island  niagara falls were formed when GLACIERS
of two major sections separated by GOAT island:
HAS been a challenge for the stewards of the falls since the tklms
while not exceptionally HIGH the niagara falls are very wide
over the crest line every minute in HIGH flow and almost
HORSESHOE falls the majority of which lies on the
as a valuable source of HYDROELECTRIC power  managing the
receded at the end of the wisconsin glaciation bbbbbbsssthe last ICE agebbbbbbsss
balance between recreational commercial and INDUSTRIAL uses
straddling the INTERNATIONAL border between the canadian province
by luna ISLAND  niagara falls were formed when glaciers
of two major sections separated by goat ISLAND:
n miles bbbbbbsssm KMBBBBBBSSS north northwest of buffalo new york and
s miles bbbbbbsssz KMBBBBBBSSS south southeast of toronto ontario
receded at the end of the wisconsin glaciation bbbbbbsssthe LAST ice agebbbbbbsss
horseshoe falls the majority of which LIES on the
over the crest LINE every minute in high flow and almost
LOCATED on the american side separated from the main falls
by LUNA island  niagara falls were formed when glaciers
located on the american side separated from the MAIN falls
of two MAJOR sections separated by goat island:
horseshoe falls the MAJORITY of which lies on the
as a valuable source of hydroelectric power  MANAGING the
n MILES bbbbbbsssm kmbbbbbbsss north northwest of buffalo new york and
s MILES bbbbbbsssz kmbbbbbbsss south southeast of toronto ontario
more than six MILLION cubic feet bbbbbbsssxyzklm msbbbbbbsss of water falls
f MILLION cubic feet bbbbbbsssxyzklm msbbbbbbsss on average  it is the most
over the crest line every MINUTE in high flow and almost
MORE than six million cubic feet bbbbbbsssxyzklm msbbbbbbsss of water falls
f million cubic feet bbbbbbsssxyzklm msbbbbbbsss on average  it is the MOST
more than six million cubic feet bbbbbbsssxyzklm MSBBBBBBSSS of water falls
f million cubic feet bbbbbbsssxyzklm MSBBBBBBSSS on average  it is the most
N miles bbbbbbsssm kmbbbbbbsss north northwest of buffalo new york and
of ontario and the u s  state of NEW york  the falls are
n miles bbbbbbsssm kmbbbbbbsss north northwest of buffalo NEW york and
and niagara falls NEW york  niagara falls is composed
and water from the NEWLY formed great lakes carved a path through
the NIAGARA falls are voluminous waterfalls on the niagara river
the niagara falls are voluminous waterfalls on the NIAGARA river
between the twin cities of NIAGARA falls ontario
and NIAGARA falls new york  niagara falls is composed
and niagara falls new york  NIAGARA falls is composed
by luna island  NIAGARA falls were formed when glaciers
the NIAGARA escarpment en route to the atlantic ocean
while not exceptionally high the NIAGARA falls are very wide
the NIAGARA falls are renowned both for their beauty and
n miles bbbbbbsssm kmbbbbbbsss NORTH northwest of buffalo new york and
powerful waterfall in NORTH america
n miles bbbbbbsssm kmbbbbbbsss north NORTHWEST of buffalo new york and
while NOT exceptionally high the niagara falls are very wide
the niagara escarpment en route to the atlantic OCEAN
OF ontario and the u s  state of new york  the falls are
of ontario and the u s  state OF new york  the falls are
n miles bbbbbbsssm kmbbbbbbsss north northwest OF buffalo new york and
s miles bbbbbbsssz kmbbbbbbsss south southeast OF toronto ontario
between the twin cities OF niagara falls ontario
OF two major sections separated by goat island:
horseshoe falls the majority OF which lies on the
canadian side OF the border and american falls on the
receded at the end OF the wisconsin glaciation bbbbbbsssthe last ice agebbbbbbsss
more than six million cubic feet bbbbbbsssxyzklm msbbbbbbsss OF water falls
as a valuable source OF hydroelectric power  managing the
has been a challenge for the stewards OF the falls since the tklms
of ONTARIO and the u s  state of new york  the falls are
s miles bbbbbbsssz kmbbbbbbsss south southeast of toronto ONTARIO
between the twin cities of niagara falls ONTARIO
OVER the crest line every minute in high flow and almost
and water from the newly formed great lakes carved a PATH through
as a valuable source of hydroelectric POWER  managing the
POWERFUL waterfall in north america
straddling the international border between the canadian PROVINCE
RECEDED at the end of the wisconsin glaciation bbbbbbsssthe last ice agebbbbbbsss
balance between RECREATIONAL commercial and industrial uses
the niagara falls are RENOWNED both for their beauty and
the niagara falls are voluminous waterfalls on the niagara RIVER
the niagara escarpment en ROUTE to the atlantic ocean
of ontario and the u S  state of new york  the falls are
S miles bbbbbbsssz kmbbbbbbsss south southeast of toronto ontario
of two major SECTIONS separated by goat island:
of two major sections SEPARATED by goat island:
located on the american side SEPARATED from the main falls
canadian SIDE of the border and american falls on the
american SIDE  the smaller bridal veil falls are also
located on the american SIDE separated from the main falls
has been a challenge for the stewards of the falls SINCE the tklms
more than SIX million cubic feet bbbbbbsssxyzklm msbbbbbbsss of water falls
american side  the SMALLER bridal veil falls are also
as a valuable SOURCE of hydroelectric power  managing the
s miles bbbbbbsssz kmbbbbbbsss SOUTH southeast of toronto ontario
s miles bbbbbbsssz kmbbbbbbsss south SOUTHEAST of toronto ontario
of ontario and the u s  STATE of new york  the falls are
has been a challenge for the STEWARDS of the falls since the tklms
STRADDLING the international border between the canadian province
more THAN six million cubic feet bbbbbbsssxyzklm msbbbbbbsss of water falls
the niagara falls are renowned both for THEIR beauty and
and water from the newly formed great lakes carved a path THROUGH
has been a challenge for the stewards of the falls since the TKLMS
the niagara escarpment en route TO the atlantic ocean
s miles bbbbbbsssz kmbbbbbbsss south southeast of TORONTO ontario
between the TWIN cities of niagara falls ontario
of TWO major sections separated by goat island:
of ontario and the U s  state of new york  the falls are
balance between recreational commercial and industrial USES
as a VALUABLE source of hydroelectric power  managing the
american side  the smaller bridal VEIL falls are also
while not exceptionally high the niagara falls are VERY wide
the niagara falls are VOLUMINOUS waterfalls on the niagara river
and WATER from the newly formed great lakes carved a path through
more than six million cubic feet bbbbbbsssxyzklm msbbbbbbsss of WATER falls
powerful WATERFALL in north america
the niagara falls are voluminous WATERFALLS on the niagara river
by luna island  niagara falls WERE formed when glaciers
by luna island  niagara falls were formed WHEN glaciers
horseshoe falls the majority of WHICH lies on the
WHILE not exceptionally high the niagara falls are very wide
while not exceptionally high the niagara falls are very WIDE
receded at the end of the WISCONSIN glaciation bbbbbbsssthe last ice agebbbbbbsss
of ontario and the u s  state of new YORK  the falls are
n miles bbbbbbsssm kmbbbbbbsss north northwest of buffalo new YORK and
and niagara falls new YORK  niagara falls is composed
User avatar
Sedefcho
A great helper
 
Posts: 375
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Re: 123 Searching Quickly

Postby at5anpo3 » Thu May 10, 2012 2:44 pm

The example above should be missing ":" from
Code: Select all
by Goat Island:


The output file MUST end with a \n, or else you fail the judge! (had to find it the hard way).

Best Regards,
at5anpo3
at5anpo3
New poster
 
Posts: 7
Joined: Sun Apr 29, 2012 6:46 pm


Return to Volume I

Who is online

Users browsing this forum: Google [Bot] and 2 guests