Editorial for COCI '08 Contest 1 #4 Jez
Submitting an official solution before solving the problem yourself is a bannable offence.
There are three parts to the solution:
- Find the number of complete diagonals the hedgehog walks on and also how many cells on the last diagonal.
- For every row:
- Calculate how many cells in the row the hedgehog visits;
- Calculate how many of those cells are grey.
For the first part, it suffices to add diagonals one by one, stopping when the total number of cells visited is more than .
The number of visited cells in a row can be calculated from ,
and the number of diagonals traversed.
What remains is to calculate, for two integers and
, how many integers
between
and
there are such that
is zero, where
is the "bitwise and" operator. Consider the binary representation of
and let
be the position of the most significant binary one. First we calculate how many integers
there are with a binary zero in position
(all these numbers are less than
) sharing no binary ones with
. Then we calculate the same for
with a binary zero in position
. If
has a binary one in position
, then there are more
such that
and we are done. Otherwise, look for the next highest binary one in
and repeat.
For example, if , then for
we count all
between
and
. For
we will count all
between
and
and for
all
between
and
.
Comments