698 - Index

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

Moderator: Board moderators

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am

698 - Index

Post by wyvmak » Thu Apr 11, 2002 10:00 am

:evil: I just hate it when I knew the sample output is wrong. If sample output is wrong, what is its purpose? or in the real ACM, wrong sample output is part of the test for competitors? Yet, I still cannot get AC.

would someone be kind enough to give me the output for the following input:

abc
def

abc abc def
abc abc def def
abc abc def def def
abc

would it be:
Case 1
ABC 1, 1-2, 2-3, 3-4
DEF 1-2, 2-3, 3, 3

Also, will there be a case that there's zero word to be indexed?
Or what other tricks in it?

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

Post by Adrian Kuegel » Thu Apr 11, 2002 12:54 pm

I would say, the output is
Case 1
ABC 1-4
DEF 1-3
but I also get WA. What is the correct output for this input?
2fOr1
.*the+
bla

blab the+ h2for1
2for1z 2for1 *the bla
blabla the

My program prints:
Case 1
2FOR1 2
BLA 2
THE 1-3

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by Ivan Golubev » Thu Apr 11, 2002 2:51 pm

My accepted solution produces this output:

For wyvmak's input:
Case 1
ABC 4
DEF 1-3

For Adrian's input:
Case 1
2FOR1 2
BLA 2

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

Post by Adrian Kuegel » Thu Apr 11, 2002 3:10 pm

Ivan, thank you for your reply. But I don't understand, why the output for ywyvmak's input is "ABC 4" and not "ABC 1-4". And can you explain, why your program does not print the "the" for my input. Because it is said in the description: "Punctuation preceding or following an index term will be ignored." What does it mean?

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by Ivan Golubev » Thu Apr 11, 2002 5:05 pm

Oops, I've used a bit incorrect input file (there was a space after ABC). So real output is 'ABC 1-4', of course.

About 'the': I think (and it can be check with asserts, lazy to do it by my own ;-)) that terms doesn't contains anything else than digits and letters. My solution reads them as is. I've done searching via strstr. If before and after term there something else than letters and digits then it's match.

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

Compile error using stl

Post by Rossi » Tue Nov 26, 2002 8:02 am

why compile error hah! runs great on VC6.0 problem-698
[cpp]
#include <iostream>
#include <vector>
#include <cctype>
#include <functional>
#include <algorithm>

using namespace std;

char *strUpper(char *);
char *getToken(char *);

class Word{
public:
char word[12];
vector<int> lst;

Word(char *str)
{
strcpy(word, strUpper(str));
lst.clear();
}
};

class Compare:binary_function<Word, Word, bool>{
public:
result_type operator()(first_argument_type A, second_argument_type B)
{
return (result_type)(!(strcmp(A.word, B.word) > 0));
}
};

char str[10000000L];

int main()
{
int set = 0, lnum;
char *p;

vector<Word> listOfWords;
vector<Word>::iterator iter;
vector<int>::iterator i;

while(gets(str)){
if(str[0] == NULL)
break;

if(!listOfWords.empty())
listOfWords.clear();

while(str[0]){
Word toPush(str);
listOfWords.push_back(toPush);
gets(str);
}

sort(listOfWords.begin(), listOfWords.end(), Compare());

gets(str);
for(lnum = 1; str[0]; lnum++){
strUpper(str);

p = getToken(str);
while(p){
iter = listOfWords.begin();
while(iter != listOfWords.end()){
int cmp = strcmp(p, iter->word);

if(cmp == 0){
iter->lst.push_back(lnum);
break;
}
else if(cmp < 0)
break;

iter++;
}
p = getToken(NULL);
}
gets(str);
}

cout << "Case " << ++set << endl;

for(iter = listOfWords.begin(); iter != listOfWords.end(); iter++){
if(!iter->lst.empty()){
i = iter->lst.begin();
cout << iter->word << " " << *i++;

for(bool seq = false; i != iter->lst.end(); i++){
switch(*i - *(i - 1)){
case 0:
break;
case 1:
seq = true;
break;
default:
if(seq){
cout << "-" << *(i - 1) << ", " << *i;
seq = false;
}
else
cout << ", " << *i;
break;
}
}
if(seq)
cout << "-" << *(i - 1);
cout << endl;

iter->lst.clear();
}
}
cout << endl;
}
return 0;
}

char *strUpper(char *in)
{
char *p = in;

while(*p){
*p = toupper(*p);
p++;
}
return in;
}

char *getToken(char *str)
{
static char *p;
char *q;

if(str)
p = str;

if(p == NULL)
return NULL;

while(!(isdigit(*p) || isalpha(*p)) && *p)
p++;

q = p;
while(isdigit(*p) || isalpha(*p))
p++;

if(*p == NULL)
p = NULL;
else
*p++ = NULL;

return q;
}

[/cpp]

suman
New poster
Posts: 45
Joined: Fri Oct 19, 2001 2:00 am
Contact:

To err is human

Post by suman » Tue Nov 26, 2002 11:25 pm

hi,
The following modification of your code compiles under g++ cygwin. You made some mistakes. Try looking at the changes. The OJ uses differnent compiler which is obviously better than VC++6.0. Try the dev-cpp which is a windows port of gcc. You can find it at http://www.sourceforge.net.


[cpp]
#include <cstdio>
#include <iostream>
#include <vector>
#include <cctype>
#include <functional>
#include <algorithm>

using namespace std;

char *strUpper(char *);
char *getToken(char *);

class Word{
public:
char word[12];
vector<int> lst;

Word(char *str)
{
strcpy(word, strUpper(str));
lst.clear();
}
};

class Compare:binary_function<Word, Word, bool>{
public:
result_type operator()(first_argument_type A, second_argument_type B)
{
return (result_type)(!(strcmp(A.word, B.word) > 0));
}
};

char str[10000000L];

int main()
{
int set = 0, lnum;
char *p;

vector<Word> listOfWords;
vector<Word>::iterator iter;
vector<int>::iterator i;

while(gets(str)!=0){
if(str[0] == 0)
break;

if(!listOfWords.empty())
listOfWords.clear();

while(str[0]){
Word toPush(str);
listOfWords.push_back(toPush);
gets(str);
}

sort(listOfWords.begin(), listOfWords.end(), Compare());

gets(str);
for(lnum = 1; str[0]; lnum++){
strUpper(str);

p = getToken(str);
while(p){
iter = listOfWords.begin();
while(iter != listOfWords.end()){
int cmp = strcmp(p, iter->word);

if(cmp == 0){
iter->lst.push_back(lnum);
break;
}
else if(cmp < 0)
break;

iter++;
}
p = getToken(NULL);
}
gets(str);
}

cout << "Case " << ++set << endl;

for(iter = listOfWords.begin(); iter != listOfWords.end(); iter++){
if(!iter->lst.empty()){
i = iter->lst.begin();
cout << iter->word << " " << *i++;
bool seq;

for(seq = false; i != iter->lst.end(); i++){
switch(*i - *(i - 1)){
case 0:
break;
case 1:
seq = true;
break;
default:
if(seq){
cout << "-" << *(i - 1) << ", " << *i;
seq = false;
}
else
cout << ", " << *i;
break;
}
}
if(seq)
cout << "-" << *(i - 1);
cout << endl;

iter->lst.clear();
}
}
cout << endl;
}
return 0;
}

char *strUpper(char *in)
{
char *p = in;

while(*p){
*p = toupper(*p);
p++;
}
return in;
}

char *getToken(char *str)
{
static char *p;
char *q;

if(str)
p = str;

if(p == NULL)
return NULL;

while(!(isdigit(*p) || isalpha(*p)) && *p)
p++;

q = p;
while(isdigit(*p) || isalpha(*p))
p++;

if(*p == 0)
p = 0;
else
*p++ = 0;

return q;
}

[/cpp]

Good luck.

- Suman

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

Post by Rossi » Fri Nov 29, 2002 5:57 am

Thankx a lot........

sjn
Learning poster
Posts: 73
Joined: Mon Apr 08, 2002 8:22 am
Contact:

TLE

Post by sjn » Sat Jul 19, 2003 3:14 pm

oh, i got TLE :cry:

can anyone help me?

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

698

Post by titid_gede » Wed Jul 30, 2003 12:06 pm

can you tell me what is the trickies input for this problem? always got WA after almost 10 submissions :(

regards,
titid
Kalo mau kaya, buat apa sekolah?

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Mon Aug 11, 2003 11:47 am

All the obvious trickies are in the sample input. Everything more would be a spoiler.

One advise: Don't assume anything that's not explicitly written in the problem description. I did that and got 10+ WAs before finaly getting AC.

bobi1978
New poster
Posts: 13
Joined: Tue Jul 22, 2003 1:57 pm
Location: Kavadarci, Macedonia
Contact:

Post by bobi1978 » Mon Aug 18, 2003 3:20 pm

little joey wrote:

Code: Select all

One advise: Don't assume anything that's not explicitly written in the problem description. 
What do you mean by this?

1) In the INDEX list, if there is a character that is not ALPHA_NUM what should I do with it?
ex:--- INDEX LIST ---

//foR*
ab*c<>
?a?b?

What are the Indexes in this list?

FOR AB A

or

FOR ABC AB
?

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Mon Aug 18, 2003 4:09 pm

There are no such cases; that would violate the description.
As I said, I'm not gonna give a spoiler.

Aleksandrs Saveljevs
New poster
Posts: 39
Joined: Fri Nov 14, 2003 11:18 pm
Location: Riga, Latvia
Contact:

Post by Aleksandrs Saveljevs » Mon Jan 19, 2004 11:14 pm

Well, I managed to get it AC recently. :)

In the end, having only REs, beseeching God he would let me have WA, suddenly, to my astonishment, it was AC. :o

There are several found-out things I would like to share:

1) Words can be longer than 10 symbols, but shorter than 21 (maybe it results from 10 letters plus 10 digits; though it contradicts to what is said in the sample input). It may be not so if one can get SIGABRT because of something else than assert().

2) Either lines can be longer than 25000 symbols or there are less than 2 blank lines in the end.

If any of the above statements are wrong, please, make a post, so that people wouldn't have so much problems. :)

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

Post by minskcity » Fri Aug 06, 2004 8:04 pm

I've already got 10 WA, can anybody tell me what I'm missing? Any special cases? HELP, PLEASE... :cry: [cpp]#include <iostream>
#include <string>
#include <fstream>
#include <ctype.h>
#include <vector>
#include <map>
using namespace std;

map < string, vector < long > > index;
vector < long > empty;
string s;
long t;

int main(){

// ifstream cin("in.txt");

t = 1;
while(getline(cin, s)){

index.clear();

while(s.size()){ // storing index words
for(unsigned i = 0; i < s.size(); i++) s = toupper(s);
index[s] = empty;
getline(cin, s);
}

long cnt = 0;
while(getline(cin, s) && s.size() && ++cnt){ // inserting to index lines of word that match
s += ' ';
string word = "";

for(unsigned i = 0; i < s.size(); i++){
s = toupper(s);
if(isalnum(s)) word += s;
else{
if(index.find(word) != index.end() && (!index[word].size() || index[word].back() != cnt))
index[word].push_back(cnt);
word = "";
}
}

}

cout << "Case " << t++ << endl; // starting to print answer

for(map < string, vector < long > > :: iterator it = index.begin(); it != index.end(); it++)
if(it->second.size()){
cout << it->first;
for(unsigned i = 0; i < it->second.size(); i++){
if(i + 1 == it->second.size() || it->second + 1 != it->second[i + 1]){
cout << " " << it->second;
if(i + 1 != it->second.size()) cout << ",";
}else{
long st = i;
while(i + 1 < it->second.size() && it->second + 1 == it->second[i + 1]) i++;
cout << " " << it->second[st] << "-" << it->second;
if(i + 1 != it->second.size()) cout << ",";
}
}
cout << endl;
}

cout << endl;

}

return 0;
}
[/cpp]

Post Reply

Return to “Volume 6 (600-699)”