#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define pb push_back #define mp make_pair #define all(a) begin(a),end(a) #define FOR(x,val,to) for(int x=(val);x<int((to));++x) #define FORE(x,val,to) for(auto x=(val);x<=(to);++x) #define FORR(x,arr) for(auto &x: arr) #define FORS(x,plus,arr) for(auto x = begin(arr)+(plus); x != end(arr); ++x) #define FORREV(x,plus,arr) for(auto x = (arr).rbegin()+(plus); x !=(arr).rend(); ++x) #define REE(s_) {cout<<s_<<'\n';exit(0);} #define GET(arr) for(auto &i: (arr)) sc(i) #define whatis(x) cerr << #x << " is " << (x) << endl; #define e1 first #define e2 second #define INF 0x7f7f7f7f typedef std::pair<int,int> pi; typedef std::vector<int> vi; typedef std::vector<std::string> vs; typedef int64_t ll; typedef uint64_t ull; #define umap unordered_map #define uset unordered_set using namespace std; using namespace __gnu_pbds; #ifdef _WIN32 #define getchar_unlocked() getchar() #define _CRT_DISABLE_PERFCRIT_LOCKS #endif template<class L, class R> ostream& operator<<(ostream &os, map<L, R> P) { for(auto const &vv: P)os<<"("<<vv.first<<","<<vv.second<<")"; return os; } template<class T> ostream& operator<<(ostream &os, set<T> V) { os<<"[";for(auto const &vv:V)os<<vv<<","; os<<"]"; return os; } template<class T> ostream& operator<<(ostream &os, vector<T> V) { os<<"[";for(auto const &vv:V)os<<vv<<","; os<<"]"; return os; } template<class L, class R> ostream& operator<<(ostream &os, pair<L, R> P) { os<<"("<<P.first<<","<<P.second<<")"; return os; } inline int fstoi(const string &str){auto it=str.begin();bool neg=0;int num=0;if(*it=='-')neg=1;else num=*it-'0';++it;while(it<str.end()) num=num*10+(*it++-'0');if(neg)num*=-1;return num;} inline void getch(char &x){while(x = getchar_unlocked(), x < 33){;}} inline void getstr(string &str){str.clear(); char cur;while(cur=getchar_unlocked(),cur<33){;}while(cur>32){str+=cur;cur=getchar_unlocked();}} template<typename T> inline bool sc(T &num){ bool neg=0; int c; num=0; while(c=getchar_unlocked(),c<33){if(c == EOF) return false;} if(c=='-'){ neg=1; c=getchar_unlocked(); } for(;c>47;c=getchar_unlocked()) num=num*10+c-48; if(neg) num*=-1; return true;}template<typename T, typename ...Args> inline void sc(T &num, Args &...args){ bool neg=0; int c; num=0; while(c=getchar_unlocked(),c<33){;} if(c=='-'){ neg=1; c=getchar_unlocked(); } for(;c>47;c=getchar_unlocked()) num=num*10+c-48; if(neg) num*=-1; sc(args...); } template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; //s.find_by_order(), s.order_of_key() <- works like lower_bound template<typename T> using ordered_map = tree<T, int, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define N 1000001 //int len(ll a){ // int ret = 0; // while(a) // a /= 10, ++ret; // return ret; //} void add1(string &s){ ++s.back(); auto it = --s.end(); while(*it > '9'){ *it = '0'; if(it == s.begin()){ s.insert(s.begin(),'1'); return; } --it; ++*it; } } int canp1(string a, string b, int df){ // ll bp1 = b+1; if(!df) return 1; if(a == b) return 2; return a < b; } int main(){ ios_base::sync_with_stdio(0);cin.tie(0); // for(ll xdd = 9; xdd < 1e17; xdd = xdd*10+9) // xddd.insert(xdd); int n; sc(n); pair<string,int> a[n]; FORR(i,a) getstr(i.e1), i.e2 = 0; ll ans = 0; FOR(i,0,n-1){ /* if(a[i].size() > 100){ */ /* abort(); */ /* } */ if(a[i].e1.size()+a[i].e2 < 20){ a[i].e1 += string(a[i].e2,'0'); a[i].e2 ^= a[i].e2; } if(!a[i].e2) add1(a[i].e1); if(a[i].e1.size()+a[i].e2 > a[i+1].e1.size() || (a[i].e1.size()+a[i].e2 == a[i+1].e1.size() && a[i].e1 > a[i+1].e1)){ int lai = a[i].e1.size()+a[i].e2; int laip1 = a[i+1].e1.size(); int xd = canp1(a[i+1].e1,a[i].e1.substr(0,a[i+1].e1.size()),lai-laip1); if(xd == 2){ ans += lai-laip1; // string tmp = a[i]; a[i+1] = a[i]; } else{ ans += lai-laip1+xd; a[i+1].e2 += lai-laip1+xd; // whatis(lai-laip1+1) // whatis(a[i+1]) /* for(int x = laip1; x < lai+xd; ++x){ */ // whatis(x) // a[i+1] *= 10; /* a[i+1] += '0'; */ /* } */ // whatis(a[i+1]) } } } cout << ans << '\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 | #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define pb push_back #define mp make_pair #define all(a) begin(a),end(a) #define FOR(x,val,to) for(int x=(val);x<int((to));++x) #define FORE(x,val,to) for(auto x=(val);x<=(to);++x) #define FORR(x,arr) for(auto &x: arr) #define FORS(x,plus,arr) for(auto x = begin(arr)+(plus); x != end(arr); ++x) #define FORREV(x,plus,arr) for(auto x = (arr).rbegin()+(plus); x !=(arr).rend(); ++x) #define REE(s_) {cout<<s_<<'\n';exit(0);} #define GET(arr) for(auto &i: (arr)) sc(i) #define whatis(x) cerr << #x << " is " << (x) << endl; #define e1 first #define e2 second #define INF 0x7f7f7f7f typedef std::pair<int,int> pi; typedef std::vector<int> vi; typedef std::vector<std::string> vs; typedef int64_t ll; typedef uint64_t ull; #define umap unordered_map #define uset unordered_set using namespace std; using namespace __gnu_pbds; #ifdef _WIN32 #define getchar_unlocked() getchar() #define _CRT_DISABLE_PERFCRIT_LOCKS #endif template<class L, class R> ostream& operator<<(ostream &os, map<L, R> P) { for(auto const &vv: P)os<<"("<<vv.first<<","<<vv.second<<")"; return os; } template<class T> ostream& operator<<(ostream &os, set<T> V) { os<<"[";for(auto const &vv:V)os<<vv<<","; os<<"]"; return os; } template<class T> ostream& operator<<(ostream &os, vector<T> V) { os<<"[";for(auto const &vv:V)os<<vv<<","; os<<"]"; return os; } template<class L, class R> ostream& operator<<(ostream &os, pair<L, R> P) { os<<"("<<P.first<<","<<P.second<<")"; return os; } inline int fstoi(const string &str){auto it=str.begin();bool neg=0;int num=0;if(*it=='-')neg=1;else num=*it-'0';++it;while(it<str.end()) num=num*10+(*it++-'0');if(neg)num*=-1;return num;} inline void getch(char &x){while(x = getchar_unlocked(), x < 33){;}} inline void getstr(string &str){str.clear(); char cur;while(cur=getchar_unlocked(),cur<33){;}while(cur>32){str+=cur;cur=getchar_unlocked();}} template<typename T> inline bool sc(T &num){ bool neg=0; int c; num=0; while(c=getchar_unlocked(),c<33){if(c == EOF) return false;} if(c=='-'){ neg=1; c=getchar_unlocked(); } for(;c>47;c=getchar_unlocked()) num=num*10+c-48; if(neg) num*=-1; return true;}template<typename T, typename ...Args> inline void sc(T &num, Args &...args){ bool neg=0; int c; num=0; while(c=getchar_unlocked(),c<33){;} if(c=='-'){ neg=1; c=getchar_unlocked(); } for(;c>47;c=getchar_unlocked()) num=num*10+c-48; if(neg) num*=-1; sc(args...); } template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; //s.find_by_order(), s.order_of_key() <- works like lower_bound template<typename T> using ordered_map = tree<T, int, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define N 1000001 //int len(ll a){ // int ret = 0; // while(a) // a /= 10, ++ret; // return ret; //} void add1(string &s){ ++s.back(); auto it = --s.end(); while(*it > '9'){ *it = '0'; if(it == s.begin()){ s.insert(s.begin(),'1'); return; } --it; ++*it; } } int canp1(string a, string b, int df){ // ll bp1 = b+1; if(!df) return 1; if(a == b) return 2; return a < b; } int main(){ ios_base::sync_with_stdio(0);cin.tie(0); // for(ll xdd = 9; xdd < 1e17; xdd = xdd*10+9) // xddd.insert(xdd); int n; sc(n); pair<string,int> a[n]; FORR(i,a) getstr(i.e1), i.e2 = 0; ll ans = 0; FOR(i,0,n-1){ /* if(a[i].size() > 100){ */ /* abort(); */ /* } */ if(a[i].e1.size()+a[i].e2 < 20){ a[i].e1 += string(a[i].e2,'0'); a[i].e2 ^= a[i].e2; } if(!a[i].e2) add1(a[i].e1); if(a[i].e1.size()+a[i].e2 > a[i+1].e1.size() || (a[i].e1.size()+a[i].e2 == a[i+1].e1.size() && a[i].e1 > a[i+1].e1)){ int lai = a[i].e1.size()+a[i].e2; int laip1 = a[i+1].e1.size(); int xd = canp1(a[i+1].e1,a[i].e1.substr(0,a[i+1].e1.size()),lai-laip1); if(xd == 2){ ans += lai-laip1; // string tmp = a[i]; a[i+1] = a[i]; } else{ ans += lai-laip1+xd; a[i+1].e2 += lai-laip1+xd; // whatis(lai-laip1+1) // whatis(a[i+1]) /* for(int x = laip1; x < lai+xd; ++x){ */ // whatis(x) // a[i+1] *= 10; /* a[i+1] += '0'; */ /* } */ // whatis(a[i+1]) } } } cout << ans << '\n'; } |