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
#include <cstdio>
#include <cstring>
#include <string>

using namespace std;

int main() {
	int n;
	scanf("%d", &n);
	string prev = "0";
	int prev_len = 1;
	long long new_digits = 0;
	for(int i = 0; i < n; ++i) {
		char num[12];
		scanf("%s", num);
		string current = string(num);
		int len = current.length();
		if(len > prev_len) {
			// simply take the new one
			prev = current;
			prev_len = len;
		} else {
			// it can be either prefix, smaller prefix or bigger prefix
			int missing_zeros = 0;
			int k;
			for(k = 0; k < len; ++k) {
				if(current[k] < prev[k]) {
					// need to add a digit
					missing_zeros = prev_len - len + 1;
					break;
				} else if(current[k] > prev[k]) {
					// take current and fill with zeros if necessary
					missing_zeros = prev_len - len;
					break;
				}
			}
			if(k == len) {
				// prefix
				if(k == prev_len) {
					// prev == current so need to add zero
					missing_zeros = 1;
				} else {
					// strict prefix (shorter), need to increment
					string sub = prev.substr(k);
					int rest = 1;
					for(int p = sub.length() - 1; p >= 0; --p) {
						int digit = sub[p] - '0';
						int added = digit + rest;
						rest = added / 10;
						added %= 10;
						sub[p] = added + '0';
					}
					current += sub;
					new_digits += sub.length();
					if(rest > 0) {
						missing_zeros = 1;
					}
				}
			}
			if(missing_zeros > 0) {
				// fill zeros
				for(int m = 0; m < missing_zeros; m++) {
					current.push_back('0');
					new_digits += 1;
				}
			}
			prev = current;
			prev_len = current.length();
		}
	}
	printf("%lld\n", new_digits);
	return 0;
}