fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. string addBigInt(string num1, string num2) {
  9.     string result = "";
  10.     int i = num1.length() - 1;
  11.     int j = num2.length() - 1;
  12.     int carry = 0;
  13.  
  14.     while (i >= 0 || j >= 0 || carry) {
  15.         int sum = carry;
  16.         if (i >= 0) sum += num1[i--] - '0';
  17.         if (j >= 0) sum += num2[j--] - '0';
  18.         carry = sum / 10;
  19.         result += to_string(sum % 10);
  20.     }
  21.     reverse(result.begin(), result.end());
  22.     return result;
  23. }
  24.  
  25. int main() {
  26.     string S;
  27.     if (!(cin >> S)) {
  28.         cout << 0 << endl;
  29.         return 0;
  30.     }
  31.  
  32.     int n = S.length();
  33.  
  34.     if (n == 0 || S[0] == '0') {
  35.         cout << 0 << endl;
  36.         return 0;
  37.     }
  38.  
  39.     vector<string> dp(n + 1, "0");
  40.  
  41.     dp[0] = "1";
  42.     dp[1] = "1";
  43.  
  44.     for (int i = 2; i <= n; i++) {
  45.         if (S[i - 1] != '0') {
  46.             dp[i] = addBigInt(dp[i], dp[i - 1]);
  47.         }
  48.  
  49.         int doubleDigit = (S[i - 2] - '0') * 10 + (S[i - 1] - '0');
  50.         if (doubleDigit >= 10 && doubleDigit <= 26) {
  51.             dp[i] = addBigInt(dp[i], dp[i - 2]);
  52.         }
  53.  
  54.         if (dp[i] == "0") {
  55.             cout << 0 << endl;
  56.             return 0;
  57.         }
  58.     }
  59.  
  60.     cout << dp[n] << endl;
  61.  
  62.     return 0;
  63. }
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
2115
stdout
copy 
5
https://ideone.com/mgSxRx
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!