A Wonderful Contest

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)$.