Submission #1003958

---

Source Code Expand

#include <iostream>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cassert>
#include <algorithm>
#include <iterator>
#include <string>
#include <vector>
#include <list>
#include <deque>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <tuple>
#include <queue>
#include <stack>
#include <functional>
#include <utility>
#include <complex>
#include <bitset>
#include <numeric>
#include <random>
using namespace std;

#define REP(i,n) for(int (i)=0; (i)<(n) ;++(i))
#define REPN(i,a,n) FOR((i),(a),(a)+(n))
#define FOR(i,a,b) for(int (i)=(a); (i)<(b) ;++(i))
#define PB push_back
#define MP make_pair
#define SE second
#define FI first
#define DBG(a) cerr<<(a)<<endl;
#define ALL(v) (v).begin(),(v).end()
typedef long long LL;  typedef pair<LL, LL> PLL; typedef vector<LL> VLL;
const LL LINF=334ll<<53; const int INF=15<<26; const LL MOD=1E9+7;
vector<long long> p;
LL n;

long long pow_(long long a, long long n){
    if(n==0) return 1;
    long long re=pow_(a*a,n/2);
    if(n%2==1) re= re*a;
    return re;
}
vector<pair<LL,LL>> conn (vector<pair<LL,LL>> a, vector<pair<LL,LL>> b){
    REP(i,b.size()){
        a.push_back(make_pair(b[i].FI,b[i].SE));
    }
    sort(ALL(a));
    FOR(i,1,a.size()){
        if(a[i].FI<=a[i-1].SE){
            a[i].SE=max(a[i].SE,a[i-1].SE);
            a[i].FI=a[i-1].FI;
            a[i-1].FI=a[i-1].SE=0;
        }
    }
    a.erase(remove(a.begin(),a.end(),make_pair(0ll,0ll)),a.end());
    return a;
}
bool chk(LL a, vector<pair<LL,LL>> &b){
    for(auto x : b){
        if(a>=x.FI && a<=x.SE) return true;
    }
    return false;
}
int solve(int d){
    vector<pair<LL,LL>> ng;
    LL mod=pow_(10,d+1);
    ng.push_back(MP(pow_(10,d)*9,pow_(10,d+1)-1));
    REP(i,n){
        vector<pair<LL,LL>> neu;
        for(auto x: ng){
            LL l=(x.FI-p[i]%mod+mod)%mod;
            LL u=(x.SE-p[i]%mod+mod)%mod;
            if(l==0 or l>u) return 9;
            neu.push_back(make_pair(l,u));
        }
        ng=conn(ng,neu);
    }
    int re=0;
    FOR(i,0,9)if(chk(pow_(10,d)*i,ng)){
        re=9-i;
        break;
    }
    return re;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> n;
    REP(i,n){
        LL tmp;cin >> tmp;
        p.push_back(tmp);
    }

    int ans=0;
    REP(i,17) {
        ans+=solve(i);
    }
    cout << ans <<endl;

    return 0;
}

Submission Info

Judge Result