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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
// O(WYNIK) ... conajmniej 
// Jakby było więcej czasu to bym doklepał optymalizacje z konczącymi 0 i by stykło na 10pkt
// a tak to tak O słabo OOOO

#include <iostream>
#include <utility>
#include <list>
#include <stack>

using namespace std;

int n;

list<int> get_digits(long long num);
pair<int, list<int>> find_needed(list<int> last, list<int> current);


int main() {
    cin >> n;
    long long all_added = 0;
    int d;
    cin >> d, n--;
    list<int> last_max = get_digits(d);
    while (n--) {
        cin >> d;      
       
        pair<int, list<int>> result = find_needed(last_max, get_digits(d));
        last_max = result.second;

        //cout << result.first;
        //print(result.second);
        //cout << endl;
        all_added += result.first;
    }
    cout << all_added << endl;
}

bool all_nines(const list<int> &digits);
bool is_bigger(const list<int> &a, const list<int> &b);


pair<int, list<int>> find_needed(list<int> last, list<int> current) {
    if (is_bigger(current, last)) {
        return make_pair(0, current);
    } else {
        int added = 0;
        list<int> result = list<int>();
        while (!current.empty() && !last.empty()
            && current.front() == last.front()) {
            int first = current.front();
            result.push_back(first);
            current.pop_front();
            last.pop_front();
        }
        // ta sama liczba - dopisujemy 0
        if (last.empty()) {
            result.push_back(0);
            added += 1;
            return make_pair(added, result);
        }
        // liczba nowa jest podciągiem poprzedniej - musimy dopisać jak najmniejsza
        if (current.empty()) {
            // same 9 - przepełnienie
            if (all_nines(last)) {
                while (!last.empty()) {
                    last.pop_front();
                    result.push_back(0);
                    added += 1;
                }
                result.push_back(0);
                added += 1;
                return make_pair(added, result);
            }
            stack<int> retrive = stack<int>(); // wkładamy od końca liczby
            // sytuacja normalna
            // 9 przepisujemy jako 0 _ przepełnienie
            while (last.back() == 9) {
                retrive.push(0);
                last.pop_back();
            }
            // nie 9 zwiększamy
            retrive.push(last.back() + 1), last.pop_back();
            // reszta jak przedtem
            while (!last.empty()) {
                retrive.push(last.back()), last.pop_back();
            }

            while (!retrive.empty()) {
                result.push_back(retrive.top());
                retrive.pop();
                added += 1;
            }

            return make_pair(added, result);
        } 
        // w pozostałym przypadku - liczby się różnią na poczatkowych pozycjach - dopisyjemy jak najmniej zer
        bool first_greater = current.front() > last.front();
        while (!current.empty()) {
            result.push_back(current.front());
            current.pop_front();
            last.pop_front();
        }
        while (!last.empty()) {
            result.push_back(0);
            added += 1;
            last.pop_front();
        }
        if (!first_greater) {
            result.push_back(0);
            added +=1;
        }
        return make_pair(added, result);
    }
}

bool all_nines(const list<int> &digits) {
    for (auto it = digits.begin(); it != digits.end(); ++it) {
        if (*it != 9) {
            return false;
        }
    }
    return true;
}

list<int> get_digits(long long num) {
    list<int> result = list<int>();
    while (num > 0) {
        result.push_front(num % 10);
        num /= 10;
    }
    return result;
}

bool is_bigger(const list<int> &a, const list<int> &b) {
    if (a.size() != b.size()) {
        return a.size() > b.size();
    }
    for (auto ait = a.begin(), bit = b.begin(); ait != a.end() && bit != b.end(); ait++, bit++) {
        if (*ait != *bit) {
            return *ait > *bit; 
        }
    }
    return false; // równe
}