fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long ll;
  5.  
  6. const int N = 5005;
  7. ll dp[N], vis[N], vid, n;
  8. string s;
  9.  
  10. ll solve(int i) {
  11.     if (i == s.size())
  12.         return 1;
  13.     if (s[i] == '0')
  14.         return 0;
  15.  
  16.     auto &ans = dp[i];
  17.     if (vis[i] == vid)
  18.         return ans;
  19.     vis[i] = vid, ans = 0;
  20.  
  21.     ans += solve(i + 1);
  22.  
  23.     if (i + 1 < s.size()) {
  24.         int two = (s[i] - '0') * 10 + (s[i + 1] - '0');
  25.         if (two >= 10 && two <= 26) {
  26.             ans += solve(i + 2);
  27.         }
  28.     }
  29.     return ans;
  30. }
  31.  
  32. void run() {
  33.     while (cin >> n, n) {
  34.         s = to_string(n);
  35.         vid++;
  36.         cout << solve(0) << '\n';
  37.     }
  38. }
  39.  
  40. signed main() {
  41.     ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  42. #ifdef clion
  43.     freopen("in.txt", "r", stdin);
  44.     freopen("output.txt", "w", stdout);
  45. #endif
  46.     run();
  47.     return 0;
  48. }
  49.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
10
0
stdout
copy 
1
https://ideone.com/Y34yxc
language:
C++ (gcc 8.3)
created:
7 days 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!