384 - Slurpys

[boatfish]

I have tried all cases that I can think about, who can give me more testcases?
this is my code:
[cpp]#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

string reverse(string t){
int length=t.length(),i;
for(i=0;i<length/2;i++)
swap(t,t[length-1-i]);
return t;
}

bool slump(string t){
int length=t.length(),pos;
if(length==0 || t[0]!='D' && t[0]!='E')
return false;

if(length==1 || t[1]!='F')
return false;

pos=1;
while(pos<length && t[pos]=='F')
pos++;
if(pos==length)
return false;
else
return (t[pos]=='G' && pos==length-1 || slump(t.substr(pos)));
}

bool slimp(string t){
int length=t.length();
if(t[0]!='A' || length<=1)
return false;
if(length==2)
return t[1]=='H';
else if(t[length-1]=='C' && slump(t.substr(1,length-2)) || t[1]=='B' && t[length-1]=='C' && slimp(t.substr(2,length-3)))
return true;
else
return false;
}

int main(){
int n,i,length,pos,posh,posc;
cin>>n;
string t,reverse_t;
cout<<"SLURPYS OUTPUT\n";
for(i=1;i<=n;i++){
cin>>t;
length=t.length();
reverse_t=reverse(t);
posh=reverse_t.find('H');
posc=reverse_t.find('C');
if(posh==string::npos && posc==string::npos){
cout<<"NO\n";
continue;
}
else if(posh==string::npos)
pos=length-1-posc;
else if(posc=string::npos)
pos=length-1-posh;
else
pos=length-1-min(posc,posh);

if(slimp(t.substr(0,pos+1)) && pos+1<=length-2 && slump(t.substr(pos+1)))
cout<<"YES";
else
cout<<"NO";
cout<<endl;
}
cout<<"END OF OUTPUT\n";
return 0;
}[/cpp]

[htl]

I've heard that there's a 'linear solution'. I've also heard that there's a recurrance solution. I tried the latter and got TLE. Could someone give some advice?

[Larry]

Recursive descent should suffice..

[Eduard]

I'm getting 384 problem WA.I recursivly check if word is slim,slump.
CHeck my code please or give some I/O. Thanks.

Code: Select all

 ---- Got AC--

[GVahe]

Just add one more condition in the function slimp
if length(s)<2 then begin slimp:=false; exit ;end

[Eduard]

Thanks I got AC.

[oscartheroot]

I don't understand why am I getting worng answer, I can't find any error.
I find recursively through the string: a slimp must always finish by a 'C' or an 'H', so I divise it in two substrings: slimp, and slump; and then check these two parts. I think it's a simple method for a simple problem...but it seems I am wrong, since I still get wrong answer.

Code: Select all

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

bool compslump(string slump){
     if (slump[0]!='E' and slump[0]!='D') return false;
     if (slump[slump.size()-1]!='G') return false;
     int pos;
     for (int i=1; i<slump.size(); i++)if (slump[i]!='F') {pos=i; break;}
     if (pos==1)return false;
     if (slump[pos]=='G') return true;
     return compslump (slump.substr (pos, slump.size()-pos));
}

bool compslimp(string slimp){
     if (slimp[0]!='A' or slimp.size()<2) return false;
     if (slimp[slimp.size()-1]=='H'){
                                   if (slimp.size()==2) return true;
                                   return false;
     }
     if (slimp[slimp.size()-1]=='C'){
                                     if (slimp[1]!='B') return compslump (slimp.substr (1, slimp.size()-2));
                                     return compslimp (slimp.substr (2, slimp.size()-3));
     }
     return false;    
}

string resposta (bool a, bool b){
       if (a and b) return "YES";
       return "NO";
}

int main(){
    int casos;
    cin>>casos;
    cout<<"SLURPYS OUTPUT"<<endl;
    for (int cas=0; cas<casos; cas++){
        string slurpy;
        cin>>slurpy;
        size_t corte=slurpy.find_last_of("C");
        if (corte==string::npos)corte=slurpy.find_last_of("H");
        string slimp=slurpy.substr (0, corte+1);
        string slump=slurpy.substr (corte+1, slurpy.size()-corte);
        cout<<resposta(compslimp(slimp), compslump(slump))<<endl;
    }
    cout<<"END OF OUTPUT"<<endl;
}

[L I M O N]

visit: http://www.youngprogrammer.com and compare with my solutions. best of luck.

[oscartheroot]

I just found the error:
i counted AHEFGG as a slurpy, when I souldn't, only AHEFG is a slurpy. I mean, I didn't count if there was more than one G at the end.

Thanks, I got accepted