Page 2 of 2
Posted: Thu Mar 01, 2007 1:09 pm
by Solaris
It is easier to think of critical test cases if you give us overview of your approach. It is a typical Grammar Problem. All other approaches may result in Wrong Answers.
Posted: Thu Mar 01, 2007 1:23 pm
by Jan
Try the cases...
Input:
Code: Select all
the tom and the jerry and goofy and mickey like cat and mouse
tom likes jerry, jerry and goofy hate mickey
jimmy knows a cat, the cat likes mouse, the mouse hates the cat
goofy hates cats
a goofy loves a jimmy
a goofy loves a jimmy and the cat, mouse hates cat
a goofy loves the a jimmy
Code: Select all
YES I WILL
YES I WILL
YES I WILL
NO I WON'T
YES I WILL
YES I WILL
NO I WON'T
Hope these help.
Posted: Thu Mar 01, 2007 3:59 pm
by sakhassan
I too really think it as a typical grammar problem... Thanks for the I?O set. my code pass all these test cases .. But still wrong answer though
my grammar look like this:
Code: Select all
S -> A|A,A
A -> LVL
L -> C and C| C
C -> N|RN
R -> a|the
N -> all noun
V -> all verb|Vs
s = statement
a = action
l = action list
c = actor
R = article
did i miss something ??
Thanks in advance
Posted: Thu Mar 01, 2007 4:09 pm
by Jan
Try the cases...
Input:
Code: Select all
tom hatessssssssssssss jerry
tom hatessssssssssssss jerry,
tom hatessssssssssssss jerry, , tom hatessssssssssssss jerry
tom hates jerry jerry hates tom
Code: Select all
YES I WILL
NO I WON'T
NO I WON'T
NO I WON'T
NO I WON'T
Hope these help. If your code passes, you can post your code.
Posted: Thu Mar 01, 2007 4:51 pm
by sakhassan
HERE MY DUMP CODE
Code: Select all
#include<stdio.h>
#include<string.h>
#define N 100
void match(char s[N]);
void get_next();
void Noun();
void L();
void S();
void R();
void C();
void A();
void V();
char lookahead[N];
int index;
int len;
char str[N];
int flag;
void V()
{
int i;
int tmp_len;
int mark;
char temp[N],tok[N],tmp[N];
char ch;
mark = 1;
//refill it in two parts
strcpy(temp,lookahead);
tmp_len = strlen(lookahead);
for(i=0;i<tmp_len;i++)
{
ch = lookahead[i];
if(ch=='s')
{
mark = 0;
break;
}
tok[i]=ch;
}
tok[i]='\0';
if(strcmp(tok,"hate")==0)
{}
//match(tok);
else if(strcmp(tok,"love")==0)
{} //match(tok);
else if(strcmp(tok,"know")==0)
{} //match(tok);
else if(strcmp(tok,"like")==0)
{} //match(tok);
else
flag = 0;
//match(tok);
if(!mark && flag)
{
strcpy(tmp,&temp[i]);
tmp_len = strlen(tmp);
i = 0;
while(i<tmp_len)
{
ch = tmp[i];
if(ch!='s')
{
flag = 0;
break;
}
i++;
}
}
if(flag)
get_next();
return;
}
void get_next()
{
int tag = 0;
int i;
char ch;
for(i=0;index<len;index++,i++)
{
ch = str[index];
if(ch==' ')
{
index++;
if(tag)
break;
else
continue;
}
else if(ch==',' && tag==1)
{
break;
}
if(tag==0)
tag=1;
lookahead[i]=ch;
}
lookahead[i]='\0';
}
void match(char s[])
{
if(strcmp(lookahead,s)==0)
get_next();
else
flag = 0;
return;
}
void Noun()
{
if(strcmp(lookahead,"tom")==0)
match("tom");
else if(strcmp(lookahead,"jerry")==0)
match("jerry");
else if(strcmp(lookahead,"goofy")==0)
match("goofy");
else if(strcmp(lookahead,"mickey")==0)
match("mickey");
else if(strcmp(lookahead,"jimmy")==0)
match("jimmy");
else if(strcmp(lookahead,"dog")==0)
match("dog");
else if(strcmp(lookahead,"cat")==0)
match("cat");
else if(strcmp(lookahead,"mouse")==0)
match("mouse");
else
flag = 0;
return;
}
void S()
{
A();
if(flag)
{
while(strcmp(lookahead,",")==0)
{
match(",");
A();
}
}
return;
}
void A()
{
L();
if(flag)
{
V();
if(flag)
L();
else
return;
}
return;
}
void L()
{
C();
if(flag)
{
while(strcmp(lookahead,"and")==0)
{
match("and");
if(flag)
C();
}
}
}
void C()
{
if( (strcmp(lookahead,"a")==0) || (strcmp(lookahead,"the")==0) )
R();
if(flag)
Noun();
return;
}
void R()
{
if( (strcmp(lookahead,"a")==0) || (strcmp(lookahead,"the")==0) )
match(lookahead);
else
flag = 0;
return;
}
int main()
{
while(gets(str))
{
index=0;
flag = 1;
len = strlen(str);
get_next();
S();
if(flag && strcmp(lookahead,"")!=0 )
flag = 0;
if(flag)
printf("YES I WILL\n");
else
printf("NO I WON'T\n");
}
return 0;
}
Posted: Fri Mar 02, 2007 9:51 am
by Jan
Your code returns wrong output when the sentences are seperated by comma(s), look at the samples
Input:
Code: Select all
tom hates jerry , tom and jerry and goofy like jimmy
tom hates jerry , tom and jerry and goofy hate jimmy
And another thing, you can use the return type of the functions as 'bool' rather than 'void'. Then it would be easier to keep track of your work.
Posted: Sun Feb 24, 2008 4:30 pm
by peterkwan
I tested my program and all the test cases in the sample and in this thread are passed. However, I still get WA all the time? could somebody help?
Code: Select all
#include <iostream>
#include <string>
using namespace std;
string trim(string s) {
s.erase(0,s.find_first_not_of(" "));
s.erase(s.find_last_not_of(" ")+1);
return s;
}
bool isNoun(string s) {
return s=="tom" || s=="jerry" || s=="goofy" || s=="mickey" || s=="jimmy" || s=="dog" || s=="cat" || s=="mouse";
}
bool isArticle(string s) {
return s=="a" || s=="the";
}
bool isVerb(string s) {
if (s.length()<4) return false;
if (s=="hate" || s=="love" || s=="know" || s=="like") return true;
if (s[s.length()-1] != 's') return false;
s=s.substr(0,s.length()-1);
return isVerb(s);
}
bool isActor(string s) {
s=trim(s);
if (isNoun(s)) return true;
size_t i = s.find_first_of(" ");
if (i==string::npos) return false;
string s1=trim(s.substr(0,i));
string s2=trim(s.substr(i+1));
return isArticle(s1) && isNoun(s2);
}
bool isActiveList(string s) {
s=trim(s);
if (isActor(s)) return true;
size_t i=s.rfind(" and ");
if (i==string::npos) return false;
string s1=trim(s.substr(0,i));
string s2=trim(s.substr(i+5));
return isActiveList(s1) && isActor(s2);
}
bool isAction(string s) {
s=trim(s);
size_t i1=s.find(" hate"),i2=s.find(" know"),i3=s.find(" love"),i4=s.find(" like");
if (i1!=string::npos) {
string s1=trim(s.substr(0,i1));
string s2=trim(s.substr(i1+1));
if (!isActiveList(s1)) return false;
size_t i=s2.find(" ");
if (i==string::npos) return false;
string s3=trim(s2.substr(0, i));
string s4=trim(s2.substr(i+1));
return isVerb(s3) && isActiveList(s4);
}
else if (i2!=string::npos) {
string s1=trim(s.substr(0,i2));
string s2=trim(s.substr(i2+1));
if (!isActiveList(s1)) return false;
size_t i=s2.find(" ");
if (i==string::npos) return false;
string s3=trim(s2.substr(0, i));
string s4=trim(s2.substr(i+1));
return isVerb(s3) && isActiveList(s4);
}
else if (i3!=string::npos) {
string s1=trim(s.substr(0,i3));
string s2=trim(s.substr(i3+1));
if (!isActiveList(s1)) return false;
size_t i=s2.find(" ");
if (i==string::npos) return false;
string s3=trim(s2.substr(0, i));
string s4=trim(s2.substr(i+1));
return isVerb(s3) && isActiveList(s4);
}
else if (i4!=string::npos) {
string s1=trim(s.substr(0,i4));
string s2=trim(s.substr(i4+1));
if (!isActiveList(s1)) return false;
size_t i=s2.find(" ");
if (i==string::npos) return false;
string s3=trim(s2.substr(0, i));
string s4=trim(s2.substr(i+1));
return isVerb(s3) && isActiveList(s4);
}
return false;
}
bool isStatement(string s) {
s=trim(s);
if (isAction(s)) return true;
size_t i=s.rfind(",");
if (i==string::npos) return false;
string s1=trim(s.substr(0,i));
string s2=trim(s.substr(i+1));
return isStatement(s1) && isAction(s2);
}
main() {
string s;
while (getline(cin, s)) {
if (cin.eof())
break;
if (isStatement(s))
cout << "YES I WILL" << endl;
else
cout << "NO I WON'T" << endl;
}
return 0;
}
Thanks a lot.
Re:
Posted: Sat Nov 15, 2008 6:53 am
by DD
arc16 wrote:hi,
yes, there might be LOT OF whitespace, including before eol.
so there would be something like:
Code: Select all
___tom__hatess___jerry___,_____mickey loves goofy______
'_' is whitespace
In the WON'T, it's ascii #39.
you could also try this:
Code: Select all
mickey lovess goofy and jerry , tom loves goofy and mickey and jerry,the jerry loves a goofy and a tom and a mickey and the jerry and the tom and the mickey and a jerry and a tom and a mickey, tom loves a cat ,jerry loves a dog
the answer is YES
It is interesting that My A.C. program outputs NO for your input. So I guess that there must be spaces before and after a comma in the Judge's inputs.