394. ACODE (Alphacode)

[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 ?

[daft_wullie]

Well, I think that there will be no invalid case in the input data. Thus it doesn't matter what your code returns for this case. I got AC without considering invalid testcases.

[pranny]

My solution produces valid op for all the test cases mentioned here. However, it fails when i submit it. Any idea which test cases it could fail to?

    #!/usr/bin/env python
    def solution(a):
        a = str(a)
        poss = [0] * len(a)
        for i in xrange(len(a)):
            if i == 0:
                poss[i] = 1
            elif i > 0:
                poss[i] = poss[i-1]
                if int(a[i-1] + a[i]) < 27 and a[i] != '0':
                    if i >= 2:
                        poss[i] = poss[i-2] + poss[i-1]
                    else:
                        poss[i] = 2
        return poss[-1]    
    while True:
        a = int(raw_input())
        if a == 0:
            exit()
        else:
            print solution(a)

[daft_wullie]

What do think is the correct result for e.g. 20102011?

[cyclic_func]

Please check my IO

Input

181292321118743131219236834956616923925
61247812412412123124579127212412435689
1798235697156912783569836129273561725378612378635613059612634513257896128935618263
91253942735679263798126356239175735123123621561235621891231231289329845123895893912943129491253945129543951293459125912534912359145912123591256
9125394273567124124121241266251212047128436215612356218912312312893298451238958939129431294912539451295439512934591259125349123591459121235912561451111111111
101010
502
0

Output

10240
19440
0
58773123072
125539390881792
1
0

[daft_wullie]

Please check my IO

here you are

10240
19440
36864
58773123072
125539390881792
1
0

[rajdeep2]

Please check where my code is getting WA ? For what tests Case ?

#include <iostream>
#include <algorithm>
#include <string>
#include <fstream>
using namespace std;

typedef long long int ll;

int main()
{
  //  ifstream cin("/Users/Rajdeep/Downloads/Google Code Jam Practice/Google Code Jam Practice/input.txt");
    string s;
    cin>>s;
    while(s!="0")
    {
        ll n;
        n = (ll)s.size();
        long long int dp[n+1];
        dp[n] = 1;
        ll f;
        f = s[n-1]-'0';
        if(f==0)
        {
            dp[n-1]=0;
        }
        else
        {
            dp[n-1]=1;
        }
        for(ll i=n-2;i>=0;i--)
        {
            ll a;
            a = s[i] - '0';
            ll b;
            b = s[i+1] - '0';
            ll w;
            w = (10*a)+b;
            if(a==0&&b==0)
            {
                dp[0] = 0;
                break;
            }
            else if(a!=0)
            {
                if(b!=0)
                {
                    dp[i] = dp[i+1];
                    //  cout<<w<<endl;
                    if(w<=26)
                    {
                        dp[i] = dp[i] + dp[i+2];
                    }
                    //  cout<<dp[i]<<endl;
                }
                else
                {
                    if(w<=26)
                    {
                        dp[i] = dp[i+2];
                    }
                    else
                    {
                        dp[0] = 0;
                        break;
                    }
                }
            }
            else
            {
                dp[i] = dp[i+1];
            }
        }
        cout<<dp[0]<<endl;
        cin>>s;
    }
    return 0;
}