Editorial for COCI '08 Contest 1 #4 Jez

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.

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 $K$ ~K~.

The number of visited cells in a row can be calculated from $R$ ~R~, $S$ ~S~ and the number of diagonals traversed.

What remains is to calculate, for two integers $x$ ~x~ and $y_\max$ ~y_\max~, how many integers $y$ ~y~ between $1$ ~1~ and $y_\max$ ~y_\max~ there are such that $x \mathbin{\&} y$ ~x \mathbin{\&} y~ is zero, where $\&$ ~\&~ is the "bitwise and" operator. Consider the binary representation of $y_\max$ ~y_\max~ and let $k$ ~k~ be the position of the most significant binary one. First we calculate how many integers $y$ ~y~ there are with a binary zero in position $k$ ~k~ (all these numbers are less than $y_\max$ ~y_\max~) sharing no binary ones with $x$ ~x~. Then we calculate the same for $y$ ~y~ with a binary zero in position $k$ ~k~. If $x$ ~x~ has a binary one in position $k$ ~k~, then there are more $y$ ~y~ such that $x \mathbin{\&} y = 0$ ~x \mathbin{\&} y = 0~ and we are done. Otherwise, look for the next highest binary one in $y_\max$ ~y_\max~ and repeat.

For example, if $y_\max = 10110$ ~y_\max = 10110~, then for $k = 4$ ~k = 4~ we count all $y$ ~y~ between $00000$ ~00000~ and $01111$ ~01111~. For $k = 2$ ~k = 2~ we will count all $y$ ~y~ between $10000$ ~10000~ and $10011$ ~10011~ and for $k = 1$ ~k = 1~ all $y$ ~y~ between $10100$ ~10100~ and $10101$ ~10101~.

Comments

There are no comments at the moment.