//Daniel Grzegorzewski #include <bits/stdc++.h> #pragma GCC optimize("O3") #define MP make_pair #define PB push_back #define ST first #define ND second #define int long long using namespace std; typedef pair<int, int> PII; typedef vector<int> VI; typedef vector<PII> VII; typedef long long LL; void init_ios() { ios_base::sync_with_stdio(0); cin.tie(0); } const int N = 2*(int)1e5 + 10; const int LOL = 18; int n, len, res; string a[N]; bool check(const string& x) { if (x.size() >= LOL) len = x.size(); } string dodaj(string co) { int nxt = 1; for (int i = (int)co.size()-1; nxt && i >= 0; --i) { if (co[i] == '9') co[i] = '0'; else { co[i]++; nxt = 0; } } if (nxt) co = "1" + co; return co; } void modify(int i) { // a[i-1] krotszy od LOL if (len == 0) { if (a[i].size() > a[i-1].size()) return; else if (a[i].size() == a[i-1].size()) { if (a[i] > a[i-1]) return; ++res; a[i] += "0"; check(a[i]); return; } else { string pref = a[i-1].substr(0, a[i].size()); if (a[i] > pref) { while (a[i].size() < a[i-1].size()) { ++res; a[i] += "0"; } check(a[i]); } else if (a[i] < pref) { while (a[i].size() <= a[i-1].size()) { ++res; a[i] += "0"; } check(a[i]); } else { string suf = a[i-1].substr(a[i].size()); string suf2 = dodaj(suf); if (suf.size() == suf2.size()) { res += suf.size(); a[i] += suf2; } else { while (a[i].size() <= a[i-1].size()) { ++res; a[i] += "0"; } } check(a[i]); } } } // a[i-1] co najmniej dlugosci LOL else { string pref = a[i-1].substr(0, a[i].size()); if (pref > a[i]) { ++len; res += len-a[i].size(); while (a[i].size() <= LOL) a[i] += "0"; } else if (a[i] == pref) { res += len-a[i].size(); while (a[i].size() <= LOL) a[i] += a[i-1][a[i].size()]; } else { res += len-a[i].size(); while (a[i].size() <= LOL) a[i] += "0"; } } } signed main() { init_ios(); cin >> n; for (int i = 1; i <= n; ++i) cin >> a[i]; for (int i = 2; i <= n; ++i) modify(i); cout<<res<<"\n"; }
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 | //Daniel Grzegorzewski #include <bits/stdc++.h> #pragma GCC optimize("O3") #define MP make_pair #define PB push_back #define ST first #define ND second #define int long long using namespace std; typedef pair<int, int> PII; typedef vector<int> VI; typedef vector<PII> VII; typedef long long LL; void init_ios() { ios_base::sync_with_stdio(0); cin.tie(0); } const int N = 2*(int)1e5 + 10; const int LOL = 18; int n, len, res; string a[N]; bool check(const string& x) { if (x.size() >= LOL) len = x.size(); } string dodaj(string co) { int nxt = 1; for (int i = (int)co.size()-1; nxt && i >= 0; --i) { if (co[i] == '9') co[i] = '0'; else { co[i]++; nxt = 0; } } if (nxt) co = "1" + co; return co; } void modify(int i) { // a[i-1] krotszy od LOL if (len == 0) { if (a[i].size() > a[i-1].size()) return; else if (a[i].size() == a[i-1].size()) { if (a[i] > a[i-1]) return; ++res; a[i] += "0"; check(a[i]); return; } else { string pref = a[i-1].substr(0, a[i].size()); if (a[i] > pref) { while (a[i].size() < a[i-1].size()) { ++res; a[i] += "0"; } check(a[i]); } else if (a[i] < pref) { while (a[i].size() <= a[i-1].size()) { ++res; a[i] += "0"; } check(a[i]); } else { string suf = a[i-1].substr(a[i].size()); string suf2 = dodaj(suf); if (suf.size() == suf2.size()) { res += suf.size(); a[i] += suf2; } else { while (a[i].size() <= a[i-1].size()) { ++res; a[i] += "0"; } } check(a[i]); } } } // a[i-1] co najmniej dlugosci LOL else { string pref = a[i-1].substr(0, a[i].size()); if (pref > a[i]) { ++len; res += len-a[i].size(); while (a[i].size() <= LOL) a[i] += "0"; } else if (a[i] == pref) { res += len-a[i].size(); while (a[i].size() <= LOL) a[i] += a[i-1][a[i].size()]; } else { res += len-a[i].size(); while (a[i].size() <= LOL) a[i] += "0"; } } } signed main() { init_ios(); cin >> n; for (int i = 1; i <= n; ++i) cin >> a[i]; for (int i = 2; i <= n; ++i) modify(i); cout<<res<<"\n"; } |