Editorial for COCI '10 Contest 5 #3 Brodovi

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.

First, let's decrease all given day indices by $1$ ~1~. This way, a ship with visit period $K$ ~K~ will come to the harbour in days $0, K, 2K, \dots$ ~0, K, 2K, \dots~

Let $A$ ~A~ be the first entertaining day after the day $0$ ~0~. It is clear that there is a ship with visit period $A$ ~A~. This ship will also arrive to the harbour in days $2A$ ~2A~, $3A$ ~3A~, etc. Therefore, we no longer need to worry about entertaining days divisible by $A$ ~A~, since this ship will visit them all.

We repeat this procedure, ignoring the days covered by previously found ships.

When there are no more entertaining days that we must take care of, we are done and the solution is equal to the number of ships found.

Complexity is $\mathcal O(N^2)$ ~\mathcal O(N^2)~, because for each ship found ( $N$ ~N~ ships max) we must traverse all the entertaining days ( $N$ ~N~).

Comments

There are no comments at the moment.