394. ACODE (Alphacode)

[chownikhil_sof]

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

[cegprakash]

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

removed after acc

[leppyr64]

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

[cegprakash]

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

[leppyr64]

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

[leppyr64]

Your logic makes no sense.

[cegprakash]

plz gimme a 5 digit test case where my logic fails

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

[leppyr64]

I can think of plenty of two and three digit ones.

[highfiver_sof]

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

[leppyr64]

long long or int? Which do you want to use? Don't use both

[e_noether]

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

[rbaid]

Problem url - http://www.spoj.pl/problems/ACODE/
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;

}

[leppyr64]

viewtopic.php?f=3&t=5516

[abhishekiiit_sof]

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

[rbaid]

can anybody give me sometest cases......... plzzzzzzzzzz.

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

[abhishekiiit_sof]

@rbaid thanx......... bt it is again giving WA. its working for 110

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

[rbaid]

[quote="abhishekiiit"]@rbaid thanx......... bt it is again giving WA. its working for 110

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

[/quote]

on testcase:
10
0

your code is giving some garbage value - 577741808038355000

[abhishekiiit_sof]

thanx rbaid............GOT AC

[dplass_sof]

forum HS - What is this?

Forum konkursu High School Programming League (hs.spoj.pl)

[pvo3obae4h]

Hi,

Could you pls explain how to consider the input like:
301
Isn't this an invalid test case? and hence o/p should be 0 ?