#include <iostream> #include <cassert> using namespace std; using ll = long long; ll ipow10(int a) { assert(a>=0); ll r = 1; while (a--) r *= 10; return r; } ll ilog10(ll a) { assert(a>=0); ll r = 0; while (a>0) { r ++; a /= 10; } return r; } const int SPS = 9; struct bnum { string start; int exp=0; long end=0; void check() { if (exp > 0) assert(start.size() == SPS); assert((start.size() > 0) ^ (exp == 0)); if (exp > 0 && exp < 18) assert(ipow10(exp) > end); } void simplify() { check(); if(end > (ll)1e16) { string s = to_string(end); start = s.substr(0, SPS); exp = s.size() - SPS; end = stoll(s.substr(SPS)); check(); } } string pr() { string s = to_string(end); if (exp > 0) while (s.size() != exp) s = ('0') + s; return start + s; } }; bnum simple(ll a) { bnum b; b.start = ""; b.exp = 0; b.end = a; return b; } pair<bnum, int> nextnum(bnum prev, ll prefix) { if (prev.exp == 0) { if (prefix > prev.end) return {simple(prefix), 0}; int delta_count = ilog10(prev.end) - ilog10(prefix); ll pref0 = prefix * ipow10(delta_count); ll prefF = (prefix + 1) * ipow10(delta_count); ll cand = prev.end + 1; if (cand < pref0) return make_pair(simple(pref0), delta_count); if (cand < prefF) return make_pair(simple(cand), delta_count); return make_pair(simple(pref0 * 10), delta_count + 1); } else { string sprefix = to_string(prefix); string soprefix = sprefix; while (sprefix.size() < SPS) sprefix.push_back('0'); int added_digits = SPS + prev.exp - ilog10(prefix); assert(sprefix.size() == prev.start.size()); // cout << prev.start.substr(0, soprefix.size()) << " " << soprefix << endl; if (prev.start.substr(0, soprefix.size()) == soprefix) { bnum n = prev; n.end ++; n.start = prev.start; return {n, added_digits}; } else if (sprefix > prev.start) { bnum n = prev; n.end = 0; n.start = sprefix; return {n, added_digits}; /*} else if (sprefix == prev.start) { bnum n = prev; n.end ++; n.start = sprefix; return {n, added_digits};*/ } else { bnum n = prev; n.end = 0; n.start = sprefix; n.exp ++; return {n, added_digits + 1}; } } abort(); } int main() { ios_base::sync_with_stdio(0); int n; cin >> n; bnum curr; cin >> curr.end; ll res = 0; for (int i=1; i < n; i++) { ll newn; cin >> newn; curr.simplify(); auto r = nextnum(curr, newn); curr = r.first; res += r.second; //cerr << "num " << newn << endl; //cerr << "curr: " << curr.start << " ..." << curr.exp << "... " << curr.end << endl; //cout << "curr: " << curr.pr() << endl; } cout << res << endl; }
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 123 124 125 126 127 128 | #include <iostream> #include <cassert> using namespace std; using ll = long long; ll ipow10(int a) { assert(a>=0); ll r = 1; while (a--) r *= 10; return r; } ll ilog10(ll a) { assert(a>=0); ll r = 0; while (a>0) { r ++; a /= 10; } return r; } const int SPS = 9; struct bnum { string start; int exp=0; long end=0; void check() { if (exp > 0) assert(start.size() == SPS); assert((start.size() > 0) ^ (exp == 0)); if (exp > 0 && exp < 18) assert(ipow10(exp) > end); } void simplify() { check(); if(end > (ll)1e16) { string s = to_string(end); start = s.substr(0, SPS); exp = s.size() - SPS; end = stoll(s.substr(SPS)); check(); } } string pr() { string s = to_string(end); if (exp > 0) while (s.size() != exp) s = ('0') + s; return start + s; } }; bnum simple(ll a) { bnum b; b.start = ""; b.exp = 0; b.end = a; return b; } pair<bnum, int> nextnum(bnum prev, ll prefix) { if (prev.exp == 0) { if (prefix > prev.end) return {simple(prefix), 0}; int delta_count = ilog10(prev.end) - ilog10(prefix); ll pref0 = prefix * ipow10(delta_count); ll prefF = (prefix + 1) * ipow10(delta_count); ll cand = prev.end + 1; if (cand < pref0) return make_pair(simple(pref0), delta_count); if (cand < prefF) return make_pair(simple(cand), delta_count); return make_pair(simple(pref0 * 10), delta_count + 1); } else { string sprefix = to_string(prefix); string soprefix = sprefix; while (sprefix.size() < SPS) sprefix.push_back('0'); int added_digits = SPS + prev.exp - ilog10(prefix); assert(sprefix.size() == prev.start.size()); // cout << prev.start.substr(0, soprefix.size()) << " " << soprefix << endl; if (prev.start.substr(0, soprefix.size()) == soprefix) { bnum n = prev; n.end ++; n.start = prev.start; return {n, added_digits}; } else if (sprefix > prev.start) { bnum n = prev; n.end = 0; n.start = sprefix; return {n, added_digits}; /*} else if (sprefix == prev.start) { bnum n = prev; n.end ++; n.start = sprefix; return {n, added_digits};*/ } else { bnum n = prev; n.end = 0; n.start = sprefix; n.exp ++; return {n, added_digits + 1}; } } abort(); } int main() { ios_base::sync_with_stdio(0); int n; cin >> n; bnum curr; cin >> curr.end; ll res = 0; for (int i=1; i < n; i++) { ll newn; cin >> newn; curr.simplify(); auto r = nextnum(curr, newn); curr = r.first; res += r.second; //cerr << "num " << newn << endl; //cerr << "curr: " << curr.start << " ..." << curr.exp << "... " << curr.end << endl; //cout << "curr: " << curr.pr() << endl; } cout << res << endl; } |