Editorial for COCI '09 Contest 2 #3 Kutevi
Submitting an official solution before solving the problem yourself is a bannable offence.
Let be a set of angles
that Mirko can construct using at most
additions or subtractions of the initial angles. From
we obtain
by copying
into
and then for each initial angle adding it to all angles in
inserting the resulting angle in
, if it is not already in. It can be easily seen that
can contain at most
angles, because there are only
possible values. Because the smallest number of angles we can add to
is
, because if we did not add any new angles we could terminate our algorithm, we will perform at most
steps at which point
will contain all angles Mirko can construct. Of course
. This can easily translate into an efficient algorithm for this task. First we precalculate
and then for each angle Slavko gives, simply check if it is contained in
.
Comments