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 A_k be a set of angles \{a_1, a_2, \dots, a_n\} that Mirko can construct using at most k additions or subtractions of the initial angles. From A_k we obtain A_{k+1} by copying A_k into A_{k+1} and then for each initial angle adding it to all angles in A_k inserting the resulting angle in A_{k+1}, if it is not already in. It can be easily seen that A_k can contain at most 360 angles, because there are only 360 possible values. Because the smallest number of angles we can add to A_{k+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 A_{360} will contain all angles Mirko can construct. Of course A_0 = \{0\}. This can easily translate into an efficient algorithm for this task. First we precalculate A_{360} and then for each angle Slavko gives, simply check if it is contained in A_{360}.


Comments

There are no comments at the moment.