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
145
146
147
#include <iostream>
#include <cstdint>
#include <cstdio>
#include <vector>
#define PRINT(ARG) std::cout << #ARG << " = " << ARG << std::endl;
typedef int32_t int32;
typedef int8_t int8;
const char  SPACE = 0;
const char  ZERO  = 48;
const char  NINE  = 57;
const int32 MAX_N = 200001;
const int32 STRLEN = 12;

int32 n, changes;
bool greater, equal;
struct Number{
    char str[STRLEN];
    int32 places=0, nines=0, endval=0;
    void copy(Number n){
        places = n.places;
        nines = n.nines;
        endval = n.endval;
    }
    void increment(){
        endval=(endval+1)%10;
        if(endval == 0) {nines++;} 
        if(nines == places){ places++; nines=0; endval=0; }
    }
}; 
std::vector<Number> a = std::vector<Number>(MAX_N);

int main(){
    std::ios_base::sync_with_stdio(0);
    std::cin >> n; 
    std::cin.getline(nullptr, 0);
    for(int32 i=0; i<n; i++){ std::cin.getline(a[i].str, STRLEN );  } 
    for(int32 i=1; i<n; i++){ 
        equal = true; greater = false;
        for(int32 j=0; j<STRLEN; j++){
            if(a[i].str[j] == SPACE || a[i-1].str[j] == SPACE ){
                if(a[i].str[j] != SPACE && a[i-1].str[j] == SPACE){ // longer

                    if(greater){
                        int32 iter = 0;
                        while(a[i].str[j+iter] != SPACE) {iter++;}
                        int32 temp = a[i-1].places - iter;
                        if(temp > 0){ a[i].places = temp; }
                    }else if(equal){
                        int32 iter = 0;
                        int32 fNineIndex = a[i-1].places - a[i-1].nines-1;
                        int32 compVal = 0;
                        while(a[i].str[j+iter] != SPACE) {
                            if(iter = a[i-1].places-1){
                                compVal = a[i-1].endval; 
                            }else if(iter >= fNineIndex){
                                compVal = 9; 
                            }else if(iter > a[i-1].places-1){
                                compVal = -1;
                            }
                            if(equal && compVal + ZERO != a[i].str[j+iter]){
                                equal = false;
                                if(compVal+ZERO > a[i].str[j+iter]){ greater = false;} 
                                else{greater = true;}
                            }
                        }
                        int32 freeslots = a[i-1].places - iter;
                        freeslots = (freeslots > 0 ? freeslots : 0);
                        if(equal){
                            a[i].places = freeslots;
                            a[i].nines  = (a[i-1].nines >= freeslots-1 ? freeslots : a[i-1].nines);
                            a[i].endval = a[i-1].endval;
                            a[i].increment();
                        }else if(greater){
                            a[i].places = freeslots; 
                        }else{
                            a[i].places = freeslots+1; 
                        }
                    }else{
                        int32 iter = 0;
                        while(a[i].str[j+iter] != SPACE) iter++;
                        int32 temp = a[i-1].places - iter;
                        if(temp > 0){ a[i].places = temp; }
                        a[i].places++;
                    } 
                }else if(a[i].str[j] == SPACE && a[i-1].str[j] == SPACE){ //same
                    if(greater){ 
                        a[i].places = a[i-1].places;
                    }else if(equal){ 
                        a[i].copy(a[i-1]);
                        a[i].increment();
                    }else{
                        a[i].places = a[i-1].places +1;
                    } 
                }else{ // shorter
                    if(greater){
                        int32 iter = 0;
                        while(a[i-1].str[j+iter] != SPACE) iter++;
                        a[i].places = a[i-1].places + iter; 

                    }else if(equal){
                        int32 iter = 0;
                        while(a[i-1].str[j+iter] != SPACE) iter++;

                        if((a[i-1].nines+1 == a[i-1].places && a[i-1].endval == 9) 
                                || (a[i-1].places == 0)){
                            bool flag = true;
                            for(int32 k=0; k<iter; k++){ 
                                if(a[i-1].str[j+k] != NINE){ flag = false; break;}
                            }
                            if(flag){
                                for(int32 k=0; k<iter; k++){ a[i].str[j+k] = ZERO;}//rewr
                                changes+=iter;
                                a[i].places = a[i-1].places+1;
                            }else{
                                bool flag2 = true;
                                for(int32 k=iter-1; k>=0; k--){ 
                                    if(flag2 && a[i-1].str[j+k] == NINE){
                                        a[i].str[j+k] = ZERO; 
                                    }else{
                                        a[i].str[j+k]=a[i-1].str[j+k];
                                        if(flag2){a[i].str[j+k]++; flag2=false;}
                                    } 
                                }
                                changes+=iter;
                                a[i].places = a[i-1].places;
                            } 
                        }else{
                            a[i].copy(a[i-1]);
                            for(int32 k=0; k<iter; k++){ a[i].str[j+k] = a[i-1].str[j+k];}//rewr
                            changes+=iter;
                            a[i].increment();
                        }
                    }else{
                        int32 iter = 0;
                        while(a[i-1].str[j+iter] != SPACE) iter++;
                        a[i].places = a[i-1].places + iter+1; 
                    }
                }
                break;
            } 
            if(equal && a[i].str[j] >  a[i-1].str[j]){ greater = true;}
            if(equal && a[i].str[j] != a[i-1].str[j]){ equal = false; }
        }  
        changes += a[i].places;
    } 
    std::cout << changes;
}