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