1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <unordered_map>

static const long long digitSolutions[] = {
    1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0
};

static std::unordered_map<long long, long long> answerCache;

long long resolve(long long n) {
    if (answerCache.count(n)) {
        return answerCache[n];
    }

    long long digit10 = n % 10;
    long long digit100 = n % 100;
    long long rest10 = n / 10;
    long long rest100 = n / 100;

    long long result;
    if (rest10 == 0) {
        result = digitSolutions[digit10];
    } else {
        result = digitSolutions[digit100] * resolve(rest100) +
                 digitSolutions[digit10] * resolve(rest10);
    }

    answerCache[n] = result;
    return result;
}

int main() {
    std::ios_base::sync_with_stdio(false);

    long long n;
    std::cin >> n;
    std::cout << resolve(n) << std::endl;
    return 0;
}