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

char input[200010][16];//length max is 9+6
int n=0;

int modify(int idx){
    int added=0;
    
    int previous_prefix=0;//1 - previous has bigger prefix; -1 - previous has smaller prefix
    
    int i=0;
    while(true){
        if(input[idx][i]==0){
            //if first number finished
            //and (second number is longer or was already larger, so even if length is the same, it is bigger)
            if(previous_prefix==1||input[idx+1][i]!=0)
                return 0;//no modifications required
            
            //both numbers were the same or even second seems to be smaller and their length is the same
            //add '0' to the end of second number
            
            input[idx+1][i]='0';
            return 1;
        }
    
        if(input[idx+1][i]==0){
            //if second number just finished, but first not finished yet
            
            if(previous_prefix==1){
                //previous has bigger prefix - just fill the rest with 0s
                
                do{
                    input[idx+1][i]='0';
                    added++;
                    i++;
                }while(input[idx][i]);
                return added;
            }
            
            if(previous_prefix==0){
                //if two prefixes are the same till now
                //but previous number ends with 99999...
                //numer must be filled with 0 (with additional 0 on the and) to make it larger - the same can be achieved with
                //simulating that previous prefix was smaller
                
                bool only_9s=true;
                
                for(int j=i;input[idx][j];j++){
                    if(input[idx][j]!='9'){
                        only_9s=false;
                        break;
                    }
                }
                
                if(only_9s)
                    previous_prefix=-1;
            }
            
            if(previous_prefix==-1){
                //previous has smaller prefix - just fill the rest with 0s and add additional 0 to make number longer
                do{
                    input[idx+1][i]='0';
                    added++;
                    i++;
                }while(input[idx][i]);
                input[idx+1][i]='0';
                added++;                
                return added;
            }
            
            //now we know that second number just finished, prefixes are the same till now
            //and first number does not finish with 999...
            
            //just scanf numer and then print it back to the buffer but increased by 1
            int suffix_val;
            sscanf(&input[idx][i],"%d",&suffix_val);
            suffix_val+=1;
            
            for(int j=i;input[idx][j];j++)
                added++;
            
            char buf[16];
            memset(buf,0,sizeof(buf));
            sprintf(buf,"%010d",suffix_val);
            
            memcpy(&input[idx+1][i],buf+(10-added),added);
            
            return added;
        }

        if(previous_prefix==0){
            if(input[idx][i]>input[idx+1][i])
                previous_prefix=-1;
            else if(input[idx][i]<input[idx+1][i])
                previous_prefix=1;
        }
        
        i++;
    }
    
}

int main(){
    scanf("%d",&n);
        
    for(int i=0;i<n;i++){
        scanf("%s",&input[i][0]);
    }
    
    n--;
    
    int added=0;
    for(int i=0;i<n;i++)
        added+=modify(i);

    //for(int i=0;i<=n;i++)
    //    printf("%2d: <%s>\n",i,&input[i][0]);
    
    printf("%d\n",added);
}