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

Felipe Santos Pinheiro
New poster
Posts: 2
Joined: Fri May 03, 2002 2:52 am

EOF

Post by Felipe Santos Pinheiro » Fri May 03, 2002 3:36 pm

Hi,

In the problem 271 (Simply Syntax), the output say "... the list of answers is followed by an end-of-file character." How I can print the EOF character?

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann » Sat May 04, 2002 12:47 am

Don't. Just ignore that silly statement.

Fresh
New poster
Posts: 46
Joined: Mon Apr 15, 2002 10:42 am
Contact:

EOF

Post by Fresh » Tue May 21, 2002 6:18 am

I normally use this style,

[cpp]
int len;
char s[1024];

while (cin.getline(s,1024))
{ if (!(len = strlen(s))) break;
process(s,len);
}
[/cpp]

-novice :wink:

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

271

Post by htl » Sun Aug 04, 2002 11:25 am

The last data makes me confused.

In:
Cqpq

Out:
NO

And I think it's YES because the substring after C can be divide into 2 right sentences 'q','pq' or 'qp','q'

Could someone tell me why?

xenon
Learning poster
Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland

Post by xenon » Sun Aug 04, 2002 12:27 pm

Every character from p..z is a correct sentence. This applies only to characters, not to strings made up of characters. So 'pq' and 'qp' are not correct sentences. So 'Cqpq' is one character too long.

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

Post by htl » Sun Aug 04, 2002 2:14 pm

My code got TLE. I can't find out where I can improve the code. Could someone help me?
[c]
#include<stdio.h>
#include<string.h>
int check(char [],int,int);
void main(void)
{
char s[300];
while(scanf("%s",s)!=EOF)
if(check(s,0,strlen(s)-1))
printf("YES\n");
else
printf("NO\n");
}
int check(char s[],int start,int end)
{
int x;
if(start==end)
{
if(s[start]>='p' && s[start]<='z')
return 1;
else
return 0;
}
if(s[start]=='N' && check(s,start+1,end))
return 1;
if(s[start]=='C' || s[start]=='D' || s[start]=='E' || s[start]=='I')
{
if(end-(start+1)+1<2)
return 0;
for(x=start+1;x<end;x++)
if(check(s,start+1,x) && check(s,x+1,end))
return 1;
}
return 0;
}
[/c]

obayashi
New poster
Posts: 33
Joined: Thu Jun 20, 2002 1:18 pm

Got AC but poor speed with problem 271

Post by obayashi » Sat Aug 10, 2002 3:22 pm

I actually use DP to solve this problem but the speed is not so satisfactory
It ran 26 secs...

i hope that somebody could help me with the poor speed :oops:
here is the code

[cpp]

#include <iostream>
#include <string.h>
using namespace std;
int valid[128],ok[300][300];
char str[300];
void init () {
for (int i=0;i<128;i++) valid = 0;
for (char ch='p';ch<='z';ch++) valid[ch] = 1;
valid['N'] = valid['C'] = valid['D'] = valid['E'] = valid['I'] = 1;
}
int check (int s,int t) {
int i,len,flag;
len = t-s+1;
if (ok[s][t]>=0) return ok[s][t];
if (len<0) return 0;
if (str[s]=='N') {
ok[s+1][t] = check(s+1,t);
return ok[s+1][t];
} else if (str[s]=='C' || str[s]=='D' || str[s]=='E' || str[s]=='I') {
for (i=1;i<len;i++) {
ok[s+1][s+i] = check(s+1,s+i);
ok[s+i+1][t] = check(s+i+1,t);
flag = (ok[s+1][s+i] && ok[s+i+1][t]);
if (flag) {
ok[s][t] = 1;
return 1;
}
}
ok[s][t] = 0;
return 0;
}
ok[s][t] = 0;
return 0;
}
int main () {
int i,j,len,flag;
init();
while (cin>>str) {
flag = 1;
len = strlen(str);
for (i=0;i<=len;i++)
for (j=0;j<=len;j++)
ok[j] = -1;
for (i=0;i<len;i++) {
if (!valid[str]) flag = 0;
ok = (str>='p' && str<='z');
}
if (!flag) {
cout<<"NO"<<endl;
} else if (check(0,len-1)) {
cout<<"YES"<<endl;
} else {
cout<<"NO"<<endl;
}
}
return 0;
}

[/cpp]
Time makes a fool of memory
And yet my memories still shine

bjacoke001
New poster
Posts: 6
Joined: Fri Jul 26, 2002 6:42 pm

Post by bjacoke001 » Tue Aug 13, 2002 6:27 pm

My program also took over 20 seconds for the problem, and I used the same DP that you did. Does anyone have an idea why it would take so long?

obayashi
New poster
Posts: 33
Joined: Thu Jun 20, 2002 1:18 pm

Post by obayashi » Wed Aug 14, 2002 2:58 am

with a glance at this problem, i thought it just another easy one which would be solved by
simple recursion. but i was wrong. i got TLE first, then i modified my code a little and got AC.

what about the string

NNNNNNN...NNNNNNNNCst
253 N 1 C 1 s 1 t totally 256 chars

how long does your program run with this string?

i think with DP it should gimme a nlog(n), but it didn't.

actually it gimme a n^2, not nlog(n), cos i divide the string from its head...

i think if with divide this string from the middle, then re-middle ..., it will be ok.

just like the difference between bubble sort and quicksort.

Do u think so?

I will fix it when free. :lol:
Time makes a fool of memory
And yet my memories still shine

Dominik Michniewski
Guru
Posts: 832
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Wed Aug 14, 2002 8:10 am

I got accepted with this problem and I use only simple recursion ...
I think, that you must make one of following mistakes in your resursive solution:
1. didn't right handle of end of string
2. had an error in recursion .....
my recursive function is very simple :-)

Best regards
Dominik

PS. My program took 0.01 sec and 64 kB RAM ;-)

obayashi
New poster
Posts: 33
Joined: Thu Jun 20, 2002 1:18 pm

Post by obayashi » Wed Aug 14, 2002 8:34 am

thanx, i will go find it and get it fixed~
Time makes a fool of memory
And yet my memories still shine

shuan_ck
New poster
Posts: 2
Joined: Sun Nov 30, 2003 11:16 am
Contact:

271 WA

Post by shuan_ck » Sun Nov 30, 2003 11:25 am

I got WA.
Anyone tell me why, please?

Code: Select all

#include<iostream>
#include<stack>
#include<string>
using namespace std;

int main()
{
    string t;
    while(cin>>t){
        stack<char> s;
        int q=0;
        for(int i=0;i<t.size();i++){
            if(t[i]<'a')
                s.push(t[i]);
            else{
                q++;
            }
            while(q>1){
                if(s.empty()){
                    i=t.size();
                    break;
                }
                if(s.top()!='N')
                    q--;
                s.pop();
                while(!s.empty()&&s.top()=='N')
                    s.pop();
            }
        }
        if(q>1||!s.empty())
            cout << "NO" << endl;
        else
            cout << "YES" << endl;
    }
}

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Mon Dec 01, 2003 9:44 am

Hi,

Rule 2 states that 'If s is a correct sentence, then so is Ns.'
I may be wrong but I think your program gives wrong output for cases such as Np, Nx etc.
:wink:

shuan_ck
New poster
Posts: 2
Joined: Sun Nov 30, 2003 11:16 am
Contact:

Post by shuan_ck » Thu Dec 11, 2003 4:27 am

Thanks a lot. That should be one of my mistakes. :)

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

stack based approach

Post by stcheung » Fri Apr 02, 2004 1:23 am

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.

Post Reply

Return to “Volume 2 (200-299)”