#include <iostream> #include <vector> using namespace std; typedef long long ll; int count_digits(int x) { int r = 0; while (x) { r++; x /= 10; } return r; } int tenp[10]; int get_digit(int x, int d) { return (x / tenp[d]) % 10; } struct number { int fix, zeroes, counter; int digit(int d) { if (d < zeroes) { return d < count_digits(counter) ? get_digit(counter, d) : 0; } else { return get_digit(fix, d-zeroes); } } }; number get_next(number pv, int x) { int a = count_digits(pv.fix); int b = count_digits(x); if (a + pv.zeroes < b) { return { x, 0, 0 }; } int nx_zeroes = a + pv.zeroes - b; for (int i = 0; i < b; i++) { int da = pv.digit(a + pv.zeroes - 1 - i); int db = get_digit(x, b - 1 - i); if (da > db) { return { x, nx_zeroes + 1, 0 }; } else if (da < db) { return { x, nx_zeroes, 0 }; } } if (a < b) { pv.fix *= tenp[b - a]; pv.zeroes -= b - a; if (pv.zeroes < 10 && pv.counter > tenp[pv.zeroes]) { pv.fix += pv.counter / tenp[pv.zeroes]; pv.counter %= tenp[pv.zeroes]; } a = b; } int diff = a - b; int extra = 0; for (int i = b; i < a; i++) { extra = 10 * extra + get_digit(pv.fix, a - 1 - i); } nx_zeroes -= diff; if (nx_zeroes > 9 || pv.counter + 1 < tenp[nx_zeroes]) { return { x * tenp[diff] + extra, nx_zeroes, pv.counter + 1 }; } else if (extra + 1 < tenp[diff]) { return { x * tenp[diff] + extra + 1, nx_zeroes, 0 }; } else { return { x, nx_zeroes + diff + 1, 0 }; } } int main() { ios_base::sync_with_stdio(0); tenp[0] = 1; for (int i = 1; i < 10; i++) tenp[i] = 10 * tenp[i-1]; ll res = 0; int n; cin >> n; number f = { 0, 0, 0 }; cin >> f.fix; for (int i = 0; i < n-1; i++) { int m; cin >> m; f = get_next(f, m); res += count_digits(f.fix) - count_digits(m) + f.zeroes; } cout << res << endl; 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 | #include <iostream> #include <vector> using namespace std; typedef long long ll; int count_digits(int x) { int r = 0; while (x) { r++; x /= 10; } return r; } int tenp[10]; int get_digit(int x, int d) { return (x / tenp[d]) % 10; } struct number { int fix, zeroes, counter; int digit(int d) { if (d < zeroes) { return d < count_digits(counter) ? get_digit(counter, d) : 0; } else { return get_digit(fix, d-zeroes); } } }; number get_next(number pv, int x) { int a = count_digits(pv.fix); int b = count_digits(x); if (a + pv.zeroes < b) { return { x, 0, 0 }; } int nx_zeroes = a + pv.zeroes - b; for (int i = 0; i < b; i++) { int da = pv.digit(a + pv.zeroes - 1 - i); int db = get_digit(x, b - 1 - i); if (da > db) { return { x, nx_zeroes + 1, 0 }; } else if (da < db) { return { x, nx_zeroes, 0 }; } } if (a < b) { pv.fix *= tenp[b - a]; pv.zeroes -= b - a; if (pv.zeroes < 10 && pv.counter > tenp[pv.zeroes]) { pv.fix += pv.counter / tenp[pv.zeroes]; pv.counter %= tenp[pv.zeroes]; } a = b; } int diff = a - b; int extra = 0; for (int i = b; i < a; i++) { extra = 10 * extra + get_digit(pv.fix, a - 1 - i); } nx_zeroes -= diff; if (nx_zeroes > 9 || pv.counter + 1 < tenp[nx_zeroes]) { return { x * tenp[diff] + extra, nx_zeroes, pv.counter + 1 }; } else if (extra + 1 < tenp[diff]) { return { x * tenp[diff] + extra + 1, nx_zeroes, 0 }; } else { return { x, nx_zeroes + diff + 1, 0 }; } } int main() { ios_base::sync_with_stdio(0); tenp[0] = 1; for (int i = 1; i < 10; i++) tenp[i] = 10 * tenp[i-1]; ll res = 0; int n; cin >> n; number f = { 0, 0, 0 }; cin >> f.fix; for (int i = 0; i < n-1; i++) { int m; cin >> m; f = get_next(f, m); res += count_digits(f.fix) - count_digits(m) + f.zeroes; } cout << res << endl; return 0; } |