#include<iostream> #include<algorithm> #include<deque> using namespace std; const bool debug = false; int dlen(long long v) { int cnt = 0; while(v != 0) { cnt += 1; v /= 10; } return cnt; } const int PRLEN = 17; class SNum { long long primary; int zeros; public: SNum(int a) { primary = a; zeros = 0; } SNum(int a, int zerAfter) { primary = a; int zerosForPr = min(zerAfter, PRLEN - dlen(a)); for (int i = 0; i < zerosForPr; i++) primary *= 10; zeros = zerAfter - zerosForPr; } int len() { return dlen(primary) + zeros; } long long prefWithLen(int k) { int toCut = dlen(primary) - k; long long pref = primary; for (int i = 0; i < toCut; i++) pref /= 10; return pref; } bool primaryWitoutLeadingWillCarry(int digits) { long long sufSize = dlen(primary) - digits; long long m = 1; for (int i = 0; i < sufSize; i++) m *= 10; return ((primary % m) + 1) >= m; } void addToPrimary(int v) { primary += v; } void debPrint() { if (!debug) return; cerr << primary; for (int i = 0; i < zeros; i++) cerr << '0'; cerr << endl; } }; int main() { ios_base::sync_with_stdio(0); int n; cin >> n; int a; cin >> a; SNum p(a); p.debPrint(); long long digitsAdded = 0; for(int i = 0; i < n - 1; i++) { cin >> a; if (dlen(a) > p.len()) p = SNum(a); else { int pPref = p.prefWithLen(dlen(a)); if (a > pPref) { int zeros = p.len() - dlen(a); p = SNum(a, zeros); // match length of p, but with prefix a digitsAdded += zeros; // just add zeros after a } else if (a < pPref) { // same as before, but with 1 extra zero int zeros = p.len() - dlen(a) + 1; p = SNum(a, zeros); digitsAdded += zeros; } else { if (p.primaryWitoutLeadingWillCarry(dlen(a))) { // same as before, just make new one longer. int zeros = p.len() - dlen(a) + 1; p = SNum(a, zeros); digitsAdded += zeros; } else { p.addToPrimary(1); digitsAdded += p.len() - dlen(a); } } } p.debPrint(); } cout << digitsAdded << 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 | #include<iostream> #include<algorithm> #include<deque> using namespace std; const bool debug = false; int dlen(long long v) { int cnt = 0; while(v != 0) { cnt += 1; v /= 10; } return cnt; } const int PRLEN = 17; class SNum { long long primary; int zeros; public: SNum(int a) { primary = a; zeros = 0; } SNum(int a, int zerAfter) { primary = a; int zerosForPr = min(zerAfter, PRLEN - dlen(a)); for (int i = 0; i < zerosForPr; i++) primary *= 10; zeros = zerAfter - zerosForPr; } int len() { return dlen(primary) + zeros; } long long prefWithLen(int k) { int toCut = dlen(primary) - k; long long pref = primary; for (int i = 0; i < toCut; i++) pref /= 10; return pref; } bool primaryWitoutLeadingWillCarry(int digits) { long long sufSize = dlen(primary) - digits; long long m = 1; for (int i = 0; i < sufSize; i++) m *= 10; return ((primary % m) + 1) >= m; } void addToPrimary(int v) { primary += v; } void debPrint() { if (!debug) return; cerr << primary; for (int i = 0; i < zeros; i++) cerr << '0'; cerr << endl; } }; int main() { ios_base::sync_with_stdio(0); int n; cin >> n; int a; cin >> a; SNum p(a); p.debPrint(); long long digitsAdded = 0; for(int i = 0; i < n - 1; i++) { cin >> a; if (dlen(a) > p.len()) p = SNum(a); else { int pPref = p.prefWithLen(dlen(a)); if (a > pPref) { int zeros = p.len() - dlen(a); p = SNum(a, zeros); // match length of p, but with prefix a digitsAdded += zeros; // just add zeros after a } else if (a < pPref) { // same as before, but with 1 extra zero int zeros = p.len() - dlen(a) + 1; p = SNum(a, zeros); digitsAdded += zeros; } else { if (p.primaryWitoutLeadingWillCarry(dlen(a))) { // same as before, just make new one longer. int zeros = p.len() - dlen(a) + 1; p = SNum(a, zeros); digitsAdded += zeros; } else { p.addToPrimary(1); digitsAdded += p.len() - dlen(a); } } } p.debPrint(); } cout << digitsAdded << endl; return 0; } |