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
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <map>

using uint64 = std::uint64_t;

uint64 aPlusB(uint64 sum) {
    std::map<uint64, uint64> helper_map{{0, 1},
                                        {1, 2},
                                        {2, 3},
                                        {3, 4},
                                        {4, 5},
                                        {5, 6},
                                        {6, 7},
                                        {7, 8},
                                        {8, 9},
                                        {9, 10},
                                        {10, 9},
                                        {11, 8},
                                        {12, 7},
                                        {13, 6},
                                        {14, 5},
                                        {15, 4},
                                        {16, 3},
                                        {17, 2},
                                        {18, 1}};

    std::map<uint64, uint64> out;
    out [0] = 1;
    out [1] = helper_map[sum%10] ;
    int i = 2;
    uint64 mod = 10;
    while (sum / mod) {
        mod *= 10;
        uint64 mod_sum = 0;
        auto tmp = sum % mod;
        tmp = tmp / (mod/100);
        if(tmp < 19)
            mod_sum = helper_map[tmp] * out[i-2];
        if(tmp >= 10)
            mod_sum += helper_map[tmp/10] * out[i - 1];
        out[i] = std::max(mod_sum, out[i-1]);
        i++;
    }
    return out.rbegin()->second;
}

int main()
{
    uint64 sum;
    std::cin >> sum;
    std::cout << aPlusB(sum);
    return 0;
}