Page 1 of 4
EOF
Posted: Fri May 03, 2002 3:36 pm
by Felipe Santos Pinheiro
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?
Posted: Sat May 04, 2002 12:47 am
by Stefan Pochmann
Don't. Just ignore that silly statement.
EOF
Posted: Tue May 21, 2002 6:18 am
by Fresh
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
271
Posted: Sun Aug 04, 2002 11:25 am
by htl
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?
Posted: Sun Aug 04, 2002 12:27 pm
by xenon
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.
Posted: Sun Aug 04, 2002 2:14 pm
by htl
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]
Got AC but poor speed with problem 271
Posted: Sat Aug 10, 2002 3:22 pm
by obayashi
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
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]
Posted: Tue Aug 13, 2002 6:27 pm
by bjacoke001
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?
Posted: Wed Aug 14, 2002 2:58 am
by obayashi
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.
Posted: Wed Aug 14, 2002 8:10 am
by Dominik Michniewski
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
Posted: Wed Aug 14, 2002 8:34 am
by obayashi
thanx, i will go find it and get it fixed~
271 WA
Posted: Sun Nov 30, 2003 11:25 am
by shuan_ck
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;
}
}
Posted: Mon Dec 01, 2003 9:44 am
by sohel
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.
Posted: Thu Dec 11, 2003 4:27 am
by shuan_ck
Thanks a lot. That should be one of my mistakes.
stack based approach
Posted: Fri Apr 02, 2004 1:23 am
by stcheung
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.