# SPOJ ACODE

## 394. Alphacode

Also seen at:

Source: East Central North America 2004

## Summary

Two people want to send coded messages to each other. One possible encoding scheme is to simply replace each letter with its numerical value in the alphabet and then string all the digits together without spaces. Determine the number of possible ways to decode a message encoded this way.

## Explanation

This is a dynamic programming problem.

If we take a single number ${\displaystyle a}$, the problem will be in a single state. If you want to add another number ${\displaystyle b}$ to the problem, the problem could be in one of two states:

• The two numbers printed one after another, ${\displaystyle ab}$
• The two numbers combined to form a different single number, ${\displaystyle c}$ ${\displaystyle (a*10+b)}$

One or both of the above states may be valid. If the first one remains valid${\displaystyle (b\neq 0)}$, the new state is ${\displaystyle b}$. If the second remains valid ${\displaystyle (1\leq c\leq 26)}$ then the state is ${\displaystyle c}$. For each of the two valid states, keep track of the previous valid states that lead to it.

## Gotchas

• The result is a 64-it integer - make sure intermediate calculations use that data type.
• String "110" only has one possible encoding.

## Input

25114
1111111111
3333333333
226210
0


## Output

6
89
1
3