Editorial for DMOPC '22 Contest 4 P3 - K-Knight
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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Hint
Binary Search
Solution
WLOG . If all moves are made with the long part of the move going vertically, then
must have the same parity as the operation count.
Otherwise, the moves we make horizontally, call it , and the vertical moves
, must satisfy the inequalities
and
.
Since we binary search, we know the value of , call it
, so we have
or
and a similar equation for
.
We can then compare our minimum value and minimum
value to see if a given
is possible.
Comments