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
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <string>
#include <algorithm>
#include <iostream>
#include <stack>
using namespace std;

typedef long long int LL;

LL res;
string a, b, c, sum;
int carry;
LL start = -1, ending = -1, lastNoCarryIdx = -1;
stack<int> carryIdxs;

void closePrevious()
{
    while (!carryIdxs.empty() && carryIdxs.top() >= lastNoCarryIdx)
    {
        carryIdxs.pop();
    }

    ending = min(ending, lastNoCarryIdx);
    if (start != -1 && ending != -1 && ending >= start)
    {
        LL len = ending - start + 1 - carryIdxs.size();
        LL currRes = len * (len + 1) / 2;
        res += currRes;

        //cout << "start: " << start << ", ending: " << ending;
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(NULL);

    cin >> a >> b >> c;

    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    reverse(c.begin(), c.end());
    a += '1';
    b += '1';
    c += '0';

    for (int i = 0; i < a.size(); ++i)
    {
        int correctSum = (a[i] - '0') + (b[i] - '0');
        int lastDigit = correctSum % 10;

        int correctSumWithCarry = correctSum + carry;
        int lastDigitWithCarry = correctSumWithCarry % 10;
        //cout << correctSum << ", c[i]: " << c[i] << endl;

        if (lastDigitWithCarry == (c[i] - '0'))
        {
            if (carry == 0)
            {
                if (start == -1)
                {
                    start = i;
                }
            }

            ending = i;
            carry = correctSumWithCarry / 10;

            if (carry == 0)
            {
                lastNoCarryIdx = i;
            }
            else
            {
                carryIdxs.push(i);
            }
        }
        else if (lastDigit == (c[i] - '0'))
        {
            // domkniecie wczesniejszego
            closePrevious();

            start = ending = i;
            carryIdxs = stack<int>();

            carry = correctSum / 10;

            if (carry == 0)
            {
                lastNoCarryIdx = i;
            }
            else
            {
                carryIdxs.push(i);
            }
        }
        else
        {
            // domkniecie wczesniejszego
            closePrevious();

            start = ending = lastNoCarryIdx = -1;
            carry = 0;
            carryIdxs = stack<int>();
        }
    }

    cout << res << endl;

    return 0;

}