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

#include <cstdlib>

using namespace std;

int main() {
    int n, al, bl, i, j, cmp;
    long long ile=0;
    string a,b;
    
    cin >> n;
    cin >> a;
    al = a.length();
    bool krotkie = true;
    int ileZer = 0;
    for(i=1;i<n;i++){
        cin >> b;
        bl = b.length();

        if(krotkie){
        
            if(bl>al){
                // ok
            }else if( bl == al ){
                cmp = b.compare(a);
                if(cmp<=0){
                    // to samo lub za małe cyfry, zatem dopisuje zero
                    b+='0'; bl++; ile++;
                }
            }else if( bl < al ){
                cmp = b.compare(0, bl, a, 0, bl);
                if(cmp>0){
                    // b lepszy początek, więc uzupełniam zerami
                        b.append(al-bl, '0');
                    ile+= al-bl; bl+= al-bl;
                }
                if(cmp==0){
                    // ten sam początek, spr, czy 99999
                    j=al-1;
                    while(j>=bl && a[j]=='9')
                        j--;
                    if(j>=bl){
                        // istnieje cyfra < 9
                        ile+= al-bl;
                        b=a;
                        bl=al;
                        b[j]++;
                        // reszte 9 zamieniam na 0
                        j++;
                        while(j<bl)
                            b[ j++ ] = '0';
                    }else{
                        // uzupełniam zerami + jeszcze jedno
                            b.append(al-bl+1, '0');  ile+= al-bl+1; bl+= al-bl+1;
                    }
                }
                if(cmp<0){
                    // b gorszy początek, więc uzupełniam zerami + jeszcze jedno
                        b.append(al-bl+1, '0'); ile+= al-bl+1; bl+= al-bl+1; 
                }

            }

            a=b;
            al=bl;
            
            if(al>20){
                krotkie = false;
                a = a.substr(0,9);
                ileZer = al-9;
            }
            
        }else{
            cmp = b.compare(0, bl, a, 0, bl);
            if(cmp == 0){
                ile += 9-bl + ileZer;
            }
            if(cmp > 0){
                a = b;
                a.append(9-bl, '0');
                ile += 9-bl + ileZer;
            }
            if(cmp < 0){
                a = b;
                a.append(9-bl, '0');
                ileZer++;
                ile += 9-bl + ileZer;
            }
        }
    }
    cout << ile << endl;
    return 0;
}