Editorial for COCI '12 Contest 1 #4 Ljubomora
Submitting an official solution before solving the problem yourself is a bannable offence.
Let be the lowest possible envy level, and
the largest number of marbles of a single colour. It is not difficult to show that for all numbers
between
and
, inclusive, we can attain an envy level of
.
It follows that binary search can be used to find the requested solution . We can begin with the lower bound of
and upper bound of
. In each step, for a number
halfway between the current bounds, we can check whether it is larger or smaller than
, i.e. whether it is possible to attain an envy level of
.
How can we check that? We can iterate over all colours and divide each of them into as many portions of size as possible. More precisely, if we have
marbles of a given colour, we will make
div
portions of size
, as well as one more portion if we have any leftover marbles (if
does not divide
). After we have distributed all colours in the manner above, if the total number of portions is at most
, we have successfully attained an envy level of
, concluding
. Otherwise, we have to conclude
, since we have made too many portions, which means that at least one child must get more than
marbles.
Comments