Preface: what is a “constructive problem”?

A “constructive problem” is a problem that asks to “construct something that satisfies the conditions and output it” like this problem. Construction problems require a sort of flash of inspiration, so some of you may have been confused, and others may have felt easier to solve if you are used to puzzles.

We will introduce some hints first, and then finally show you an answer.

Hint 1: the knowledge of \(N\)-ary notation (positional number system)

The positional number system is a way to represent a number. Especially, the decimal system is used in our daily life, and binary and hexadecimal notations are widely used in the world of programming.
We will describe how to express a integer value \(n\) in base \(N\). \(n\) can be uniquely expressed with a sequence \((a_0,a_1,\dots,a_r)\) of integers between \(0\) and \(N-1\) (inclusive) as follows:

\[n = a_r N^r + \dots + a_2 N^2 + a_1 N + a_0.\]

The concatenation of the sequence

\[a_ra_{r-1} \dots a_2a_1a_0\]

is the \(N\)-ary expression of the integer. This is the \(N\)-ary notation.

• In the decimal notation which we usually use, it may be easier to think that \(N^0,N^1,N^2,N^3,\dots\) correspond to \(1,10,100,1000,\dots\), respectively.

For example, let us express an integer expressed as \(251\) in decimal to \(7\)-ary (septenary) notation. \(251\) can be expressed as:

\[251 = 5 \times 7^2 + 0 \times 7 + 6,\]

so \(251\) can be written as \(506\) in base \(7\).

In general, we can express every non-negative integer less than or equal to \(p^d - 1\) in base \(p\) between \(1\) and \(d\) digits. For example, every non-negative integer less than or equal to \(10^4-1 = 9999\) can be written with \(4\)-our-less-digit decimal notation.

Such knowledge of \(N\)-ary notation is a large hint for this problem.

Hint 2: How can we solve the problem for \(W = 999\)?

Based on the concept of \(N\)-ary number we introduce above, let us solve the problem for \(W=999\) with decimals.
Every integer less than or equal to \(10^3 - 1 = 999\) cane be expressed with integers \(a,b\), and \(c\) between \(1\) and \(9\) (inclusive) as

\[n = a \times 10^2 + b \times 10 + c.\]

So let us prepare weights with masses of the following \(27\) numbers corresponding to \(a \times 10^2,b \times 10 ,c\):

• \(1,2,3,4,5,6,7,8,9\)
• \(10,20,30,40,50,60,70,80,90\)
• \(100,200,300,400,500,600,700,800,900\)

In fact, the set of these \(27\) weights is the answer for \(W=999\).
Let us confirm the fact. For example, \(n=251\) can be expressed as

\[251 = 2 \times 10^2 + 5 \times 10 + 1,\]

so we can use three weights of masses \(200, 50, 1\) for a total mass of \(251\).

Also, for \(n = 401\), we have

\[401 = 4 \times 10^2 + 0 \times 10 + 1.\]

In that case, we don’t need a weight corresponding to the \(10\)’s place; with a weight of mass \(400\) and another of \(1\), we can get the sum of \(401\).

When a general \(n\) such that \(1 \leq n \leq 999\) is expressed as

\[n = a \times 10^2 + b \times 10 + c,\]

we can

• choose the weight of mass \(a \times 100\) if \(1 \leq a\),
• choose the weight of mass \(b \times 10\) if \(1 \leq b\),
• choose the weight of mass \(c \times 1\) if \(1 \leq c\),

so that we can obtain a total mass of \(n\) with \(3\) or less weights.
Therefore, we can solve the problem for \(W=999\) with \(27\) weights. We can solve \(W=10^6\) in the same way.

Hint 3: it is sufficient to solve \(W = 10^6\)

In fact, this problem can be solved independent of the input: we can just output the answer for \(W = 10^6\). This is because an output that is accepted for \(W=10^6\) satisfies the condition that “every integer \(n\) such that \(1 \leq n \leq 10^6\) is a good integer,” and thus satisfies the conditions of good integers even when \(W < 10^6\).

Solution

For those who want to come up with an answer by yourself with all those hints, we hid the answer inside the tab below.

(Press here to reveal the solution)

The following $297$ weights satisfies the answer:

• $1,2,3\dots,98,99$
• $100,200,300,\dots,9800,9900$
• $10^4,2\times 10^4,3\times 10^4,\dots,98\times 10^4,99\times 10^4$

(Proof) It is sufficient to prove that every integer $1 \leq n \leq 10^6$ is a good integer. We will split into two cases: when $1 \leq n \leq 10^6-1$, and $n=10^6$. (1) When $1 \leq n \leq 10^6-1$ Every integer $n$ less than or equal to $999999 = 10^6 -1$ can be expressed with integers $a,b$, and $c$ between $0$ and $99$ (inclusive) as $$n = a \times (10^2)^2 + b \times 10^2 + c,$$ so we can prepare weights just as in $W=999$ as follows so that we can choose at most $3$ weights to make the sum of masses $n$. Therefore, $n$ is a good integer.

• If $1 \leq a$, choose the weight of mass $a \times 10^4$
• If $1 \leq b$, choose the weight of mass $b \times 100$
• If $1 \leq c$, choose the weight of mass $c \times 1$

(2) If $n=10^6$ $10^6$ can be made with a mass of weight $99 \times 10^4$ and another of $10^4$. Therefore, $n$ is a good integer. [Sample code, C++](https://atcoder.jp/contests/abc251/submissions/31639177)