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

using namespace std;


int getCase(char *curr, int currLen, char *next, int nextLen) {
    if (nextLen > currLen) {
        return 1; // next number longer (and greater) than curr number
    }
    char *cr = curr;
    char *nx = next;
    while (*nx) {
        if (*nx < *cr) {
            return 2; // next number shorter and smaller lexicografically than curr number
        }
        if (*nx > *cr) {
            return 3; // next number shorter and greater lexicografically than curr number
        }
        cr++;
        nx++;
    }
    return 4; // next number is a prefix of curr number
}

char curr[300000];

int main() {
    int n;
    scanf("%d", &n);

    long long result = 0;
    scanf("\n%s", curr);
    int currLen = strlen(curr);
    for (int i = 1; i < n; i++) {
        char next[20];
        scanf("\n%s", next);
        int nextLen = strlen(next);
        int caseNo = getCase(curr, currLen, next, nextLen);
        switch (caseNo) {
            case 1:
                currLen = nextLen;
                memcpy(curr, next, currLen);
                break;
            case 2:
                currLen++;
            case 3:
                result += currLen - nextLen;
                memcpy(curr, next, nextLen);
                memset(curr + nextLen, '0', currLen - nextLen);
                break;
            case 4:
                result += currLen - nextLen;
                int j = currLen - 1;
                while (j >= nextLen && curr[j] == '9') {
                    curr[j] = '0';
                    j--;
                }
                if (j >= nextLen) {
                    curr[j]++;
                } else {
                    result++;
                    currLen++;
                    curr[currLen - 1] = '0';
                }
                break;
        }
    }

    printf("%lld\n", result);

    return 0;
}