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
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
    // Optymalizacja operacji wejścia/wyjścia
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string A, B, C;
    if (!(cin >> A >> B >> C)) return 0;

    int n = A.length();
    
    // req[i] to wymagane przeniesienie z prawej strony (z i+1), aby uzyskać cyfrę C[i].
    // out[i] to wytworzone przeniesienie na lewą stronę (do i-1), zakładając że req[i] zostało spełnione.
    // -1 oznacza, że z żadnym przeniesieniem (0 ani 1) nie da się otrzymać C[i].
    vector<int> req(n, -1);
    vector<int> out(n, -1);

    for (int i = 0; i < n; ++i) {
        int a = A[i] - '0';
        int b = B[i] - '0';
        int c = C[i] - '0';

        int s0 = a + b;
        int s1 = a + b + 1;

        if (s0 % 10 == c) {
            req[i] = 0;
            out[i] = s0 / 10;
        } else if (s1 % 10 == c) {
            req[i] = 1;
            out[i] = s1 / 10;
        }
    }

    long long total_pairs = 0;
    int i = 0;
    
    // Poszukiwanie maksymalnych bloków, w których przeniesienia się zgadzają
    while (i < n) {
        if (req[i] == -1) {
            i++;
            continue;
        }

        int j = i;
        long long valid_starts = 0;

        // Sprawdzanie dla pojedynczego indeksu
        if (out[i] == 0) valid_starts++;
        if (req[i] == 0) total_pairs += valid_starts;

        // Rozszerzanie bloku, póki wymagane przeniesienie zgadza się z wytworzonym przez sąsiada
        while (j + 1 < n && req[j] == out[j + 1] && req[j + 1] != -1) {
            j++;
            if (out[j] == 0) valid_starts++;
            if (req[j] == 0) total_pairs += valid_starts;
        }

        i = j + 1; // Zakończenie bloku i przejście dalej
    }

    cout << total_pairs << "\n";

    return 0;
}