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