Editorial for COCI '09 Contest 2 #3 Kutevi


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.

Let Ak be a set of angles {a1,a2,,an} that Mirko can construct using at most k additions or subtractions of the initial angles. From Ak we obtain Ak+1 by copying Ak into Ak+1 and then for each initial angle adding it to all angles in Ak inserting the resulting angle in Ak+1, if it is not already in. It can be easily seen that Ak can contain at most 360 angles, because there are only 360 possible values. Because the smallest number of angles we can add to Ak+1 is 1, because if we did not add any new angles we could terminate our algorithm, we will perform at most 360 steps at which point A360 will contain all angles Mirko can construct. Of course A0={0}. This can easily translate into an efficient algorithm for this task. First we precalculate A360 and then for each angle Slavko gives, simply check if it is contained in A360.


Comments

There are no comments at the moment.