Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //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";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement