## 384 - Slurpys

All about problems in Volume 3. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

boatfish
New poster
Posts: 18
Joined: Thu May 08, 2003 11:46 am

### 384 - Slurpys

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
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

### 384

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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Recursive descent should suffice..

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

### WA 384 Slurpys

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--``
Last edited by Eduard on Wed Feb 02, 2005 2:00 pm, edited 1 time in total.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

GVahe
New poster
Posts: 17
Joined: Thu Aug 05, 2004 6:04 pm
Location: Armenia
Contact:
Just add one more condition in the function slimp
if length(s)<2 then begin slimp:=false; exit ;end

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan
Thanks I got AC.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

oscartheroot
New poster
Posts: 5
Joined: Sat Oct 11, 2008 1:03 pm

### 384 WA !

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
Learning poster
Posts: 58
Joined: Wed Dec 31, 2003 8:43 am
Contact:

### Re: 384 WA !

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

oscartheroot
New poster
Posts: 5
Joined: Sat Oct 11, 2008 1:03 pm

### Re: 384 WA !

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