H. Score Values

Updated May 21, 2026

Track ICPC

Year 2025

Statement Text + PDF

TeXC++Statement textStatement PDF

Problem statement

Problem Statement

Formatted from the contest statement text, with sample tests broken out into copyable blocks.

Statement text Statement PDF

Time limit 2 seconds

Ever since you arrived at your university, you have been a tireless advocate for introducing the brand-new martial-arts- plus-card-based sport of Contact Bridge to the school (and the world). Finally, after a great deal of (really persistent and annoying) advocacy on your part, you have obtained per- mission and funding from your dean to build a grand new arena for the sport! Well, technically it is not so much an “arena” as a “broom closet,” and maybe not “grand” so much as “cramped,” and the “new” is also debatable. But the sport of the future has to start somewhere! Generated by ChatGPT

Unfortunately, you just realized that you are going to need a score display in order to run the games. In Contact Bridge, the score for a team starts at 0 and, after various repeatable actions, may be incremented by certain fixed amounts. There is also a maximum value – if the team’s score would be incremented above the maximum, it will instead be capped there. You want the team’s score to be visible at all times, so you will need to prepare some signs, each with a single digit printed on it, that can be arranged to show the score. Unfortunately the dean’s “funding” is running short, and these signs are expensive. Figure out the minimum set of signs you need to purchase to show any score that is possible to achieve during the game. Note that you won’t need any 9 signs, as any 6 sign can be turned upside-down to make a 9.

Input

The first line of input contains two integers m and n, where m (1 ≤ m ≤ 1018 ) is the maximum score value, and n (1 ≤ n ≤ 10) is the number of different ways of scoring. This is followed by n lines, each containing an integer p (1 ≤ p ≤ 1 000), which is the number of points awarded for a type of action in the game. No two types of action are awarded the same number of points.

Output

For each digit from 0 to 8 in increasing order, output two integers: the digit and the number of signs with that digit that you need to purchase. Omit digits where the number of signs needed is 0.

Sample Tests

Sample 1

Sample Input

Sample Output

Sample 2

Sample Input

967 1
1000

Sample Output

0 1
6 2
7 1

Editorial

The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.

Raw TeX

Key Observations

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.
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.
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.
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.
The cap makes the value $m$ reachable even if $m$ itself is not a multiple of $g$, so we must also test $m$ explicitly.

Algorithm

Compute $g=\gcd(p_1,\dots,p_n)$ and divide all scores by $g$.
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 dist[r] for every residue $r$.
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.
Enumerate all reachable values below $gB$ explicitly and update the best digit counts.
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).
Also evaluate the digits of $m$ itself and take the maximum.

Correctness Proof

We prove that the algorithm returns the correct answer.

Lemma 1.

For every residue $r$ modulo the smallest reduced score $a$, dist[r] computed by Dijkstra is the smallest reachable reduced score congruent to $r$.

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. □

Lemma 2.

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

Proof.

Take any reduced value $y \ge B$. Let $r=y \bmod a$. By definition, dist[r] is reachable and has the same residue as $y$, and dist[r] \le B \le y$. Therefore $y-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. □

Lemma 3.

The digit DP computes, for each digit weight function, the largest total weight among all reachable scores in the long suffix interval.

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. □

Theorem.

The algorithm outputs the correct answer for every valid input.

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. □

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.

Implementation Notes

The DP handles leading zeros separately so that the score $0$ contributes one zero digit.
For digit $6$, the weight is assigned to both digits $6$ and $9$ because the same sign can display either one.

C++

Clean code view with a raw-file link when you want the original source.

Raw file

#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;
}

Show raw files

TeX write-upcompetitive_programming/icpc/2025/H-score-values/solution.texC++ implementationcompetitive_programming/icpc/2025/H-score-values/solution.cppStatement textcompetitive_programming/icpc/2025/H-score-values/statement.txtStatement PDFcompetitive_programming/icpc/2025/H-score-values/statement.pdfMetadatacompetitive_programming/icpc/2025/H-score-values/meta.jsonYear packetcompetitive_programming/icpc/2025/contest_problems.pdf

H. Score Values

Problem Statement

Input

Output

Sample Tests

Editorial

Key Observations

Algorithm

Correctness Proof

Complexity Analysis

Implementation Notes

Code

Source Files and Assets