#include <iostream> #include <cstdio> #include <string> #include <vector> #include <map> #include <algorithm> #include <cassert> using namespace std; using ll = long long; vector<int> int_to_digits(ll n) { vector<int> digits; while(n > 0) { digits.push_back(n % 10); n /= 10; } reverse(digits.begin(), digits.end()); return digits; } bool is_less_than(const vector<int>& da, const vector<int>& db) { if (da.size() < db.size()) { return true; } else if (da.size() == db.size()) { for (int i = 0; i < da.size(); ++i) { if (da[i] < db[i]) { return true; } else if (da[i] > db[i]) { return false; } } } return false; } void print(const vector<int>& da) { for (auto val : da) { printf("%d", val); } printf("\n"); } int main() { int n; scanf("%d", &n); ll a; scanf("%lld", &a); vector<int> da = int_to_digits(a); ll res = 0; --n; const int BOUND = 30; //print(da); int max_len = da.size(); while (n--) { ll b; scanf("%lld", &b); vector<int> db = int_to_digits(b); if (is_less_than(da, db)) { da = db; //print(da); continue; } int pref_len = 0; while (pref_len < db.size()) { if (da[pref_len] != db[pref_len]) { break; } ++pref_len; } if (pref_len == db.size()) { for (int i = 0; i < db.size(); ++i) { da[i] = db[i]; } // increment int acc = 1; int idx = (int)da.size()-1; while (idx >= db.size() and acc) { auto tmp = da[idx]+acc; da[idx] = tmp%10; acc = tmp/10; --idx; } if (acc) { for (int i = db.size(); i < da.size(); ++i) { da[i] = 0; } da.push_back(0); } } else { const int ai = da[pref_len]; const int bi = db[pref_len]; for (int i = 0; i < db.size(); ++i) { da[i] = db[i]; } for (int i = 0; db.size() + i < da.size() and i < BOUND; ++i) { da[db.size() + i] = 0; } for (int i = 0; i < BOUND and (int)da.size()-1-i >= db.size(); ++i) { da[da.size()-1-i] = 0; } if (ai > bi) { da.push_back(0); } } //print(da); res += da.size() - db.size(); max_len = max(max_len, (int)da.size()); } //cout << max_len << endl; printf("%lld\n", res); 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 | #include <iostream> #include <cstdio> #include <string> #include <vector> #include <map> #include <algorithm> #include <cassert> using namespace std; using ll = long long; vector<int> int_to_digits(ll n) { vector<int> digits; while(n > 0) { digits.push_back(n % 10); n /= 10; } reverse(digits.begin(), digits.end()); return digits; } bool is_less_than(const vector<int>& da, const vector<int>& db) { if (da.size() < db.size()) { return true; } else if (da.size() == db.size()) { for (int i = 0; i < da.size(); ++i) { if (da[i] < db[i]) { return true; } else if (da[i] > db[i]) { return false; } } } return false; } void print(const vector<int>& da) { for (auto val : da) { printf("%d", val); } printf("\n"); } int main() { int n; scanf("%d", &n); ll a; scanf("%lld", &a); vector<int> da = int_to_digits(a); ll res = 0; --n; const int BOUND = 30; //print(da); int max_len = da.size(); while (n--) { ll b; scanf("%lld", &b); vector<int> db = int_to_digits(b); if (is_less_than(da, db)) { da = db; //print(da); continue; } int pref_len = 0; while (pref_len < db.size()) { if (da[pref_len] != db[pref_len]) { break; } ++pref_len; } if (pref_len == db.size()) { for (int i = 0; i < db.size(); ++i) { da[i] = db[i]; } // increment int acc = 1; int idx = (int)da.size()-1; while (idx >= db.size() and acc) { auto tmp = da[idx]+acc; da[idx] = tmp%10; acc = tmp/10; --idx; } if (acc) { for (int i = db.size(); i < da.size(); ++i) { da[i] = 0; } da.push_back(0); } } else { const int ai = da[pref_len]; const int bi = db[pref_len]; for (int i = 0; i < db.size(); ++i) { da[i] = db[i]; } for (int i = 0; db.size() + i < da.size() and i < BOUND; ++i) { da[db.size() + i] = 0; } for (int i = 0; i < BOUND and (int)da.size()-1-i >= db.size(); ++i) { da[da.size()-1-i] = 0; } if (ai > bi) { da.push_back(0); } } //print(da); res += da.size() - db.size(); max_len = max(max_len, (int)da.size()); } //cout << max_len << endl; printf("%lld\n", res); return 0; } |