Hello All,
I have been trying to solve this problem using dynamic programming. As far as i know the program works well except for cases with a '0' in the middle. Could any tell me how to handle a valid '0' in the middle of a testcase. The code given below works well on my pc but generates seg fault when i try to run it in spoj.
#include<iostream>
#include<cstring>
using namespace std;
bool check(string s)
{
if((s[0]-48)>2 || s.length()==1 || (s.length()==2 && s[0]==50 && (s[1]-48)>6) || (s.length()==2 && (s[0]=='0' || s[1]=='0'))) return false;
return true;
}
bool isvalid(string s)
{
int len = s.length();
for(int i=0;i<len;i++)
{
if(s[i]=='0' && (s[i-1]=='0' || (s[i-1]-48)>2)) return false;
}
return true;
}
int main()
{
string s;
long long count;
cin>>s;
while(s[0]!='0')
{
int len = s.length();
long long c[len][len];
if(!isvalid(s))
{
cout<<0<<endl;
}
else
{
for(int i=0;i<len;i++) c[i][i] = 1;
long long x = 0;
for(int i=len-2;i>=0;i--)
{
int temp = i;
x++;
while(temp>=0)
{
if(x==1)
{
string d = s.substr(temp, 2);
if(check(d)) c[temp][temp+x] = 2;
else c[temp][temp+x] = 1;
}
else
{
if(c[temp][temp+1]==1)
{
c[temp][temp+x] = c[temp+1][temp+x];
}
else
{
c[temp][temp+x] = c[temp+1][temp+x] + c[temp+2][temp+x];
}
}
temp--;
}
}
cout<<c[0][len-1]<<endl;
}
cin>>s;
}
return 0;
}