i'm trying out this problem www.spoj.pl/problems/ACODE
i'm getting TLE.. I donno y my recursion leads to tle
#include<iostream>
#include<map>
#include<stdio.h>
#include<string.h>
using namespace std;
map<string, long long> ans;
map<string, bool> flags;
long long find(char *s, int len){
if(flags[s])
return ans[s];
if(s[0]=='0')
ans[s]=0;
else if(len==1)
ans[s]=1;
else if(len==2)
if(s[0]<'3'&&s[1]<'7'&&s[1]!='0')
ans[s]=2;
else
ans[s]=1;
else{
ans[s]=find(s+1,len-1);
if(s[0]<'3'&&s[1]<'7')
ans[s] = ans[s]+find(s+2,len-2);
}
flags[s]=true;
return ans[s];
}
int main(){
char str[5001];
while(1){
scanf("%s",str);
if(str[0]=='0') break;
ans.clear();
flags.clear();
printf("%lld\n",find(str,strlen(str)));
}
return 0;
}
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
