USACO MAR07 Problem 'fireshow' Analysis

by Bruce Merry

A trivial solution is to iterate over all the seconds in the range, and check whether it is a multiple of the period of any of the cannons. It can be made slightly more efficient by keeping in mind that the modulus (%) operator is quite slow. Instead, make an array of booleans and for each cannon, fill in all the times at which the cannon fires. The answer is then just the number of set flags in the array.