271 - Simply Syntax

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

Moderator: Board moderators

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Re: stack based approach

Post by junbin » Fri Apr 02, 2004 2:52 pm

stcheung wrote:I got TLE at first too (it's unfortunate that time limit is now 10 second instead of the previous 30 second). I just got AC using 0.5 second by the stack approach. Basically just start at the end of the string, and whenever you see one of the C, D, E, or I, check if stack has at least 2 correct sentences. Let's say the current char is C, and the stack has 2 correct sentences on the top, then they can all be combined into one correct sentence and pushed onto the stack. If the stack doesn't have 2 correct sentences on the top, then you can immediately judge the string as incorrect.

Another optimization is to take out the N.
Starting from the front, using recursion, I got 0.12s..

This is a very simple parsing question. There is no need for branching, so no need for DP.

Realise that

If X is a sentence and Y is a sentence, XY is NOT a sentence.

This effectively tells you how the recursion should go.

lovemagic
Learning poster
Posts: 52
Joined: Thu Oct 02, 2003 11:38 am

p271 WA

Post by lovemagic » Tue Sep 14, 2004 10:46 pm

Can anybody give me some sample input & output for p271?
khobaib

tuyide
New poster
Posts: 8
Joined: Sat Oct 04, 2003 9:28 am

271 wawawawa!

Post by tuyide » Thu Sep 16, 2004 2:47 pm

Is there anybody so kind to give me some advice?


[cpp]
#include <iostream>
#include <cstring>
using namespace std;
int key[255];
int is(char *p)
{
int stack[300],stack1[300],now,f;
int i,at=0;
int len=strlen(p);
for(i=0;i<len;i++)
{
if(p=='N')continue;
stack[at++]=key[p];
}
while(1)
{
now=0;
f=0;
for(i=0;i<at;i++)
if(i<at-2&&stack==2&&stack[i+1]==1&&stack[i+2]==1)
{f=1;stack1[now++]=1;i+=2;}
else stack1[now++]=stack;
for(i=0;i<now;i++)
stack=stack1;
at=now;
if(!f)break;
}
if(at==1&&stack[0]==1)
return 1;
return 0;
}
int main()
{
int i;
for(i=0;i<255;i++)
key=0;
for(i='p';i<='z';i++)
key=1;
key['E']=2;
key['I']=2;
key['C']=2;
key['D']=2;
char s[1000];
while(cin.getline(s,1000))
{
if(is(s))
cout<<"YES\n";
else
cout<<"NO\n";
}
return 0;
}
[/cpp]
Thank a lot!

hiloshi
New poster
Posts: 20
Joined: Fri Aug 27, 2004 8:15 am
Location: Kanagawa, Japan

Post by hiloshi » Sat Oct 02, 2004 7:09 pm

try this.

Code: Select all

EppIqq
You should output "Yes".
I hope you can understand my poor English.

d91-lek
New poster
Posts: 22
Joined: Thu Sep 16, 2004 2:25 am
Location: KTH, Stockholm
Contact:

Post by d91-lek » Thu Dec 02, 2004 3:22 am



EppIqq

You should output "Yes".
Oh, but that is not a valid sentence. Two, yes, but we should
only output YES for exactly one valid sentence per line. Please
refer to the final example: Cqpq.

biterman
New poster
Posts: 3
Joined: Tue Mar 22, 2005 7:02 am
Location: Santo Domingo, Dominican Republic

271

Post by biterman » Tue Mar 22, 2005 7:33 am

Hi,

I apologize for starting a new topic, but the other posts on this problem seemed abandoned and I didn't know how bumping is looked upon here.

I've submitted a few solutions to this problem, after an initial WA, thinking that I might have interpreted the problem erroneously. And after some long testing and a lot of thought I've come up with this code that as far as I can tell /should/ solve the problem. I've also seen code from other people with the same interpretation of the problem, perfectly good C code mind you, and it also gets WA.

Thus I can only conclude that I must be misinterpreting the problem. I'll stop ranting and let the code speak for itself.

Code: Select all

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#define MAX_STR 100

char validUpper[] = { 'N', 'C', 'D', 'E', 'I' };
#define VU_MAX (sizeof validUpper / sizeof(char))

int isValidLower(char c);
int isValidUpper(char c);
int isValidSent(char *str);

int main(int argc, char **argv)
{
    char buff[MAX_STR][BUFSIZ];
    size_t c, i;
    for(c = 0; c < MAX_STR; c++)
    {
        fgets(buff[c], BUFSIZ, stdin);
        if(*buff[c] == EOF || *buff[c] == '\0')
        {
            break;
        }
        else if(isValidSent(buff[c]))
        {
            memset(buff[c], 0, BUFSIZ);
            strcpy(buff[c], "YES");
        }
        else
        {
            memset(buff[c], 0, BUFSIZ);
            strcpy(buff[c], "NO");
        }
    }
    puts("");
    for(i = 0; i < c; i++)
        printf("%s\n", buff[i]);
    return 0;
}

int isValidLower(char c)
{
    return ((c - 'p') >= 0 && ('z' - c) >= 0);
}

int isValidUpper(char c)
{
    size_t i;
    for(i = 0; i < VU_MAX; i++)
        if(c == validUpper[i])
            return 1;
    return 0;
}

int isValidSent(char *str)
{
    if(str != NULL && *str != '\0')
    {
        size_t l = strlen(str) - 1;
        if(l == 1 || l == 0)
            return isValidLower(*str);
        else if(l == 2)
        {
            if(isValidUpper(*str))
            {
                if(*str != 'N')
                    return 0;
                else
                    return isValidSent((str + 1));
            }
            else if(isValidLower(*str))
            {
                if(isValidUpper(*(str - 1)))
                    return isValidSent((str + 1));
            }
            else
                return 0;
        }
        else
            if(isValidUpper(*str) || isValidLower(*str))
                return isValidSent((str + 1));
    }
    return 0;
}
Thanks in advance :)

adios,
biterman.

PS: I realize this is certainly not the /best/ way to go about things, I/O and the crux of the problem.
"The machinery of government is always subordinate to the will of those who administer that machinery." --Frank Herbert.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Tue Mar 22, 2005 12:46 pm

Try these test cases:

Code: Select all

CDEIpqrst
CCppp
For each of the above cases, the answer must be "YES".

Also, your program prints unnecessary empty line at the start of output - you'll get P.E. for that.

[edit]
I/O code seems to be incorrect: I got different answers from your program, when I deleted newline characters at the end of input.

biterman
New poster
Posts: 3
Joined: Tue Mar 22, 2005 7:02 am
Location: Santo Domingo, Dominican Republic

...

Post by biterman » Tue Mar 22, 2005 7:31 pm

From those cases one infers that a succession of characters from p through z form a valid sentence, i.e.: pqrst. Given the fact that 'Ipqrst' needs to be two sentences thus we could have 'Ipq' and 'rst', or any other combination which satisfies Ist.

I believe that to achieve this with the code I've written one needs only comment out the line:

Code: Select all

if(isValidUpper(*(str - 1))) 
Which is inside isValidSent(). Having done this the test cases you suggest do return YES for output.

About the code behaving strangely when you delete the newline character at the end of input, I wrote the code counting on that newline because it is stated in the Input portion of the problem description that: "Each sentence is ended by a new-line character."

I've removed the unnecessary new-line character at the start of output, thank you.

I added

Code: Select all

buff[c][strlen(buff[c]) - 1] = '\0';
Right after receiving input, as I see it effectively deleting the newline character and still got a YES reply for the test cases you suggested, and many others besides.

Thank you again for your help :)

adios,
biterman.
"The machinery of government is always subordinate to the will of those who administer that machinery." --Frank Herbert.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Tue Mar 22, 2005 9:30 pm

A succession of p..z does not necessarily form a valid sentence. It depends on the context. 'pqrst' alone is not a valid sentence, but 5 independent concatenated sentences.

But 'CDEIpqrst' is a valid single sentence. Here I intentionally put brackets to delimit smaller sub-sentences (except those of form p..z) inside it:

Code: Select all

C(D(E(Ipq)r)s)t
Going from bottom to top:

By rule 1, 'p' and 'q' are two valid sentences.
By rule 3, 'Ipq' is a valid sentence, because it is a capital 'I', followed by exactly two valid sentences - 'p' and 'q'.
Then again by rule 1, 'r' is a valid sentence.
And by rule 3, 'EIpqr' is also valid: capital 'E', followed by two valid sentences 'Ipq' and 'r', concatencated together.
And so on.

biterman
New poster
Posts: 3
Joined: Tue Mar 22, 2005 7:02 am
Location: Santo Domingo, Dominican Republic

I see now...

Post by biterman » Tue Mar 22, 2005 10:02 pm

...I must completely reevaluate my interpretation of the problem and my solution. Your suggestions have been most enlightening.

Thank you very much.

adios,
biterman.
"The machinery of government is always subordinate to the will of those who administer that machinery." --Frank Herbert.

serendipity
New poster
Posts: 6
Joined: Tue May 09, 2006 9:22 pm

271-CE!!!!!!!!!

Post by serendipity » Mon Jul 03, 2006 3:59 pm

can someone tell me why my code shows the CE?

#include<stdio.h>
#include<conio.h>

int find_min(int p,int q)
{
if(p>q)
return q;
else
return p;


}

int main(void)
{
long cs;
int m, n;
char chpcs;

scanf("%ld", &cs);

while(cs)
{
chpcs=getch();
scanf("%d %d",&m,&n);

if(chpcs=='r'||chpcs=='Q')
printf("%d\n", find_min(m,n));


else if(chpcs=='k')
printf("%d\n",m*n/2);

else
printf("%d\n",( ((m+1)/2) * ((n+1)/2) ) );


cs--;


}
return 0;
}

:cry:

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon » Mon Jul 03, 2006 6:45 pm

no <conio.h> is allowed, no getch() is allowed
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

Joseph Kurniawan
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia

Post by Joseph Kurniawan » Sat Jul 08, 2006 7:23 am

If you're trying to use a certain C function, you should first check it's portability in UNIX.
How do we do that?
Quite simple.
For example :
You're trying to use getch();
Move your cursor to the getch(); and then press Ctrl+F1. The help Screen which provides all information about getch(); will appear. Keep scrolling down until you find the portability table.
If in the UNIX column is written "Yes", then the function is recognized in the Judge's GCC compiler.
As far as I know, every single function provided in conio.h is not portable for UNIX, therefore if you use them, it will produce CE.
you can use this method for every function.
Good luck!
There are 3 things one need to be successful : motivation, ability and chance. And if you're a believer, make it four : God's will.

User avatar
cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:

Post by cytmike » Sat Nov 04, 2006 4:53 am

To all people who are getting TLE, there is an algorithm posted on Methods to Solve website. It takes 0.5s to run.

http://www.comp.nus.edu.sg/~stevenha/pr ... y%20Syntax
Impossible is Nothing.

Kire Sopov
New poster
Posts: 7
Joined: Wed Sep 15, 2004 2:01 am

271 - Simply Syntax

Post by Kire Sopov » Sun Dec 10, 2006 1:49 am

What's wrong with this code. I tried so many input cases and it seems to work ok. Are there any special cases I'm missing?

[code]
#include <iostream>
#include <string>

#define IsPZ(ch) (((ch) >= 'p') && ((ch) <= 'z'))

bool CheckValid(const std::string &ss, std::string::const_iterator it, int nValids)
{
if (nValids < 0) return false;
else if (it == ss.end()) return (nValids == 0);

if (IsPZ(*it)) return CheckValid(ss, ++it, nValids-1);

switch (*it)
{
case 'N':
while ((it != ss.end()) && (*it == 'N')) ++it;
return (it == ss.end()) ? false : CheckValid(ss, it, nValids);

case 'C':
case 'D':
case 'E':
case 'I':
return CheckValid(ss, ++it, nValids+1);

default:
return false;
}
}

int main()
{
std::string str;

while (std::getline(std::cin, str) != NULL)
{
std::cout << (CheckValid(str, str.begin(), 1) ? "YES" : "NO") << std::endl;
}
}
[/code]

Post Reply

Return to “Volume 2 (200-299)”