35 / 60
Sep 2011

I don't get you. Can you provide the link ? It works correctly on my computer for the sample test cases in the problem statement and in the forums too. confused

I'm afraid it can't possibly give the right output, so you can't be testing it properly. Go back to your post and click the 'view submissions' link at the top of your code. You'll see Leppy has run it on the sample input and it has resulted in the wrong output.

OMG !! I can't believe that I missed out exiting when the input is 0. Sorry abt that. Thanks. Got AC. smiley

7 months later

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;
}
3 months later

no idea why i'm getting TLE. I guess my code solves for all cases imp imp

removed after acc

You should not be using a map for this problem. The complexity of that is driving you over the limit.

is there any other way to store a value for a corresponding string? astonished
it exceeds time limit if i recalculate for same strings without using map

You dont need to store an entire string. The string doesn't change throughout the entire problem. What does change?

plz gimme a 5 digit test case where my logic fails

code removed after ACC. Thank you leppy once more :) 
wat a blunder mistake :@ :@
14 days later

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;
}
28 days later

works for all above mentioned test cases but is giving WA imp

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;
}
4 months later

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;

}

28 days later

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";
	}
}
}

for testcase: 110
output should be 1, your code gives 2...same testcase on which my code was not working!