#include <iostream> #include <vector> using namespace std; namespace { constexpr long long sqr(long long x) { return x * x; } constexpr long long llpow(long long a, int b) { return (b == 0) ? 1 : ((b % 2 == 0) ? sqr(llpow(a, b / 2)) : a * sqr(llpow(a, b / 2))); } struct Number { constexpr static long long cnt = 17; constexpr static long long limit = llpow(10, cnt); int len; long long prefix; long long suffix; Number(long long x) { prefix = x; while (prefix >= limit) prefix /= 10; while (prefix * 10 < limit) prefix *= 10; suffix = x % limit; len = 0; while (x > 0) { ++len; x /= 10; } } #define CMP(OP) \ friend bool operator OP(Number const& lhs, Number const& rhs) { \ if (lhs.len != rhs.len) return lhs.len OP rhs.len; \ if (lhs.prefix != rhs.prefix) return lhs.prefix OP rhs.prefix; \ return lhs.suffix OP rhs.suffix; \ } CMP(<) CMP(>) CMP(<=) CMP(>=) CMP(==) CMP(!=) Number& operator<<=(int s) { len += s; if (s >= cnt) { suffix = 0; } else { suffix = suffix % llpow(10, cnt - s) * llpow(10, s); } return *this; } Number& operator++() { if (len <= cnt) return *this = Number{suffix + 1}; if (len < 2 * cnt) { int shift = llpow(10, len - cnt); prefix -= suffix / shift; ++suffix; prefix += suffix / shift; } else { ++suffix; } return *this; } }; long long solve(vector<int> const& data) { long long res = 0; Number smallest{1}; for (auto const& x: data) { auto cur = Number{x}; auto upper = Number{x + 1}; if (cur.len < smallest.len) { int shift = smallest.len - cur.len; res += shift; cur <<= shift; upper <<= shift; } if (cur < smallest) { if (smallest < upper) { cur = smallest; } else { ++res; cur <<= 1; } } smallest = cur; ++smallest; } return res; } } int main() { iostream::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> data; data.reserve(n); for (int i = 0; i < n; ++i) { int x; cin >> x; data.emplace_back(x); } cout << solve(data) << 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 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 | #include <iostream> #include <vector> using namespace std; namespace { constexpr long long sqr(long long x) { return x * x; } constexpr long long llpow(long long a, int b) { return (b == 0) ? 1 : ((b % 2 == 0) ? sqr(llpow(a, b / 2)) : a * sqr(llpow(a, b / 2))); } struct Number { constexpr static long long cnt = 17; constexpr static long long limit = llpow(10, cnt); int len; long long prefix; long long suffix; Number(long long x) { prefix = x; while (prefix >= limit) prefix /= 10; while (prefix * 10 < limit) prefix *= 10; suffix = x % limit; len = 0; while (x > 0) { ++len; x /= 10; } } #define CMP(OP) \ friend bool operator OP(Number const& lhs, Number const& rhs) { \ if (lhs.len != rhs.len) return lhs.len OP rhs.len; \ if (lhs.prefix != rhs.prefix) return lhs.prefix OP rhs.prefix; \ return lhs.suffix OP rhs.suffix; \ } CMP(<) CMP(>) CMP(<=) CMP(>=) CMP(==) CMP(!=) Number& operator<<=(int s) { len += s; if (s >= cnt) { suffix = 0; } else { suffix = suffix % llpow(10, cnt - s) * llpow(10, s); } return *this; } Number& operator++() { if (len <= cnt) return *this = Number{suffix + 1}; if (len < 2 * cnt) { int shift = llpow(10, len - cnt); prefix -= suffix / shift; ++suffix; prefix += suffix / shift; } else { ++suffix; } return *this; } }; long long solve(vector<int> const& data) { long long res = 0; Number smallest{1}; for (auto const& x: data) { auto cur = Number{x}; auto upper = Number{x + 1}; if (cur.len < smallest.len) { int shift = smallest.len - cur.len; res += shift; cur <<= shift; upper <<= shift; } if (cur < smallest) { if (smallest < upper) { cur = smallest; } else { ++res; cur <<= 1; } } smallest = cur; ++smallest; } return res; } } int main() { iostream::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> data; data.reserve(n); for (int i = 0; i < n; ++i) { int x; cin >> x; data.emplace_back(x); } cout << solve(data) << endl; return 0; } |