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
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <cstdio>
#include <cstring>
#include <set>
#include <unordered_set>

typedef std::tuple<long, long, bool> Stan;

int main() {
    char a[1'000'010];
    char b[1'000'010];
    char c[1'000'010];
    //char r[1'000'010];
    //char s[1'000'010];

    scanf("%s", a);
    scanf("%s", b);
    scanf("%s", c);

    int dlugosc = strlen(a);
    std::set<Stan> stany_poprzednie;
    std::set<Stan> stany_biezace;
    stany_poprzednie.insert({0, 0, false});

    for (int i=0; i<dlugosc; ++i) {
        a[i] -= '0';
        b[i] -= '0';
        c[i] -= '0';
        for (const Stan &stan: stany_poprzednie){
            long stan_wynik = std::get<0>(stan);
            long stan_poczatkow = std::get<1>(stan);
            bool stan_przeniesienie = std::get<2>(stan);
            //fprintf(stderr, " %ld, %ld, %d\n", stan_wynik, stan_poczatkow, stan_przeniesienie);
            if (a[i] + b[i] == c[i]){
                if (!stan_przeniesienie) {
                    stany_biezace.insert({
                        stan_wynik + stan_poczatkow + 1,
                        stan_poczatkow + 1,
                        false,
                    });
                } else {
                    stany_biezace.insert({
                        stan_wynik + 1,
                        1,
                        false,
                    });
                }
            }
            else if (a[i] + b[i] == c[i] + 10 && stan_przeniesienie) {
                stany_biezace.insert({
                    stan_wynik + stan_poczatkow,
                    stan_poczatkow,
                    false,
                });
            }
            else if (a[i] + b[i] + 1 == c[i]) {
                if (!stan_przeniesienie) {
                    stany_biezace.insert({
                        stan_wynik,
                        stan_poczatkow + 1,
                        true,
                    });
                } else {
                    stany_biezace.insert({
                        stan_wynik,
                        1,
                        true,
                    });
                }
            }
            else if (a[i] + b[i] + 1 == c[i] + 10 && stan_przeniesienie) {
                stany_biezace.insert({
                    stan_wynik,
                    stan_poczatkow,
                    true,
                });
            }
            else {
                stany_biezace.insert({
                    stan_wynik,
                    0,
                    false,
                });
            }
        }
        //fprintf(stderr, "%d + %d = %d\n", a[i], b[i], c[i]);
        std::swap(stany_biezace, stany_poprzednie);
        stany_biezace.clear();
    }

    for (const Stan &stan: stany_poprzednie){
        long stan_wynik = std::get<0>(stan);
        printf("%ld", stan_wynik);
        break;
    }

    /*



    for (int i=0; i<dlugosc; ++i) {
        for (int j=i; j<dlugosc; ++j) {
            int p=0;
            int rowne = 1;
            for (int k=j; i<=k;--k) {
                s[k] = a[k] + b[k] + p;
                p = (10 <= s[k]);
                if (p) {
                    s[k] -= 10;
                }
                if (s[k] != c[k]) {
                    rowne = 0;
                    break;
                }
            }
            if (rowne && p==0) {
                //for (int k=i; k<=j;++k) { putchar(a[k]+'0'); } putchar('\n');
                //for (int k=i; k<=j;++k) { putchar(b[k]+'0'); } putchar('\n');
                //for (int k=i; k<=j;++k) { putchar(c[k]+'0'); } putchar('\n');
                for (int k=i; k<=j;++k) { putchar(r[k]); } putchar('\n');
                //putchar('\n');
            }
        }
    }
    */
}