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
#include <bits/stdc++.h>
#define MX 200005
using namespace std;
int n, len[MX], last[MX];
string s[MX], ostatnie[MX];
long long res;
bool plusjeden(int i)
{	int ilemoge = len[i - 1] - s[i].size();
//	cout << i << " " << ilemoge << endl;
	for(int j = 0; j < min(ilemoge, 20); j++)
	{	if(ostatnie[i - 1][j] < '9')
		{	//cout << "XD" << endl;
			len[i] = len[i - 1];
			ostatnie[i] = ostatnie[i - 1];
			ostatnie[i][j]++;
			s[i] = s[i - 1];
			if(len[i] - j <= 10)
				s[i][len[i] - j - 1] = ostatnie[i][j];
			for(int k = 0; k < j; k++)
			{	ostatnie[i][k] = '0';
				if(len[i] - k <= 10)
					s[i][len[i] - k - 1] = ostatnie[i][k];
			}
			return 1;
		}
	}
	return 0;
}
int main()
{	cin >> n;
	for(int i = 1; i <= n; i++)
	{	cin >> s[i];
		len[i] = s[i].size();
		if(len[i] > len[i - 1] || i == 1)
		{	ostatnie[i] = s[i];
			reverse(ostatnie[i].begin(), ostatnie[i].end());
			continue;
		}
		int val = 0, when = 0;
		for(int j = 0; j < len[i]; j++)
		{	if(s[i][j] == s[i - 1][j])
				continue;
			if(s[i][j] > s[i - 1][j])
				val = 1;
			else val = -1;
			when = j;
			break;
		}
		bool przepisz = 0;
		if(val == 1)
		{	res += len[i - 1] - len[i];
			len[i] = len[i - 1];
		}
		else if(val == 0)
		{	res += len[i - 1] - len[i];
			if(plusjeden(i))
				goto kon;
			res++;
			len[i] = len[i - 1] + 1;
		}
		else
		{	res += len[i - 1] - len[i] + 1;
			len[i] = len[i - 1] + 1;
		}
		if(!przepisz)
		{	while(s[i].size() < min(10, len[i]))
				s[i] += '0';
			for(int i = 1; i <= min(20, (int)(len[i] - s[i].size())); i++)
				ostatnie[i] += '0';
			if(ostatnie[i].size() < min(20, (int)s[i].size()))
			{	int k = s[i].size() - 1;
				while(k >= 0 && ostatnie[i].size() < 20)
				{	ostatnie[i] += s[i][k];
					k--;
				}
			}
		}
		kon:;
	}
	//for(int i = 1; i <= n; i++)
	//	cout << s[i] << " " << len[i] <<"\n";
	cout << res; 
}