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
//Michał Hołubowicz
#include <bits/stdc++.h>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
unsigned long long zam,ien,wynik,suma;
int dl1,dl2,a;
string tab[200003];
int t[200003];
int main()
{
    cin>>a;
    if(a==1)
    {
        cout<<0;
        return 0;
    }
    cin>>tab[1];
    t[1]=tab[1].size();
    for(int i=2; i<=a; i++)
    {
        cin>>tab[i];
        if(tab[i]==tab[i-1]) {tab[i]+='0'; wynik++; }
        else
        {
            t[i]=tab[i].size();
            zam=atoi(tab[i-1].c_str());
            ien=atoi(tab[i].c_str());
            dl1=tab[i-1].size();
            if(zam>ien)
            {
                dl2=tab[i].size();
                for(int j=0; j<dl2; j++)
                {
                    dl2=tab[i].size();
                    if(tab[i][j]>tab[i-1][j])
                    {
                        while(dl1>dl2)
                        {
                            tab[i]+='0';
                            wynik++;
                            dl2++;
                        }
                        break;
                    }
                    else if(tab[i][j]<tab[i-1][j])
                    {
                        while(dl1>=dl2)
                        {
                            tab[i]+='0';
                            wynik++;
                            dl2++;
                        }
                        break;
                    }
                    else if(tab[i][j]==tab[i-1][j] && dl2-1==j)
                    {
                        if(dl1>dl2)
                        {
                            if(tab[i-1][dl1-1]!='9')
                            {
                                while(dl1>dl2)
                                {
                                    tab[i]+=tab[i-1][dl2];
                                    wynik++;
                                    dl2++;
                                }
                                tab[i][dl2-1]+=1;
                            }
                            else
                            {
                                int f=dl1;
                                f-=2;
                                while(tab[i-1][f]=='9' && f>=t[i]) f--;
                                if(f>=t[i] && tab[i-1][f]!='9')
                                {
                                    if(f>t[i]) for(int v=t[i]; v<=f; v++)
                                        {
                                            if(v<dl2) tab[i][v]=tab[i-1][v];
                                            else
                                            {
                                                tab[i]+=tab[i-1][v];
                                                wynik++;
                                            }
                                        }
                                    tab[i]+=tab[i-1][f]+1;

                                    if(f+1!=dl1)for(int v=f+1; v<dl1; v++) tab[i]+='0';

                                }
                                else
                                {
                                    for(int v=t[i]; v<=dl1; v++)
                                    {
                                        if(v<dl2)  tab[i][v]='0';
                                        else
                                        {
                                            tab[i]+='0';
                                            wynik++;
                                        }
                                    }
                                }
                            }
                        }
                        else if(dl1==dl2)
                        {
                            tab[i]+='0';
                            wynik++;
                        }

                    }
                }
            }
        }
    }
    cout<<wynik<<endl;
}