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
#include <bits/stdc++.h>
using namespace std;

string liczby[200000];

int czy_pref_wiek(int a, int b, int r){
	for(int i=0; i<r; i++){
		if(liczby[a][i]>liczby[b][i])
			return 0;
		if(liczby[a][i]<liczby[b][i])
			return 1;
	}
	return 2;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> liczby[i];
	}
	long long wynik=0;
	int a, b;
	for(int i=1; i<n; i++){
		a=liczby[i-1].size();
		b=liczby[i].size();
		int czy=czy_pref_wiek(i, i-1, min(b, a));
		if (a>=b && czy==0){
			for(int j=0; j<a-b; j++){
				liczby[i]+='0';
			}
			wynik+=a-b;
		} else {
			if (a>=b){
				if (czy==1){
					for(int j=0; j<a-b+1; j++){
						liczby[i]+='0';
					}
					wynik+=a-b+1;	
				}
				if (czy==2){
					if(a==b){
						liczby[i]+='0';
						++wynik;
					} else {
						int kon=a-1;
						while (liczby[i-1][kon]=='9' && kon>b-1){
							kon--;
						}
						if (kon==b-1){
							for(int j=0; j<a-b+1; j++){
								liczby[i]+='0';
							}
							wynik+=a-b+1;
						} else {
							for(int j=b; j<kon; j++){
								liczby[i]+=liczby[i-1][j];
							}
							liczby[i]+=liczby[i-1][kon]+1;
							for(int j=kon+1; j<a; j++){
								liczby[i]+='0';
							}
							wynik+=a-b;
						}
					}
				}
			}
		}
	}
	cout << wynik << "\n";
//	cout << "lol\n";
//	for(int i=0; i<n; i++){
//		cout << liczby[i] << "\n";
//	}
}