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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <cstdio>
#include <cstdlib>
#include <cstdint>

#include <array>

typedef unsigned long long int llu;

struct stats
{
    uint64_t digit;
    uint64_t zz_eq;
    uint64_t zz_gt;
    uint64_t zn;
    uint64_t nn_eq;
    uint64_t nn_gt;
};

uint64_t solve(uint64_t v);

int main()
{
    llu v;
    scanf("%llu", &v);
    printf("%llu\n", (llu)solve((uint64_t)v));
    return 0;
}

uint64_t solve(uint64_t v)
{
    std::array<stats, 24> ss = {};
    ss[0] = stats{0, 0, 0, 0, 0, 0};
    ss[1] = stats{0, 1, 0, 0, 0, 0};

    size_t idx = 2;
    do
    {
        auto &curr = ss[idx];
        const auto &prev1 = ss[idx - 1];
        const auto &prev2 = ss[idx - 2];

        curr.digit = v % 10;
        v /= 10;

        if (curr.digit == 0)
        {
            curr.zz_eq = prev1.zz_eq + prev1.nn_eq;
            curr.zz_gt = prev1.zz_gt + prev1.zn + prev1.nn_gt;
            curr.zn = 0;
            curr.nn_eq = 0;
            curr.nn_gt = 0;
        }
        else
        {
            curr.zz_eq = 0;
            curr.zz_gt = 0;
            curr.zn = 2 * (prev1.zz_gt + prev1.zn + prev1.nn_gt) + prev1.zz_eq + prev1.nn_eq;
            curr.nn_eq = 0;
            curr.nn_gt = ((curr.digit - 1) / 2) * (2 * (prev1.zz_gt + prev1.zn + prev1.nn_gt) + prev1.zz_eq + prev1.nn_eq);

            if (curr.digit % 2 == 0)
            {
                curr.nn_eq += prev1.zz_eq + prev1.nn_eq;
                curr.nn_gt += prev1.zz_gt + prev1.zn + prev1.nn_gt;
            }

            if (curr.digit == 1)
            {
                curr.nn_gt += ((9 - prev1.digit) / 2) * (2 * (prev2.zz_gt + prev2.zn + prev2.nn_gt) + prev2.zz_eq + prev2.nn_eq);
                if (prev1.digit % 2 == 0)
                {
                    curr.nn_eq += prev2.zz_eq + prev2.nn_eq;
                    curr.nn_gt += prev2.zz_gt + prev2.zn + prev2.nn_gt;
                }
            }
        }


        idx += 1;
    } while (v > 0);

    const auto &last = ss[idx - 1];
    return 2 * (last.zn + last.nn_gt) + last.nn_eq;
}