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

using namespace std;

int compare(string &current, string &prev)
{
    if (prev.size() < current.size())
        return -100;

    return prev.compare(0, current.size(), current);
}

void incrementEnding(string &ending)
{
    bool required = true;
    for (int i = ending.size()-1; required && i>=0; i--)
    {
        if (ending[i] < '9')
        {
            ending[i]++;
            required = false;
        }
        else
        {
            ending[i] = '0';
        }
    }

    if (required)
        ending += '0';
}

int main()
{
    int N;
    string prev = "0";
    string current;

    long long result = 0;

    cin >> N;
    while (prev.size()<16 && N--)
    {
        cin >> current;
        int compareResult = compare(current, prev);

        if (compareResult == -100) // no change required
        {

        }
        else if (compareResult < 0) // prev is smaller
        {
            result += prev.size() - current.size();
            current.resize(prev.size(), '0');
        }
        else if (compareResult > 0) // prev is greater
        {
            result += prev.size() - current.size() + 1;
            current.resize(prev.size() + 1, '0');
        }
        else
        {
            string ending = prev.substr(current.size());
            incrementEnding(ending);
            result += ending.size();
            current += ending;
        }
        prev = current;
    }
    int prevSize = prev.size();
    while (N-- > 0)
    {
        cin >> current;
        int compareResult = compare(current, prev);

        if (compareResult > 0) // prev is greater
        {
            prevSize++;
        }
        result += prevSize - current.size();
    }

    cout << result << endl;

    return 0;
}