Editorial for COCI '08 Contest 4 #5 Trezor
Submitting an official solution before solving the problem yourself is a bannable offence.
We say that vaults with a common x-coordinate form a column. There are
Let:
be the total number of vaults in column seen by the guard at ; be the total number of vaults in column seen by the guard at ; be the total number of vaults in column seen by both guards.
Knowing these numbers, we can calculate:
- The number of super-secure vaults in column
as ; - The number of secure vaults in column
as ; - The number of insecure vaults as
.
How do we calculate the number of vaults in a column? Let
The number of integers relatively prime with
A special case is
Now it is obvious that
Comments