OJ Board

We are getting time limit exceeded to this one. we reduced the sentences down to 12 basic types and if the sentence give is not one of these types then we do not accept it. We tried different test cases and it worked with all of them. I am wondering can a sentence contains capitals in it ( but even if it does our program shoul five a wrong answer).

Thank YOU!

//@begin_of_source_code

#include<iostream.h>
#include<string.h>

struct tp
{
char n[4];
char w[5][3];
};

tp tb[5]=
{
{"A", {"a", "e", "i", "o", "u" }},
{"MOD",{"ga","ge","gi","go","gu",}},
{"BA", {"ba","be","bi","bo","bu",}},
{"DA", {"da","de","di","do","du",}},
{"LA", {"la","le","li","lo","lu",}}
};

char tg[12][100]=
{
"LA<PS>MOD<PS>",
"LA<PS>MOD<PS>LA<PS>",
"LA<PS>MOD<PS>NAM",
"NAMMOD<PS>",
"NAMMOD<PS>LA<PS>",
"NAMMOD<PS>NAM",
"LA<PS>BA<PS>",
"LA<PS>BA<PD>",
"NAMBA<PS>",
"NAMBA<PD>",
"DA<PS>",
"DA<PD>"
};

char sentence[2000][8];
int cnt;

bool NAM(char str[])
{
switch (str[strlen(str)-1])
{
case 'a':
case 'e':
case 'i':
case 'o':
case 'u':
return false;
break;
}
return true;
}

bool PREDA(char str[])
{
char word[6];
int i;

if (strlen(str)!=5) return false;
for (i=0;i<5;i++)
{
switch (str)
{
case 'a':
case 'e':
case 'i':
case 'o':
case 'u':
word='V';
break;
default:
word='C';
break;
}
}
word='';
if ((strcmp(word,"CCVCV")==0) || (strcmp(word,"CVCCV")==0)) return true;
return false;
}

void convert(char str[])
{
int i,j;

if (NAM(str))
{
strcpy(str,"NAM");
return;
}
if (strlen(str)<=2)
{
for (i=0;i<5;i++)
for (j=0;j<5;j++)
{
if (strcmp(str,tb.w[j])==0)
{
strcpy(str,tb.n);
return;
}
}
}
else
{
if (PREDA(str))
{
strcpy(str,"PREDA");
return;
}
}
str[0]='';
return;
}

int find(char str[])
{
int i;

for (i=0;i<=cnt;i++)
{
if (strcmp(str,sentence)==0) return i;
}
return -1;
}

void connect(char sent[])
{
int i;

sent[0]='';
for (i=0;i<=cnt;i++)
{
if (sentence[0]!='')
{
strcat(sent,sentence);
}
}
}

int search(int pos)
{
int i;
for (i=pos;i>=0;i--)
{
if ((sentence[0])!='') return i;
}
return -1;
}

bool grammar()
{
char sent[100];
int i,j;

i=find("PREDA");
while (i!=-1)
{
strcpy(sentence[i],"<PS>");
i++;
while (strcmp(sentence[i],"PREDA")==0)
{
sentence[i][0]='';
i++;
}
i=find("PREDA");
}

i=find("A");
while (i!=-1)
{
j = search(i-1);
if (j!=-1)
if (((strcmp(sentence[j],"<PS>")==0) || (strcmp(sentence[j],"<PD>")==0)) && (strcmp(sentence[i+1],"<PS>")==0))
{
sentence[j][0]='';
sentence[i][0]='';
strcpy(sentence[i+1],"<PD>");
}
i=find("A");
}

connect(sent);
for (i=0;i<12;i++)
{
if (strcmp(sent,tg[i])==0) return true;
}
return false;
}

void main()
{
char str[100];
bool flag,broken;
int i,j;

cin >> str;
while (str[0]!='#')
{
cnt=0;
flag=true;
broken=false;
while (flag)
{
if (str[strlen(str)-1]=='.')
{
str[strlen(str)-1]='';
flag=false;
}
convert(str);
if (str[0]!='')
{
strcpy(sentence[cnt++],str);
}
else
{
cout << "Bad!" << endl;
broken=true;
while (str[strlen(str)-1]=='.') cin >> str;
cin >> str;
break;
}
cin >> str;
}
if (broken) continue;
cnt--;
if (grammar()) cout << "Good" << endl;
else cout << "Bad!" <<endl;
}
}

//@end_of_source_code

We are getting time limit exceeded to this one. we reduced the sentences down to 12 basic types and if the sentence give is not one of these types then we do not accept it. We tried different test cases and it worked with all of them. I am wondering can a sentence contains capitals in it ( but even if it does our program should give a wrong answer).

Thank YOU!

//@begin_of_source_code

#include<iostream.h>
#include<string.h>

struct tp
{
char n[4];
char w[5][3];
};

tp tb[5]=
{
{"A", {"a", "e", "i", "o", "u" }},
{"MOD",{"ga","ge","gi","go","gu",}},
{"BA", {"ba","be","bi","bo","bu",}},
{"DA", {"da","de","di","do","du",}},
{"LA", {"la","le","li","lo","lu",}}
};

char tg[12][100]=
{
"LA<PS>MOD<PS>",
"LA<PS>MOD<PS>LA<PS>",
"LA<PS>MOD<PS>NAM",
"NAMMOD<PS>",
"NAMMOD<PS>LA<PS>",
"NAMMOD<PS>NAM",
"LA<PS>BA<PS>",
"LA<PS>BA<PD>",
"NAMBA<PS>",
"NAMBA<PD>",
"DA<PS>",
"DA<PD>"
};

char sentence[2000][8];
int cnt;

bool NAM(char str[])
{
switch (str[strlen(str)-1])
{
case 'a':
case 'e':
case 'i':
case 'o':
case 'u':
return false;
break;
}
return true;
}

bool PREDA(char str[])
{
char word[6];
int i;

if (strlen(str)!=5) return false;
for (i=0;i<5;i++)
{
switch (str)
{
case 'a':
case 'e':
case 'i':
case 'o':
case 'u':
word='V';
break;
default:
word='C';
break;
}
}
word='';
if ((strcmp(word,"CCVCV")==0) || (strcmp(word,"CVCCV")==0)) return true;
return false;
}

void convert(char str[])
{
int i,j;

if (NAM(str))
{
strcpy(str,"NAM");
return;
}
if (strlen(str)<=2)
{
for (i=0;i<5;i++)
for (j=0;j<5;j++)
{
if (strcmp(str,tb.w[j])==0)
{
strcpy(str,tb.n);
return;
}
}
}
else
{
if (PREDA(str))
{
strcpy(str,"PREDA");
return;
}
}
str[0]='';
return;
}

int find(char str[])
{
int i;

for (i=0;i<=cnt;i++)
{
if (strcmp(str,sentence)==0) return i;
}
return -1;
}

void connect(char sent[])
{
int i;

sent[0]='';
for (i=0;i<=cnt;i++)
{
if (sentence[0]!='')
{
strcat(sent,sentence);
}
}
}

int search(int pos)
{
int i;
for (i=pos;i>=0;i--)
{
if ((sentence[0])!='') return i;
}
return -1;
}

bool grammar()
{
char sent[100];
int i,j;

i=find("PREDA");
while (i!=-1)
{
strcpy(sentence[i],"<PS>");
i++;
while (strcmp(sentence[i],"PREDA")==0)
{
sentence[i][0]='';
i++;
}
i=find("PREDA");
}

i=find("A");
while (i!=-1)
{
j = search(i-1);
if (j!=-1)
if (((strcmp(sentence[j],"<PS>")==0) || (strcmp(sentence[j],"<PD>")==0)) && (strcmp(sentence[i+1],"<PS>")==0))
{
sentence[j][0]='';
sentence[i][0]='';
strcpy(sentence[i+1],"<PD>");
}
i=find("A");
}

connect(sent);
for (i=0;i<12;i++)
{
if (strcmp(sent,tg[i])==0) return true;
}
return false;
}

void main()
{
char str[100];
bool flag,broken;
int i,j;

cin >> str;
while (str[0]!='#')
{
cnt=0;
flag=true;
broken=false;
while (flag)
{
if (str[strlen(str)-1]=='.')
{
str[strlen(str)-1]='';
flag=false;
}
convert(str);
if (str[0]!='')
{
strcpy(sentence[cnt++],str);
}
else
{
cout << "Bad!" << endl;
broken=true;
while (str[strlen(str)-1]=='.') cin >> str;
cin >> str;
break;
}
cin >> str;
}
if (broken) continue;
cnt--;
if (grammar()) cout << "Good" << endl;
else cout << "Bad!" <<endl;
}
}

//@end_of_source_code

i got WA too.

isn't it a bit weird when the problem description said "You can assume that all words will be correctly formed.", but you still will get some strange words ended with a vowel. but not a name or A LA etc. ?

Try this one...

la mutce bunbo mrenu bi ditca.
la fumna bi le mrenu.
djan ga vedma le
negro ketpi.
la fumna bi ditca.
la fumna bi ditca
djan ga vedsa le negro ketpi.
djan be vedsa a vedma a ketpi.
.
#

it's answer is...

Good
Bad!
Good
Good
Bad!
Good
Bad!

how big is the maximum input sentence?
my program can handle your test case but still got WA
or is there any other special test case?

[quote="wyvmak"]i got WA too.

isn't it a bit weird when the problem description said "You can assume that all words will be correctly formed.", but you still will get some strange words ended with a vowel. but not a name or A LA etc. ?[/quote]

I did some test and found there are non-Loglan words that
end with a vowel. However, I don't know how to deal with
them and still get WA too.

i've passed this problem several weeks ago...
the last thing i remember was i add the ability to handle multiple line input, like this:
i think you should check it too, it's harder than it looks

I have checked my program for a long time, but failed to find any mistake. Are there any tricks in this problem?

There is my testcase:

INPUT:
le bcade ga fgiho.
le bcade ge fgiho le bcade.
le bcade gi fgiho li bcade.
le bcade go fgiho lo bcade.
le bcade gu fgiho lu bcade.
foobar ge juklo li manpi.
lo qrase ba tviwu a xiyzu.
lo qrase ba tviwu a xiyzu e futye i
futno o blara u jukko.
da ztoya.
de ztoya i grota u thomo.
di ztoya.
do ztoya a brute.
du ztoya.
la mutce
bunbo mrenu ba ditca a ghoto.
futon be ditca.
gruton bi ditca.
le blara bunbo mrenu bo ditca.
jhqdhjqdwhjqwdhjqdjhwefdjhqwedhjwefzz bu ditca.
djb ba bbaba.
djan ga vedma le negro ketpi.
bad starts now.
la fumna bi le mrenu.
dja blarg.
djb ba.
.
le bcad ga fgiho.
le bcade gn fgiho le bcade.
le bcade gi fgiho ly bcade.
le bcade go fgiho lo bcadf.
bcade gu fgiho lu bcade.
lo qrase ba tviwu x xiyzu.
lo qrase ba tviwu a xiyzu e futye i
futno o blara u jukk.
la ztoya.
ge ztoya i grota u thomo.
bi ztoya.
do ztoya a bruten.
du zaoya.
futon e ditca.
gruton li ditca.
le blar bunbo mrenu bo ditca.
djan da vedma le negro ketpi.
#

My OUTPUT:
Good
Good
Good
Good
Good
Good
Good
Good
Good
Good
Good
Good
Good
Good
Good
Good
Good
Good
Good
Good
Bad!
Bad!
Bad!
Bad!
Bad!
Bad!
Bad!
Bad!
Bad!
Bad!
Bad!
Bad!
Bad!
Bad!
Bad!
Bad!
Bad!
Bad!
Bad!
Bad!

Have you tried having the period "." as a single word?
Something like
le_bcade_ga_fgiho_.
where the underscore "_" is space.
The output should be "Good"

Hope this helps.

junjieliang wrote:Have you tried having the period "." as a single word?
Something like
le_bcade_ga_fgiho_.
where the underscore "_" is space.
The output should be "Good"

Hope this helps.

my program gave the correct answer to such cases

I've got two more questions here:

1. Should A, E, I, O, U be considered as vowels as a, e, i, o, u? Also, is 'GA' a MOD just like 'ga'?

2. If a word contains some non-alpha characters, should this characters be considered as consonant, or just consider the sentence to be a Bad one?

1. vowels 'a' and 'A' (and so on) are the same so mAma and mAmA are to be considered as correct.

2. I use scanf() to read words from stdin, so I think, that not letter characters should be considered as consonants ... but I think that such input doesn't exist ....

I don't know how you write your code, but you must create grammar (from problem statement) which you can easy parse ) i.e.
it's dificult to parse grammar like
A ->BCD | BCE | BF
but it's easier to parse something like
A -> BA'
A' -> CA'' | F
A'' -> D | E
If you don't do this - think about that (it's possible, that you avoid a lot of problems, when you transform grammar in such way )

Good luck
Dominik

I still failed to find any mistake in my program
Here it is
[cpp]
#include <stdio.h>
#include <strstream>
#include <string.h>
#include <ctype.h>
#define ISVOWEL(x) ( (x)=='a' || (x)=='e' || (x)=='i' || (x)=='o' || (x)=='u' )
#define NOTVOWEL(x) ( (x)!='a' && (x)!='e' && (x)!='i' && (x)!='o' && (x)!='u' )

using namespace std;

int main() {
char line[10000], word[500];

#ifndef ONLINE_JUDGE
freopen("134.in", "r+", stdin);
freopen("134.out", "w+", stdout);
#endif

for ( ; ; ) {
memset(line, 0, sizeof(line));
scanf(" %c", &line[0]);
if ( line[0]=='#' )
break;

for ( ; ; ) {
char ch = getchar();
if ( ch=='.' )
break;
ch=( ch=='\n' ? ' ' : tolower(ch) );
strncat(line, &ch, 1);
}

int nitem = 0, item[10000];
bool valid = true;

istrstream strin(line);
while ( strin >> word ) {
int len = (int)strlen(word);

if ( len==1 && ISVOWEL(word[0]) )
if ( nitem && item[nitem-1]==6 )
if ( nitem<2 || item[nitem-2]!=7 )
item[nitem-1]=7; // predstring + A
else
--nitem;
else
item[nitem++]=0; // A
else if ( len==2 && word[0]=='g' && ISVOWEL(word[1]) )
item[nitem++]=1; // MOD
else if ( len==2 && word[0]=='b' && ISVOWEL(word[1]) )
item[nitem++]=2; // BA
else if ( len==2 && word[0]=='d' && ISVOWEL(word[1]) )
item[nitem++]=3; // DA
else if ( len==2 && word[0]=='l' && ISVOWEL(word[1]) )
item[nitem++]=4; // LA
else if ( NOTVOWEL(word[len-1]) )
item[nitem++]=5; // NAM
else if ( len==5 &&
(NOTVOWEL(word[0]) && NOTVOWEL(word[1]) && ISVOWEL(word[2]) && NOTVOWEL(word[3]) && ISVOWEL(word[4]) ||
NOTVOWEL(word[0]) && ISVOWEL(word[1]) && NOTVOWEL(word[2]) && NOTVOWEL(word[3]) && ISVOWEL(word[4])) ) {
if ( nitem==0 )
item[nitem++]=6;
else if ( item[nitem-1]==4 )
item[nitem-1]=8; // LA + predstring
else if ( item[nitem-1]!=6 && item[nitem-1]!=8 )
item[nitem++]=6;
}
else {
valid=false; break;
}
}

for ( int i=0; i<nitem; ++i )
if ( item==8 )
item=5;

if ( valid ) {
valid=false;

if ( nitem==3 && item[0]==5 && item[1]==1 && item[2]==6 )
valid=true;
else if ( nitem==4 && item[0]==5 && item[1]==1 && item[2]==6 && item[3]==5 )
valid=true;
else if ( nitem==3 && item[0]==5 && item[1]==2 && item[2]==6 )
valid=true;
else if ( nitem==4 && item[0]==5 && item[1]==2 && item[2]==7 && item[3]==6 )
valid=true;
else if ( nitem==2 && item[0]==3 && item[1]==6 )
valid=true;
else if ( nitem==3 && item[0]==3 && item[1]==7 && item[2]==6 )
valid=true;
}

printf(valid ? "Good\n" : "Bad!\n");
fgets(line, 10000, stdin);
}

#ifndef ONLINE_JUDGE
fclose(stdin);
fclose(stdout);
#endif

return 0;
}
[/cpp]

Are you sure that you correct handle inputs like: Output should be "Good"

Dominik

Dominik Michniewski wrote:Are you sure that you correct handle inputs like:

Code: Select all

la 
mutce
      bunbo 
mrenu bi 
ditca
.

Output should be "Good"

Dominik

My program does give the correct answer for this testcase...