Submission #1023187

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_from_reverse(i,m,n) for (int i = (n)-1; (i) >= int(m); --(i))
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
typedef long long ll;
using namespace std;
struct interval_t { ll l, r; };
bool operator < (interval_t a, interval_t b) { return make_pair(a.l, a.r) < make_pair(b.l, b.r); }
bool is_mergeable(interval_t a, interval_t b) { return not (a.r <= b.l or b.r <= a.l); }
interval_t merge(interval_t a, interval_t b) { assert (is_mergeable(a, b)); return { min(a.l, b.l), max(a.r, b.r) }; }
interval_t shift(interval_t a, ll b) { return { a.l - b, a.r - b }; }
interval_t adjust(interval_t a, ll b) { ll l = (a.l % b + b) % b; return { l, a.r + (l - a.l) }; }
bool does_include(interval_t a, ll b) { return a.l <= b and b < a.r; }
int main() {
    int n; cin >> n;
    vector<ll> as(n); repeat (i,n) cin >> as[i];
    int ans = 0;
    for (ll e = 1; e <= ll(1e17); e *= 10) {
        repeat_from_reverse (d,1,10) {
            vector<interval_t> xs;
            xs.push_back({ d*e, (d+1)*e });
            for (ll a : as) {
                vector<interval_t> ys = xs;
                for (interval_t x : xs) {
                    ys.push_back(       shift(x, a % (10*e)));
                    ys.push_back(adjust(shift(x, a % (10*e)), 10*e));
                }
                xs.clear();
                whole(sort, ys);
                for (interval_t y : ys) {
                    if (y.r <= 0) continue;
                    if (xs.empty() or not is_mergeable(xs.back(), y)) {
                        xs.push_back(y);
                    } else {
                        xs.back() = merge(xs.back(), y);
                    }
                }
            }
            bool found = false;
            for (interval_t x : xs) {
                if (does_include(x, 0)) {
                    found = true;
                }
            }
            if (found) {
                ans += d;
                break;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result