Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
First, let us determine the minimum number of integers needed to obtain the average of
.
Let
be the solution to the problem and let
. The following holds:

It can be inferred that the right side of the equation is an integer.
can be expressed in the form of a reduced fraction
, where
and
are relatively prime.

The equation holds if and only if
is a multiple of
. Therefore, the minimum
is not less than
. We now show how to obtain a solution where
.
Observe that with
integers we can obtain any sum in the interval
. Moreover,
. Considering these facts, the number of each integer can be found with a greedy algorithm. Starting from the greatest one, we pick each integer maximum number of times, such that it is possible that the remaining sum can be obtained using the remaining number of integers.
Comments