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