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
#include <cstdio>
#include <cstring>
int n,x,min=0,ileCyfr=1,maxCyfr,dlgA;
long long dopisanych=0LL;
char last[35],a[20];

int main(){
    for(int i=0;i<30;i++)
        last[i] = '0';
    scanf(" %d",&n);
    for(int z=0; z<n; z++){
        scanf(" %s",&a);
        dlgA = strlen(a);
//        printf("%s\n",a);
        int i;
        for(i=0; i<dlgA; i++){
            //========= jesli cyfra liczby na danej pozycji ma mniejszy poczatek niz minimalna ==============
            if(a[i] < last[i]) {
                //przepisz cala liczbe
                for(int j=i; j<dlgA; j++){
                    last[j] = a[j];
//                    printf("%c",last[j]);
                }
                //dopisz na koncu zero (o cyfre wieksza)
                last[ dlgA ]='0';
                if(ileCyfr < dlgA )
                    ileCyfr = dlgA;
                else {
                    //zapewnij zwiekszyc minimum o jedna cyfre
                    ileCyfr++;
                }
                    //wyzeruj reszte pozycje liczby
                    maxCyfr = ileCyfr;
                    if(maxCyfr > 20)
                        maxCyfr = 20;
                    for(int j=dlgA; j<maxCyfr; j++){
                        last[j] = '0';
//                        printf("0");
                    }

//                printf(" MNIEJ\n");
                //wyjdz z petli bo wiemy co to za  liczba (mniejsza z zerem na koncu) i zakonczylismy jej uzupelnianie
                //last[ileCyfr]=0;
                dopisanych += ileCyfr - dlgA;
//                printf("z:%d - cyfr:%d, dopisanych:%d\n\n",z,ileCyfr,ileCyfr-dlgA);
                break;
            }

            //========== jesli cyfra tej liczby na danej pozycji jest wieksza ========
            if(a[i] > last[i]) {
                //takze przepisz cala liczbe
                for(int j = i; j< dlgA; j++) {
                    last[j] = a[j];
//                    printf("%c",last[j]);
                }
                //reszte uzupelnij zerami do dlugosci liczby minimalnej
                maxCyfr = ileCyfr;
                if(maxCyfr > 20)
                    maxCyfr = 20;
                if(ileCyfr > dlgA)
                    for(int j = dlgA; j<maxCyfr; j++){
                        last[j] = '0';
//                        printf("0");
                    }
                else
                    ileCyfr = dlgA;
//                printf(" WINCYJ\n");

                dopisanych += ileCyfr - dlgA;
//                printf("z:%d - cyfr:%d, dopisanych:%d\n\n",z,ileCyfr,ileCyfr-dlgA);
                break;

            }
//            printf("%c",last[i]);
        }
        if(i == dlgA) {
            // ==== no i najtrudniejszy przypadek, wez to zrob a jestes algorytmistrzem wszechswiata
            //jesli taka sama to dopisz zero na koncu i wsio jedziem dalej
            if(dlgA == ileCyfr) {
                last[dlgA] == '0';
                ileCyfr++;
                dopisanych++;
//                printf("0 ROWNE -> Dalej\n\n");
                continue;

            }

            int maxCyfr;
            int j;
            maxCyfr = ileCyfr;
            if (maxCyfr>20)
                maxCyfr = 20;


            //zwieksz od konca o jeden az bedzie ziaziu
            for( j=maxCyfr-1; j>=dlgA; j--){
                if(last[j]=='9'){
                    last[j] = '0';
                    if( j == dlgA ) {
                        last[maxCyfr] = '0';
                        ileCyfr++;
                    }
//                    printf("0");
                    continue;
                }
                last[j]++;
//                printf("%c",last[j]);
                break;
            }

            dopisanych += ileCyfr - dlgA;

//            printf(" ROWNE\n");
//            printf("z:%d - cyfr:%d, dopisanych:%d\n\n",z,ileCyfr,ileCyfr-dlgA);

        }


    }
    printf("%lld",dopisanych);
    return 0;
}