ACODE

ALPHACODE

Link to the question : ACODE 

HINT :

We solve the question using dynamic programming. Lets say we check for the string {1,2,3}. We create a array b[] such that b[i] denotes the decryption of the string from (0 to i). For example b[0] denotes the decryption of {1} while b[1] denotes the decryption of {1,2}. We assign b[0] = 1 as it is very clear that the first element can be written in 1 way. Now for the rest of the string we assign b[i]= b[i-1] and we check with the previous element. If the previous and current element both can form a valid character, i.e, if x > 9 & x<27 we add b[i-2] to b[i]. This is done because if we know that we can directly from i-2th position to i-th as i-1 th and i-2 th both can form a character together.

SOURCE CODE:

/* Alphacode */
/* Sushant Gupta */

#include<stdio.h>
#include<string.h>
int main()
{
    char a[5010];
    int i,j;
    scanf("%s",a);
    while(a[0]!='0')
    {

        int n= strlen(a);
        long long int b[n];
        for(i=0;i<n;i++)
            b[i]= 0;
        b[0]= 1;
        for(i=1;i<n;i++)
        {

            j= (a[i-1] - '0') * 10 + (a[i] - '0');
            if(a[i]- '0')
                b[i]= b[i-1];
             if(j>9 && j<27)
             {
                 if(i==1)
                    b[i]= b[i] + 1;
                 else
                    b[i]= b[i] + b[i-2];
             }

        }
        printf("%lld\n",b[n-1]);
        scanf("%s",a);
    }
    if(a[0]=='0')
        return 0;
}