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
#include <cstdio>
#include <algorithm>
#include <assert.h>
#define MAXC 200020
//PA2018
//Nowy kontrakt
//Autor rozwiązania: Jan Horodecki

enum Ord{
   LT=1,
   EQ=0,
   GT=2
};

int main(){
   int n,k,it;
   Ord porz;
   long long wyn = 0,c, k_prev = 0;
   char _a[MAXC],_b[MAXC];
   char *a =_a, *b = _b;
   bool same9;
   scanf("%d",&n);
   scanf(" %s",a);
   for(int i=1;i<n;i++){
      scanf(" %s",b);
      k = c = 0;
      porz = EQ;
      same9 = true;
      if(k_prev >= 20){
         while(a[k]!='\0'){
            if(b[k]!='\0'){
               if( porz != EQ ){
                  k++;
                  continue;
               }
               if(a[k]<b[k])
                  porz = LT;
               if(a[k]>b[k])
                  porz = GT;
            }else{
               c++;
               if(porz != EQ){
                  b[k] = '0';
               }else{
                  b[k] = a[k];
               }
               b[k+1] = '\0';
            }
            k++;
         }
         while(b[k]!='\0')
            k++;
         if(porz == GT){
            c += k_prev - k + 1;
            k += k_prev - k + 1;
         }else{
            c += k_prev - k;
            k += k_prev - k;
         }
         wyn += c;
      }else{
         while(a[k]!='\0'){
            if(b[k]!='\0'){
               if( porz != EQ ){
                  k++;
                  continue;
               }
               if(a[k]<b[k])
                  porz = LT;
               if(a[k]>b[k])
                  porz = GT;
            }else{
               wyn++;
               c++;
               if(porz != EQ){
                  b[k] = '0';
               }else{
                  b[k] = a[k];
               }
               if(b[k]!='9')
                  same9 = false;
               b[k+1] = '\0';
            }
            k++;
         }
         if(b[k]=='\0'){
            if(porz == GT){
               wyn++;
               c++;
               b[k] = '0';
               b[k+1] = '\0';
               k++;
            }
            if(porz == EQ){
               if(c == 0){
                  b[k] = '0';
                  b[k+1] = '\0';
                  wyn++;
                  c++;
                  k++;
               }else if(same9){
                  it = k - c ; 
                  while(it<=k){
                     b[it++] = '0';
                  }
                  b[it] = '\0';
                  wyn++;
                  c++;
                  k++;
               }else{
                  it = k-1;
                  while(true){
                     if(b[it]!='9'){
                        b[it]++;
                        break;
                     }else{
                        b[it] = '0';
                        it--;
                     }
                  }
               }
            }
         }
         if(k>=20){
            b[k-c] = '\0';
         }
      }

      k_prev = k;

      std::swap(a,b);
   }
   printf("%lld",wyn);
}