#include <bits/stdc++.h> #define PII std::pair<int, int> #define ll long long ll countDigits(ll number){ ll ret = 0; while(number){ ret++; number /= 10; } return ret; } PII splitAfter(ll number, ll after){ ll nCount = countDigits(number); if(after >= nCount) return {number, 0}; if(after == 0) return {0, number}; ll tmp = 1; ll e = nCount - after; while(e){ e--; tmp *= 10; } return {number/tmp, number%tmp}; } int main(void){ ll ret = 0; ll n, current, last; std::cin >> n >> last; ll maxLength = 0; ll lastLength = countDigits(last); ll lastLengthUntouched = lastLength; ll MAX = 1000000000000000; for(int i = 1; i < n; i++){ std::cin >> current; ll currentLength = countDigits(current); lastLengthUntouched = currentLength; if(maxLength == 0 && last < MAX){ if(current == last){ current *= 10; } else if (current < last){ if(currentLength == lastLength){ current *= 10; } else{ auto pair = splitAfter(last, currentLength); int tmp = lastLength - currentLength; if(pair.first < current){ while(tmp--) current*=10; }else if(pair.first > current){ tmp++; while(tmp--) current*=10; } else{ // pair.first == current if(countDigits(pair.second + 1) <= tmp){ // nie ma przepelnienia current = last + 1; } else { // byloby przepelnienie tmp++; while(tmp--) current*=10; } } } } auto toAdd = countDigits(current) - currentLength; ret += toAdd; } // last < MAX else { if(maxLength == 0){ maxLength = countDigits(last); lastLength = lastLengthUntouched; auto tmp = splitAfter(last, lastLength); last = tmp.first; } ll c, l; if(current > last){ auto t = splitAfter(current, lastLength); c = t.first; l = last; if(c < l) maxLength++; } if(current < last){ auto t = splitAfter(last, currentLength); c = current; l = t.first; if(c < l) maxLength++; } auto toAdd = maxLength - currentLength; ret += toAdd; } last = current; lastLength = countDigits(current); } std::cout << ret << std::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 | #include <bits/stdc++.h> #define PII std::pair<int, int> #define ll long long ll countDigits(ll number){ ll ret = 0; while(number){ ret++; number /= 10; } return ret; } PII splitAfter(ll number, ll after){ ll nCount = countDigits(number); if(after >= nCount) return {number, 0}; if(after == 0) return {0, number}; ll tmp = 1; ll e = nCount - after; while(e){ e--; tmp *= 10; } return {number/tmp, number%tmp}; } int main(void){ ll ret = 0; ll n, current, last; std::cin >> n >> last; ll maxLength = 0; ll lastLength = countDigits(last); ll lastLengthUntouched = lastLength; ll MAX = 1000000000000000; for(int i = 1; i < n; i++){ std::cin >> current; ll currentLength = countDigits(current); lastLengthUntouched = currentLength; if(maxLength == 0 && last < MAX){ if(current == last){ current *= 10; } else if (current < last){ if(currentLength == lastLength){ current *= 10; } else{ auto pair = splitAfter(last, currentLength); int tmp = lastLength - currentLength; if(pair.first < current){ while(tmp--) current*=10; }else if(pair.first > current){ tmp++; while(tmp--) current*=10; } else{ // pair.first == current if(countDigits(pair.second + 1) <= tmp){ // nie ma przepelnienia current = last + 1; } else { // byloby przepelnienie tmp++; while(tmp--) current*=10; } } } } auto toAdd = countDigits(current) - currentLength; ret += toAdd; } // last < MAX else { if(maxLength == 0){ maxLength = countDigits(last); lastLength = lastLengthUntouched; auto tmp = splitAfter(last, lastLength); last = tmp.first; } ll c, l; if(current > last){ auto t = splitAfter(current, lastLength); c = t.first; l = last; if(c < l) maxLength++; } if(current < last){ auto t = splitAfter(last, currentLength); c = current; l = t.first; if(c < l) maxLength++; } auto toAdd = maxLength - currentLength; ret += toAdd; } last = current; lastLength = countDigits(current); } std::cout << ret << std::endl; return 0; } |