10058 - Jimmi's Riddles

[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.

[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

Output:

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.

[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

[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

Output:

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.

[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;
}

[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

Output:

Code: Select all

YES I WILL
YES I WILL

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.

[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.

[DD]

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.