Page 2 of 4
Re: stack based approach
Posted: Fri Apr 02, 2004 2:52 pm
by junbin
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.
p271 WA
Posted: Tue Sep 14, 2004 10:46 pm
by lovemagic
Can anybody give me some sample input & output for p271?
271 wawawawa!
Posted: Thu Sep 16, 2004 2:47 pm
by tuyide
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!
Posted: Sat Oct 02, 2004 7:09 pm
by hiloshi
try this.
You should output "Yes".
Posted: Thu Dec 02, 2004 3:22 am
by d91-lek
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.
271
Posted: Tue Mar 22, 2005 7:33 am
by biterman
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.
Posted: Tue Mar 22, 2005 12:46 pm
by mf
Try these test cases:
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.
...
Posted: Tue Mar 22, 2005 7:31 pm
by biterman
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:
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.
Posted: Tue Mar 22, 2005 9:30 pm
by mf
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:
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.
I see now...
Posted: Tue Mar 22, 2005 10:02 pm
by biterman
...I must completely reevaluate my interpretation of the problem and my solution. Your suggestions have been most enlightening.
Thank you very much.
adios,
biterman.
271-CE!!!!!!!!!
Posted: Mon Jul 03, 2006 3:59 pm
by serendipity
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;
}
Posted: Mon Jul 03, 2006 6:45 pm
by ayon
no <conio.h> is allowed, no getch() is allowed
Posted: Sat Jul 08, 2006 7:23 am
by Joseph Kurniawan
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!
Posted: Sat Nov 04, 2006 4:53 am
by cytmike
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
271 - Simply Syntax
Posted: Sun Dec 10, 2006 1:49 am
by Kire Sopov
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]