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
85
86
87
88
89
90
91
92
93
94
95
96
#include <iostream>
#include <vector>
#include <utility>

using namespace std;

int debug = 0;

tuple<long long, long long, long long> findLongestValidSegment(const vector<int>& a, 
                            const vector<int>& b, 
                            const vector<int>& c, 
                            int j) {
    int longest_i = -1;
    int carry = 0;

    int blocks_count = 0;
    for (int i = j; i >= 0; --i) {
        int sum = a[i] + b[i] + carry;

        if (sum % 10 == c[i]) {
            carry = sum / 10;
            
            if (carry == 0) {
                longest_i = i;
                blocks_count++;
            }
        } else {
            break;
        }
    }
    if (debug) cout << "blocks_count " << blocks_count << endl;

    long long no_carry_count = 0;
    if (longest_i != -1) {
        for (int i = j; i >= longest_i; i--) {
            if (a[i] + b[i] == c[i]) {
                no_carry_count++;
            }
        }
    }

    return { longest_i, no_carry_count, blocks_count - no_carry_count };
}

int main() 
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    string a, b, c;
    vector<int> x, y, z;

    cin >> a >> b >> c;

    for (char ch : a) {
        x.push_back(ch - '0');
    }

    for (char ch : b) {
        y.push_back(ch - '0');
    }

    for (char ch : c) {
        z.push_back(ch - '0');
    }

    int size = x.size();
    int i = size - 1;
    long long sum = 0;

    while (i >= 0) {
        auto [longest_i, carry_count, blocks_count]= findLongestValidSegment(x, y, z, i);
        if (debug) cout << i << " " << longest_i << " " << carry_count << " " << blocks_count << endl;
        if (longest_i == -1) {
            i--;
        } else {
            sum += carry_count;
            sum += blocks_count;
            if (carry_count > 1) {
                sum += (long long)(((carry_count - 1) * carry_count) / 2);
            }
            if (blocks_count > 1) {
                sum += (long long)(((blocks_count - 1) * blocks_count) / 2);
            }
            if (carry_count > 0 && blocks_count > 0) {
                sum += (long long)(carry_count * blocks_count);
            }
            
            i = longest_i - 1;
        }
    }
    
    cout << sum << endl;

    return 0;
}