Editorial for WC '17 Finals J1 - Cownterintelligence


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.

Upon inputting each cow i's moo frequency M_i, we'll need to determine whether it's a power-of-2 multiple of F, and output the number i if it's not.

One way to check this is to initialize a variable x to be equal to F, and then repeatedly multiply x by 2 while checking if it's equal to M_i at each iteration. If we do find a value of x which is equal to M_i, then we know that cow i isn't an imposter, and we'll want to skip over it. On the other hand, if x never becomes equal to M_i and instead gets to be larger than M_i, then we know that cow i is an alien imposter.


Comments

There are no comments at the moment.