2222AUnreviewedunratedKimi K2.6 (thinking)

A Wonderful Contest

Progressive hints first, then the full explanation and implementation when you're ready to cash out.

brute force dp math

Original problem

Review status

AI-generated and still unreviewed. Double-check the details before internalizing them.

Hints

Progressive nudges

Open only as much as you need to keep the solve alive.

What is the point value of a single subtask? If you want to score exactly $k=1$ , what must be true about at least one of the $a_i$ ?

If no problem has $a_i = 100$ , every subtask is worth at least $2$ points. Can a contestant ever reach a total of $1$ ? What does that immediately tell you about the answer?

Suppose some problem has $a_i = 100$ , so it alone can produce every integer from $0$ to $100$ . Look at the remaining problems: each of them contributes a score in the range $[0,100]$ . Prove by induction that the sumset of any collection of such problems never contains a gap larger than $100$ .

Let $S$ be the set of scores achievable by the problems other than the one with $a_i=100$ . You now know that consecutive elements of $S$ differ by at most $100$ . The total achievable set is $\bigcup_{y\in S} [y, y+100]$ . Why do these overlapping intervals guarantee coverage of every integer from $0$ to $100n$ ?

The answer is Yes if and only if some $a_i = 100$ . If none equal $100$ , the smallest positive step is $\min(100/a_i) \ge 2$ , so a total of $1$ is impossible. If some equal $100$ , that problem yields the full interval $[0,100]$ , and the others patch the rest because their combined sumset has gaps of at most $100$ , exactly filling $[0,100n]$ .

Observation 1: The smallest step

The $i$ -th problem offers scores $0,\; \frac{100}{a_i},\; 2\cdot\frac{100}{a_i},\; \dots,\; 100.$ Because every $a_i$ divides $100$ , the step size $d_i = \frac{100}{a_i}$ is a positive integer.

Observation 2: Necessity of a unit step

If we need every integer total from $0$ to $100n$ , we certainly need $k=1$ . A contestant’s total is a sum of non-negative integer multiples of the step sizes $d_i$ . The smallest positive value any single problem can contribute is $\min_i d_i$ . Therefore, score $1$ is reachable iff some problem has step $1$ , i.e. $d_i = 1 \iff \frac{100}{a_i}=1 \iff a_i = 100.$ If no $a_i$ equals $100$ , every positive total is at least $2$ , so the answer is immediately No.

Observation 3: Sufficiency when $a_i = 100$

Assume problem $p$ satisfies $a_p = 100$ . It alone yields every integer in $[0,100]$ . Let $S$ be the set of scores achievable by the remaining $n-1$ problems. For each remaining problem $j$ , its score set $T_j$ is a subset of $[0,100]$ containing $0$ . We claim the sorted elements of $S$ have gaps of at most $100$ : $s_{j+1} - s_j \le 100.$

Proof by induction. For one problem the claim is trivial because $\max T_j \le 100$ . Assume it holds for a sumset $S'$ , and let $S = S' + T$ where $T\subseteq[0,100]$ and $0\in T$ . Take any $s\in S$ that is not the maximum. Write $s = s' + t$ .

If $s'$ is not maximal in $S'$ , there exists $s''\in S'$ with $s''-s'\le 100$ . Then $s''+t \in S$ lies in $(s, s+100]$ .
If $s'$ is maximal in $S'$ but $t$ is not maximal in $T$ , pick $t'\in T$ with $t'-t\le 100$ ; then $s'+t'\in S$ lies in $(s, s+100]$ .

Thus a successor always exists within $100$ , proving the claim.

Observation 4: Patching the intervals

The total achievable set is $\bigcup_{y\in S} [y,\; y+100].$ Because consecutive elements of $S$ differ by at most $100$ , these closed intervals overlap (or at least touch). Since $\min S = 0$ and $\max S = 100(n-1)$ , their union is exactly the continuous integer interval $[0,\; 100(n-1)+100] = [0,\; 100n].$ Hence the answer is Yes.

Complexity Analysis

We only need to check whether the input contains the value $100$ .

Time complexity: $O(n)$ per test case.
Memory usage: $O(1)$ .

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

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main() {
    setIO();
    int T;
    if (!(cin >> T)) return 0;
    while (T--) {
        int n;
        cin >> n;
        bool has100 = false;
        for (int i = 0; i < n; ++i) {
            int x;
            cin >> x;
            if (x == 100) has100 = true;
        }
        cout << (has100 ? "Yes" : "No") << '\n';
    }
    return 0;
}

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

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main() {
    setIO();
    int T;
    if (!(cin >> T)) return 0;
    while (T--) {
        int n;
        cin >> n;
        bool has100 = false;
        for (int i = 0; i < n; ++i) {
            int x;
            cin >> x;
            if (x == 100) has100 = true;
        }
        cout << (has100 ? "Yes" : "No") << '\n';
    }
    return 0;
}

View on Codeforces Back to the list

A Wonderful Contest

Progressive nudges

Full explanation

Observation 1: The smallest step

Observation 2: Necessity of a unit step

Observation 3: Sufficiency when $a_i = 100$

Observation 4: Patching the intervals

Complexity Analysis

Generated C++

A Wonderful Contest

Progressive nudges

Full explanation

Observation 1: The smallest step

Observation 2: Necessity of a unit step

Observation 3: Sufficiency when ai=100a_i = 100ai​=100

Observation 4: Patching the intervals

Complexity Analysis

Generated C++

Observation 3: Sufficiency when $a_i = 100$