fork download
  1. #include<iostream>
  2. using namespace std;
  3.  
  4. int length(string a) {
  5. int i=0;
  6. while(a[i])
  7. i++;
  8. return i;
  9. }
  10.  
  11. int numberPossibilites(string input, int dp[],int index){
  12. int ans = 0, ansNext=0;
  13.  
  14. if(input[index] == '\0') {
  15. dp[index]=1;
  16. return 1;
  17. } else {
  18. if(!dp[index]){
  19. if(input[index+1] != '\0'){
  20. if(input[index] > '0' && input[index] < '3' && input[index+1] < '7'){
  21. if(!dp[index+2]){
  22. ans = numberPossibilites(input, dp, index+2);
  23. } else {
  24. ans = dp[index+2];
  25. }
  26.  
  27. }
  28. }
  29. if(input[index] != '0'){
  30. if(!dp[index+1]){
  31. ansNext = numberPossibilites(input, dp, index+1);
  32. ans += ansNext;
  33. } else {
  34. ans += dp[index+1];
  35. }
  36. }
  37. dp[index] = ans;
  38. }
  39.  
  40. }
  41. return dp[index];
  42. }
  43.  
  44. int main() {
  45. string input;
  46. while(true){
  47. cin >> input;
  48. if(input[0] == '0' && input[1] == '\0')
  49. break;
  50. int len = length(input);
  51.  
  52. int *dp = new int[len+1]();
  53.  
  54. cout << numberPossibilites(input, dp, 0) << "\n";
  55. }
  56. }
Success #stdin #stdout 0s 16056KB
stdin
202020
1001
2220220202020
1521015204552
122011056
12345
0
stdout
1
0
2
4
2
3