271 - Simply Syntax
Moderator: Board moderators
-
- New poster
- Posts: 2
- Joined: Fri May 03, 2002 2:52 am
EOF
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?
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?
-
- A great helper
- Posts: 284
- Joined: Thu Feb 28, 2002 2:00 am
- Location: Germany
- Contact:
EOF
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:](./images/smilies/icon_wink.gif)
[cpp]
int len;
char s[1024];
while (cin.getline(s,1024))
{ if (!(len = strlen(s))) break;
process(s,len);
}
[/cpp]
-novice
![:wink:](./images/smilies/icon_wink.gif)
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]
[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
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]
It ran 26 secs...
i hope that somebody could help me with the poor speed
![:oops:](./images/smilies/icon_redface.gif)
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
And yet my memories still shine
-
- New poster
- Posts: 6
- Joined: Fri Jul 26, 2002 6:42 pm
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:](./images/smilies/icon_lol.gif)
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:](./images/smilies/icon_lol.gif)
Time makes a fool of memory
And yet my memories still shine
And yet my memories still shine
-
- Guru
- Posts: 834
- Joined: Wed May 29, 2002 4:11 pm
- Location: Wroclaw, Poland
- Contact:
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![:-)](./images/smilies/icon_smile.gif)
Best regards
Dominik
PS. My program took 0.01 sec and 64 kB RAM![;-)](./images/smilies/icon_wink.gif)
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
![:-)](./images/smilies/icon_smile.gif)
Best regards
Dominik
PS. My program took 0.01 sec and 64 kB RAM
![;-)](./images/smilies/icon_wink.gif)
271 WA
I got WA.
Anyone tell me why, please?
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;
}
}
stack based approach
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.
Another optimization is to take out the N.