#include<bits/stdc++.h> using namespace std; #define st first #define nd second #define mp make_pair #define pb push_back #define all(x) x.begin(), x.end() #define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0) typedef long long lli; typedef pair<int, int> pii; typedef pair<lli, lli> pll; typedef pair<lli, int> pli; typedef pair<int, lli> pil; const int N=2e5+5; int n, a, l[N], lpref[N], lsuf[N], pot[10]; pii tab[N]; lli wyn=0; int lng(int x) { if(x==0)return 0; return lng(x/10)+1; } lli pref(pii xy, int lx, int ly, int lxy, int blep) { lli nghu=xy.st; if(lx<blep) { nghu*=pot[blep-lx]; if(blep+ly>lxy)nghu+=(xy.nd/pot[lxy-blep]); } else { nghu/=pot[lx-blep]; } return nghu; } int main() { boost; pot[0]=1; for(int i=1;i<=9;i++)pot[i]=pot[i-1]*10; cin>>n; for(int i=1;i<=n;i++) { cin>>a; tab[i]=mp(a, 0); lpref[i]=lng(a); } l[1]=lpref[1]; for(int i=2;i<=n;i++) { if(lpref[i]>l[i-1]) { l[i]=lpref[i]; continue; } lli b=pref(tab[i-1], lpref[i-1], lsuf[i-1], l[i-1], lpref[i]); if(tab[i].st>b) { tab[i]=mp(tab[i].st, 0); l[i]=l[i-1]; wyn+=(l[i]-lpref[i]); } else if(tab[i].st<b) { tab[i]=mp(tab[i].st, 0); l[i]=l[i-1]+1; wyn+=(l[i]-lpref[i]); } else { int pom=tab[i-1].nd; if(lpref[i]+lsuf[i-1]>l[i-1])pom%=pot[l[i-1]-lpref[i]]; int bliep=lng(pom); if((pom+1<pot[bliep])||(max(lpref[i-1], lpref[i])+bliep<l[i-1])) { tab[i]=mp(tab[i].st, pom+1); l[i]=l[i-1]; lsuf[i]=lng(pom+1); wyn+=(l[i]-lpref[i]); if(tab[i-1].st>b) { tab[i]=mp(tab[i-1].st, pom+1); lpref[i]=lpref[i-1]; } } else if((b<tab[i-1].st)&&(tab[i-1].st%pot[lpref[i-1]-lpref[i]]+1<pot[lpref[i-1]-lpref[i]])) { tab[i]=mp(tab[i-1].st+1, 0); l[i]=l[i-1]; lsuf[i]=bliep; wyn+=(l[i]-lpref[i]); lpref[i]=lpref[i-1]; } else { tab[i]=mp(tab[i].st, 0); l[i]=l[i-1]+1; wyn+=(l[i]-lpref[i]); } } } cout<<wyn<<"\n"; 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 | #include<bits/stdc++.h> using namespace std; #define st first #define nd second #define mp make_pair #define pb push_back #define all(x) x.begin(), x.end() #define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0) typedef long long lli; typedef pair<int, int> pii; typedef pair<lli, lli> pll; typedef pair<lli, int> pli; typedef pair<int, lli> pil; const int N=2e5+5; int n, a, l[N], lpref[N], lsuf[N], pot[10]; pii tab[N]; lli wyn=0; int lng(int x) { if(x==0)return 0; return lng(x/10)+1; } lli pref(pii xy, int lx, int ly, int lxy, int blep) { lli nghu=xy.st; if(lx<blep) { nghu*=pot[blep-lx]; if(blep+ly>lxy)nghu+=(xy.nd/pot[lxy-blep]); } else { nghu/=pot[lx-blep]; } return nghu; } int main() { boost; pot[0]=1; for(int i=1;i<=9;i++)pot[i]=pot[i-1]*10; cin>>n; for(int i=1;i<=n;i++) { cin>>a; tab[i]=mp(a, 0); lpref[i]=lng(a); } l[1]=lpref[1]; for(int i=2;i<=n;i++) { if(lpref[i]>l[i-1]) { l[i]=lpref[i]; continue; } lli b=pref(tab[i-1], lpref[i-1], lsuf[i-1], l[i-1], lpref[i]); if(tab[i].st>b) { tab[i]=mp(tab[i].st, 0); l[i]=l[i-1]; wyn+=(l[i]-lpref[i]); } else if(tab[i].st<b) { tab[i]=mp(tab[i].st, 0); l[i]=l[i-1]+1; wyn+=(l[i]-lpref[i]); } else { int pom=tab[i-1].nd; if(lpref[i]+lsuf[i-1]>l[i-1])pom%=pot[l[i-1]-lpref[i]]; int bliep=lng(pom); if((pom+1<pot[bliep])||(max(lpref[i-1], lpref[i])+bliep<l[i-1])) { tab[i]=mp(tab[i].st, pom+1); l[i]=l[i-1]; lsuf[i]=lng(pom+1); wyn+=(l[i]-lpref[i]); if(tab[i-1].st>b) { tab[i]=mp(tab[i-1].st, pom+1); lpref[i]=lpref[i-1]; } } else if((b<tab[i-1].st)&&(tab[i-1].st%pot[lpref[i-1]-lpref[i]]+1<pot[lpref[i-1]-lpref[i]])) { tab[i]=mp(tab[i-1].st+1, 0); l[i]=l[i-1]; lsuf[i]=bliep; wyn+=(l[i]-lpref[i]); lpref[i]=lpref[i-1]; } else { tab[i]=mp(tab[i].st, 0); l[i]=l[i-1]+1; wyn+=(l[i]-lpref[i]); } } } cout<<wyn<<"\n"; return 0; } |