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;
}
Hey guys,
I've tried out the test cases here (and they work fine for me), but I just can't seem to get AC. I've used forward DP. Any help?
#include<stdio.h>
#include<string.h>
int valid;
long long int dp[10000];
int count(char str[],int len)
{
memset(dp,0,sizeof(dp));
int i;dp[0]=1;
for(i=1;i<len;i++) {
//if(str[i]=='0')
dp[i]=dp[i-1];
//else
{ if(str[i-1]=='1')
{ if(dp[i-1]==1 && str[i]!='0')
dp[i]=2;
else if(str[i]!='0')
dp[i]=dp[i-1]+dp[i-2];
}
if(str[i-1]=='2' && (str[i]>='0' && str[i]<='6')) {
if(dp[i-1]==1 && str[i]!='0')
dp[i]=2;
else if(str[i]!='0')
dp[i]=dp[i-1]+dp[i-2];
}
}
}
/* for(i=0;i<len;i++)
printf("%d ",dp[i]);
printf("\n");
*/ return dp[len-1];
}
int main()
{
while(1) {
char str[5010];
scanf("%s",str);//cout<<str<<endl;
if(strcmp("0",str)==0)
return 0;
printf("%d\n",count(str,strlen(str)));
valid=0;
}
return 0;
}
works for all above mentioned test cases but is giving WA
a is similar to dptable[i-2]
b is similar to dptable[i-1]
#include<stdio.h>
int main(void)
{
char str[5001];
unsigned long long int a,b,cnt=0,i=1,n;
scanf("%s",str);
while(str[0]!='0')
{
a=1;
b=1;
cnt=0;
i=1;
while(str[i]!='\0')
{
if(((str[i-1]=='2' && str[i]<'7') || (str[i-1]=='1')) && str[i]!='0')
cnt=a+b;
else if(str[i]=='0')
{
if(str[i-1]=='2' || str[i-1]=='1')
cnt=a;
else
{cnt=0; break;}
}
else
cnt=b;
a=b;
b=cnt;
i++;
}
printf("%llu\n",cnt);
scanf("%s",str);
}
return 0;
}
Problem url - http://www.spoj.pl/problems/ACODE/4
My code is working for test case but i am getting WA ... Could anyone suggest more test cases or point out the mistake in the program ?
include
include
using namespace std;
int main()
{
char s[10000];
long long int sc[10000],sz=0,i,j,k,c=0,ans=1,m,n,x;
while(1)
{
cin>>s;
sz=strlen(s);
if(sz==1 &&s [0]=='0')
break;
for(i=0;i<sz;i++)
{
if (s[i]=='0')
sc[c-1] = ((int)s[i-1]-48)*10;
else
{
sc[c] = (int)s[i]-48;
c++;
}
}
m=1;n=0;
if(sc[0]<27)
{
for(i=1;i<c;i++)
{
if(sc[i]>26)
{ans=0;break;}
if( (10*sc[i-1]+sc[i])<27 )
{
ans = 2*m+n;
x = m;
m = m+n;
n = x;
}
else{
ans = m+n;
m = m+n;
n = 0;
}
}
}
else
ans=0;
cout<<ans<<endl;
c=0;ans=1;
}
return 0;
}
can anybody give me sometest cases......... plzzzzzzzzzz.
#include <iostream>
#include <string>
using namespace std;
int main()
{
string a;
while(1)
{
cin>>a;
if(a[0]=='0')
break;
int n=a.size();
long long int f[3];
f[0]=1;
int x=(a[1]-48)+(a[0]-48)*10;
int i=2;
if(x<=26 && x>10 && x!=20 && (a[1]!='0'))
{
if(x==21 || x==22 || x==11 ||x==12)
{
if(a[2]=='0')
{
f[1]=1;
i++;
}
else
{
f[1]=2;
}
}
else
f[1]=2;
}else
f[1]=1;
for(int i=2;i<n;i++)
{
x=(a[i]-48)+(a[i-1]-48)*10;
if(x<=26 && x>10 && x!=20)
{
if(x==21 || x==22 || x==11 || x==12)
{
if(a[i+1]=='0')
{
f[2]=f[1];
i++;
}
else
{
f[2]=f[0]+f[1];
}
}
else
f[2]=f[0]+f[1];
}
else
f[2]=f[1];
f[0]=f[1];
f[1]=f[2];
}
cout<<f[2]<<"\n";
}
}
}