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
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

char buf1[1000050];
char buf2[1000050];

void readn(char* tab, int& n) {
    scanf("%s", tab);
    char* p = tab;
    while (*p) {
        *p -= '0';
        p++;
    }
    n = (int) (p - tab);
    *p = -1;
}

void debugprint(char* tab, int n, int& zerostart, int& zeroend) {
    if (zeroend > zerostart)
        memset(&tab[zerostart], 0, zeroend - zerostart);
    zerostart = -1;
    zeroend = -1;
    for (int j = 0; j < n; j++)
        putchar(tab[j] + '0');
    printf("\n");
}
#define debugprint(...)

int main() {
    //freopen("/home/paul/Documents/cpp/algo/blah/.test/test.txt", "r", stdin);
    int n;
    scanf("%i", &n);
    char* cur = buf1;
    int curn;
    char* last = buf2;
    int lastn = 0;
    int lastzerostart = -1, lastzeroend = -1;
    long long int res = 0;
    readn(last, lastn);
    for (int i = 1; i < n; i++) {
        debugprint(last, lastn, lastzerostart, lastzeroend);
        readn(cur, curn);
        if (curn > lastn) {
            std::swap(last, cur);
            lastn = curn;
            lastzerostart = lastzeroend = -1;
            continue;
        }
        int j = 0;
        while (true) {
            if (j >= lastzerostart && j < lastzeroend) {
                last[j] = 0;
                ++lastzeroend;
            }
            if (cur[j] != last[j] || cur[j] == -1)
                break;
            j++;
        }
        int add_zeros = 0;
        if (cur[j] == -1) {
            // try to increment last one
            bool success = false;
            for (int k = lastn - 1; k >= j; --k) {
                if (k >= lastzerostart && k < lastzeroend) {
                    last[k] = 0;
                    --lastzeroend;
                }
                if (last[k] == 9) {
                    last[k] = 0;
                    continue;
                }
                last[k]++;
                success = true;
                break;
            }
            if (success) {
                // we succeeded! - we only need to add the amount of digits
                res += lastn - j;
                continue;
            } else {
                // we failed, we'll need to zero pad+1
                add_zeros = 1;
            }
        }
        if (cur[j] < last[j]) {
            add_zeros = 1;
        }
        // just zero-pad it
        std::swap(last, cur);
        lastn += add_zeros;
        lastzerostart = curn;
        lastzeroend = lastn;
        res += lastn - curn;
    }
    debugprint(last, lastn, lastzerostart, lastzeroend);
    printf("%lli\n", res);
    return 0;
}