#include <bits/stdc++.h> using namespace std; typedef long long ll; #define N 200000 char a[N][16]; char c[N][16]; int la[N], lc[N], k[N], old[N]; char get(int i, int j) { if (j < la[i]) return a[i][j]; int lbi = la[i]+k[i]; int lzi = lbi-lc[i]; if (j < lzi) return '0'; if (j < lbi) return c[i][j-lzi]; return 0; } bool inc(char s[], int n) { for (int i = n-1; i >= 0; --i) { if (s[i] == '9') { s[i] = '0'; continue; } ++s[i]; return true; } return false; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n; ll ans = 0; cin >> n; for (int i = 0; i < n; ++i) { cin >> a[i]; la[i] = strlen(a[i]); } old[0] = la[0]; for (int i = 1; i < n; ++i) { old[i] = la[i]; if (la[i] > la[i-1]+k[i-1]) { continue; } int p; for (p = 0; p < la[i]; ++p) { if (a[i][p] != get(i-1, p)) break; } /// diff: if (p < la[i]) { k[i] = la[i-1]+k[i-1]-la[i]; if (a[i][p] < get(i-1, p)) ++k[i]; continue; } /// eq: if (p == la[i-1]+k[i-1]) { k[i] = 1; continue; } /// pref: for (; p < la[i-1]; ++p) a[i][p] = a[i-1][p]; k[i] = la[i-1]+k[i-1]-p; lc[i] = min(lc[i-1], k[i]); copy(c[i-1]+lc[i-1]-lc[i], c[i-1]+lc[i-1], c[i]); if (!inc(c[i], lc[i])) { if (lc[i] < k[i]) { c[i][lc[i]++] = '0'; c[i][0] = '1'; } else { lc[i] = 0; if (!inc(a[i]+la[i], p-la[i])) { k[i] += p-la[i]+1; p = la[i]; } } } //assert(0 <= lc[i] && lc[i] <= k[i]); la[i] = p; } for (int i = 0; i < n; ++i) ans += la[i]+k[i]-old[i]; cout << ans << '\n'; /// dbg /*cerr << "*** debug ***\n"; for (int i = 0; i < n; ++i) { //cerr << "i = " << i << '\n'; //cerr << " la = " << la[i] << '\n'; //cerr << " k = " << k[i] << '\n'; //cerr << " diff = " << la[i]+k[i]-old[i] << '\n'; for (int j = 0; j < old[i]; ++j) cerr << a[i][j]; cerr << '|'; for (int j = old[i]; j < la[i]+k[i]; ++j) cerr << get(i, j); cerr << '\n'; } cerr << "*** end debug ***\n";*/ return 0; }
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 | #include <bits/stdc++.h> using namespace std; typedef long long ll; #define N 200000 char a[N][16]; char c[N][16]; int la[N], lc[N], k[N], old[N]; char get(int i, int j) { if (j < la[i]) return a[i][j]; int lbi = la[i]+k[i]; int lzi = lbi-lc[i]; if (j < lzi) return '0'; if (j < lbi) return c[i][j-lzi]; return 0; } bool inc(char s[], int n) { for (int i = n-1; i >= 0; --i) { if (s[i] == '9') { s[i] = '0'; continue; } ++s[i]; return true; } return false; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n; ll ans = 0; cin >> n; for (int i = 0; i < n; ++i) { cin >> a[i]; la[i] = strlen(a[i]); } old[0] = la[0]; for (int i = 1; i < n; ++i) { old[i] = la[i]; if (la[i] > la[i-1]+k[i-1]) { continue; } int p; for (p = 0; p < la[i]; ++p) { if (a[i][p] != get(i-1, p)) break; } /// diff: if (p < la[i]) { k[i] = la[i-1]+k[i-1]-la[i]; if (a[i][p] < get(i-1, p)) ++k[i]; continue; } /// eq: if (p == la[i-1]+k[i-1]) { k[i] = 1; continue; } /// pref: for (; p < la[i-1]; ++p) a[i][p] = a[i-1][p]; k[i] = la[i-1]+k[i-1]-p; lc[i] = min(lc[i-1], k[i]); copy(c[i-1]+lc[i-1]-lc[i], c[i-1]+lc[i-1], c[i]); if (!inc(c[i], lc[i])) { if (lc[i] < k[i]) { c[i][lc[i]++] = '0'; c[i][0] = '1'; } else { lc[i] = 0; if (!inc(a[i]+la[i], p-la[i])) { k[i] += p-la[i]+1; p = la[i]; } } } //assert(0 <= lc[i] && lc[i] <= k[i]); la[i] = p; } for (int i = 0; i < n; ++i) ans += la[i]+k[i]-old[i]; cout << ans << '\n'; /// dbg /*cerr << "*** debug ***\n"; for (int i = 0; i < n; ++i) { //cerr << "i = " << i << '\n'; //cerr << " la = " << la[i] << '\n'; //cerr << " k = " << k[i] << '\n'; //cerr << " diff = " << la[i]+k[i]-old[i] << '\n'; for (int j = 0; j < old[i]; ++j) cerr << a[i][j]; cerr << '|'; for (int j = old[i]; j < la[i]+k[i]; ++j) cerr << get(i, j); cerr << '\n'; } cerr << "*** end debug ***\n";*/ return 0; } |