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 | #include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct number {
string prefix;
int zeros;
string suffix;
int len() const {
return prefix.size() + zeros + suffix.size();
}
int operator[](int ind) const {
if (ind < (int)prefix.size()) {
return prefix[ind] - '0';
}
ind -= prefix.size();
if (ind < zeros) {
return 0;
}
ind -= zeros;
return suffix[ind] - '0';
}
bool operator<(number const& rhs) const {
if (len() != rhs.len()) {
return len() < rhs.len();
}
for (int i = 0; i < (int)max(prefix.size(), rhs.prefix.size()); i++) {
if ((*this)[i] != rhs[i]) {
return (*this)[i] < rhs[i];
}
}
for (int i = len() - max(suffix.size(), rhs.suffix.size()); i < len(); i++) {
if ((*this)[i] != rhs[i]) {
return (*this)[i] < rhs[i];
}
}
return false;
}
number add1() const {
number res = *this;
for (int i = (int)(res.suffix.size()) - 1; i >= 0; i--) {
if (res.suffix[i] != '9') {
res.suffix[i]++;
return res;
}
res.suffix[i] = '0';
}
if (res.zeros) {
res.zeros--;
res.suffix = string("1") + res.suffix;
return res;
}
res.zeros = res.suffix.size();
res.suffix.clear();
for (int i = (int)(res.prefix.size()) - 1; i >= 0; i--) {
if (res.prefix[i] != '9') {
res.prefix[i]++;
break;
}
res.zeros++;
res.prefix.pop_back();
}
if (res.prefix.empty()) {
res.prefix = "1";
}
return res;
}
};
int main() {
int n;
cin >> n;
number prv{};
ll res = 0;
while (n--) {
string s;
cin >> s;
number current{std::move(s), 0, ""};
if (prv < current) {
prv = std::move(current);
} else {
auto p1 = prv.add1();
bool pref = true;
for (int i = 0; i < (int)current.prefix.size(); i++) {
if (current[i] != p1[i]) {
pref = false;
break;
}
}
if (pref) {
res += p1.len() - current.len();
prv = std::move(p1);
} else {
current.zeros = prv.len() - current.len();
if (!(prv < current)) {
current.zeros++;
}
res += current.zeros;
prv = std::move(current);
}
}
}
cout << res << endl;
}
|