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
#pragma GCC optimize("O3,unroll-loops")
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
    // Ekstremalnie szybkie wejście/wyjście
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string A, B, C;
    // Wczytujemy od razu 3 stringi, bo w wejściu nie ma osobnej liczby N
    if (!(cin >> A >> B >> C)) return 0;

    int n = A.length();

    // Tablice do przechowywania "wymagań" (R) i "produkcji" (L) przeniesień dla każdej cyfry
    vector<int> L(n, -1);
    vector<int> R(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 diff = a + b - c;

        // Mapowanie różnicy na przeniesienia
        if (diff == 0) {
            L[i] = 0; R[i] = 0;
        } else if (diff == -1) {
            L[i] = 0; R[i] = 1;
        } else if (diff == 10) {
            L[i] = 1; R[i] = 0;
        } else if (diff == 9) {
            L[i] = 1; R[i] = 1;
        } else {
            L[i] = -1; R[i] = -1; // Stan nieważny (łamie ciąg)
        }
    }

    long long total_valid_pairs = 0;
    int start = 0;

    // Przeszukiwanie tablicy i wykrywanie poprawnych bloków
    while (start < n) {
        if (R[start] == -1) {
            start++;
            continue;
        }

        int end = start;
        long long count_L0 = 0;

        while (end < n) {
            // Jeśli lewy kraniec wypuszcza przeniesienie 0, potencjalnie zaczyna poprawny przedział
            if (L[end] == 0) {
                count_L0++;
            }
            // Jeśli prawy kraniec wymaga przeniesienia 0, zamyka wszystkie otwarte poprawne przedziały
            if (R[end] == 0) {
                total_valid_pairs += count_L0;
            }

            // Sprawdzanie czy sąsiadująca z lewej cyfra pasuje do wyprodukowanego przez nas przeniesienia
            // Pamiętamy, że przeniesienie idzie "w lewo" (czyli od indeksu end+1 do end)
            if (end + 1 < n && R[end + 1] != -1 && L[end + 1] == R[end]) {
                end++;
            } else {
                break; // Łańcuch dopasowań przeniesień został zerwany
            }
        }

        // Skok za sprawdzony blok
        start = end + 1;
    }

    // Wypisanie wyniku
    cout << total_valid_pairs << "\n";

    return 0;
}