ICPC 2025 - H. Score Values

#include <bits/stdc++.h>
using namespace std;

using int64 = long long;

namespace {

const int64 INF = (1LL << 60);
const int64 NEG = -(1LL << 60);

int64 gcd64(int64 a, int64 b) {
    return b == 0 ? a : gcd64(b, a % b);
}

vector<int> count_digits(int64 x) {
    vector<int> cnt(10, 0);
    if (x == 0) {
        cnt[0] = 1;
        return cnt;
    }
    while (x > 0) {
        cnt[x % 10]++;
        x /= 10;
    }
    return cnt;
}

vector<int> to_padded_digits(int64 x, int len) {
    string s = to_string(x);
    if ((int)s.size() < len) {
        s = string(len - (int)s.size(), '0') + s;
    }
    vector<int> digits(len);
    for (int i = 0; i < len; ++i) {
        digits[i] = s[i] - '0';
    }
    return digits;
}

int dp_mod;
int digit_len;
vector<int> low_d, high_d;
int64 digit_weight[10];
static int64 memo[20][1001][2][2][2];
static unsigned char seen[20][1001][2][2][2];

int64 solve_dp(int pos, int rem, int tight_low, int tight_high, int started) {
    if (pos == digit_len) {
        if (rem == 0) {
            return started ? 0LL : digit_weight[0];
        }
        return NEG;
    }

    int64& ans = memo[pos][rem][tight_low][tight_high][started];
    if (seen[pos][rem][tight_low][tight_high][started]) {
        return ans;
    }
    seen[pos][rem][tight_low][tight_high][started] = 1;
    ans = NEG;

    int lo = tight_low ? low_d[pos] : 0;
    int hi = tight_high ? high_d[pos] : 9;
    for (int d = lo; d <= hi; ++d) {
        int next_started = started || (d != 0);
        int64 add = next_started ? digit_weight[d] : 0LL;
        int next_rem = (rem * 10 + d) % dp_mod;
        int64 suffix = solve_dp(
            pos + 1,
            next_rem,
            tight_low && (d == low_d[pos]),
            tight_high && (d == high_d[pos]),
            next_started
        );
        if (suffix != NEG) {
            ans = max(ans, add + suffix);
        }
    }
    return ans;
}

int64 max_weighted_digits(int64 lo, int64 hi, int mod, const vector<int>& w) {
    if (lo > hi) {
        return NEG;
    }
    string s = to_string(hi);
    digit_len = (int)s.size();
    low_d = to_padded_digits(lo, digit_len);
    high_d.resize(digit_len);
    for (int i = 0; i < digit_len; ++i) {
        high_d[i] = s[i] - '0';
    }
    dp_mod = mod;
    for (int i = 0; i < 10; ++i) {
        digit_weight[i] = w[i];
    }
    memset(seen, 0, sizeof(seen));
    return solve_dp(0, 0, 1, 1, 0);
}

}  // namespace

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

    int64 m;
    int n;
    cin >> m >> n;
    vector<int> p(n);
    for (int i = 0; i < n; ++i) {
        cin >> p[i];
    }

    int64 g = 0;
    for (int x : p) {
        g = gcd64(g, x);
    }

    vector<int> q(n);
    for (int i = 0; i < n; ++i) {
        q[i] = p[i] / g;
    }

    int a = *min_element(q.begin(), q.end());
    vector<int64> dist(a, INF);
    priority_queue<pair<int64, int>, vector<pair<int64, int>>, greater<pair<int64, int>>> pq;
    dist[0] = 0;
    pq.push({0, 0});
    while (!pq.empty()) {
        pair<int64, int> cur = pq.top();
        pq.pop();
        if (cur.first != dist[cur.second]) {
            continue;
        }
        for (int w : q) {
            int nxt = (cur.second + w) % a;
            int64 nd = cur.first + w;
            if (nd < dist[nxt]) {
                dist[nxt] = nd;
                pq.push({nd, nxt});
            }
        }
    }

    int64 conductor = 0;
    for (int64 x : dist) {
        conductor = max(conductor, x);
    }

    int64 max_reduced = m / g;
    vector<int64> answer(9, 0);

    int64 brute_upto = min(max_reduced, conductor - 1);
    if (conductor == 0) {
        brute_upto = -1;
    }
    for (int64 y = 0; y <= brute_upto; ++y) {
        if (y >= dist[(int)(y % a)]) {
            vector<int> cnt = count_digits(y * g);
            for (int d = 0; d <= 8; ++d) {
                int64 cur = (d == 6 ? (int64)cnt[6] + cnt[9] : cnt[d]);
                answer[d] = max(answer[d], cur);
            }
        }
    }

    int64 suffix_lo = conductor * g;
    if (max_reduced >= conductor) {
        for (int d = 0; d <= 8; ++d) {
            vector<int> w(10, 0);
            if (d == 6) {
                w[6] = 1;
                w[9] = 1;
            } else {
                w[d] = 1;
            }
            answer[d] = max(answer[d], max_weighted_digits(suffix_lo, m, (int)g, w));
        }
    }

    vector<int> cntm = count_digits(m);
    for (int d = 0; d <= 8; ++d) {
        int64 cur = (d == 6 ? (int64)cntm[6] + cntm[9] : cntm[d]);
        answer[d] = max(answer[d], cur);
    }

    for (int d = 0; d <= 8; ++d) {
        if (answer[d] > 0) {
            cout << d << ' ' << answer[d] << '\n';
        }
    }
    return 0;
}

\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{enumitem}

\title{ICPC World Finals 2025\\H. Score Values}
\author{}
\date{}

\begin{document}
\maketitle

\section*{Problem Summary}

We can increase the score by any of the given point values, and whenever the score would exceed $m$ it
is capped to exactly $m$. We must determine, for every digit $0$ through $8$, the maximum number of
times that digit can appear in any reachable score. Digit $9$ is merged into digit $6$ because a $6$ sign
can be turned upside down.

\section*{Key Observations}

\begin{itemize}[leftmargin=*]
    \item Ignoring the cap for a moment, the reachable scores form a numerical semigroup generated by the
    point values. Let $g$ be their gcd. Only multiples of $g$ can appear before the cap is hit.
    \item Divide all point values by $g$, and let $a$ be the smallest reduced value.
    Using Dijkstra on residues modulo $a$, we can compute for every residue the smallest reachable value
    with that residue.
    \item From the classical semigroup criterion, once we know these smallest values, every sufficiently
    large number with the correct residue is reachable. Therefore there is a finite exceptional prefix, and
    after that all multiples of $g$ are reachable.
    \item The finite prefix can be enumerated directly.
    On the long suffix interval, the problem becomes:
    among all numbers in $[L,m]$ that are congruent to $0 \pmod g$, maximize the weighted digit count.
    This is a standard digit-DP problem.
    \item The cap makes the value $m$ reachable even if $m$ itself is not a multiple of $g$, so we must also
    test $m$ explicitly.
\end{itemize}

\section*{Algorithm}

\begin{enumerate}[leftmargin=*]
    \item Compute $g=\gcd(p_1,\dots,p_n)$ and divide all scores by $g$.
    \item Let $a$ be the smallest reduced score.
    Run Dijkstra on the graph of residues modulo $a$, where adding a reduced score is one edge.
    This gives the smallest reachable reduced value \texttt{dist[r]} for every residue $r$.
    \item Let $B=\max_r \texttt{dist[r]}$.
    Then every reduced value $y \ge B$ is reachable iff $y \equiv 0 \pmod g$ after scaling back, so every
    multiple of $g$ in $[gB,m]$ is reachable.
    \item Enumerate all reachable values below $gB$ explicitly and update the best digit counts.
    \item For each digit $d \in \{0,\dots,8\}$, run a digit DP on the interval $[gB,m]$ with the modulus
    condition ``number is divisible by $g$'' and weight $1$ on digit $d$ (or on both digits $6$ and $9$ for
    the merged case).
    \item Also evaluate the digits of $m$ itself and take the maximum.
\end{enumerate}

\section*{Correctness Proof}

We prove that the algorithm returns the correct answer.

\paragraph{Lemma 1.}
For every residue $r$ modulo the smallest reduced score $a$, \texttt{dist[r]} computed by Dijkstra is the
smallest reachable reduced score congruent to $r$.

\paragraph{Proof.}
The residue graph has one vertex for each residue modulo $a$. Traversing an edge labeled by a reduced
score $q$ changes residue by $q$ and increases the total reduced score by exactly $q$.
Thus every walk corresponds to a reachable reduced score with the resulting residue, and vice versa.
All edge weights are positive, so Dijkstra returns the shortest path to every residue, i.e.\ the smallest
reachable reduced score with that residue. \qed

\paragraph{Lemma 2.}
Every multiple of $g$ whose reduced value is at least $B=\max_r \texttt{dist[r]}$ is reachable.

\paragraph{Proof.}
Take any reduced value $y \ge B$.
Let $r=y \bmod a$.
By definition, \texttt{dist[r]} is reachable and has the same residue as $y$, and
\texttt{dist[r]} \le B \le y$.
Therefore $y-\texttt{dist[r]}$ is a nonnegative multiple of $a$, so by adding the smallest reduced score
$a$ enough times we can reach $y$. Scaling back by $g$ proves the claim. \qed

\paragraph{Lemma 3.}
The digit DP computes, for each digit weight function, the largest total weight among all reachable scores
in the long suffix interval.

\paragraph{Proof.}
By Lemma 2, the long suffix contains exactly the multiples of $g$ in that interval.
The digit DP enumerates precisely those integers in the interval that satisfy the modulus condition
``value $\equiv 0 \pmod g$'' and maximizes the chosen digit weight. Therefore it returns the correct best
digit count on the suffix. \qed

\paragraph{Theorem.}
The algorithm outputs the correct answer for every valid input.

\paragraph{Proof.}
Every reachable score is either in the finite exceptional prefix, in the suffix covered by Lemma 3, or is
the capped score $m$ itself. The program checks all three possibilities. By Lemma 1 the prefix boundary
is computed correctly, by Lemma 2 no reachable suffix value is missed, and by Lemma 3 the best digit
count on the suffix is computed exactly. Therefore the maximum reported for each digit is correct. \qed

\section*{Complexity Analysis}

The residue Dijkstra uses $a \le 1000$ states and $n \le 10$ transitions per state, so it is tiny.
The digit DP has at most $19 \cdot 1000 \cdot 2 \cdot 2 \cdot 2$ states and is run once for each of the
$9$ reported digits. The memory usage is dominated by the DP table and is also small.

\section*{Implementation Notes}

\begin{itemize}[leftmargin=*]
    \item The DP handles leading zeros separately so that the score $0$ contributes one zero digit.
    \item For digit $6$, the weight is assigned to both digits $6$ and $9$ because the same sign can display
    either one.
\end{itemize}

\end{document}