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.

Author: Riolku

Hint

Binary Search

Solution

WLOG $x \le y$ ~x \le y~. If all moves are made with the long part of the move going vertically, then $x$ ~x~ must have the same parity as the operation count.

Otherwise, the moves we make horizontally, call it $h$ ~h~, and the vertical moves $v$ ~v~, must satisfy the inequalities $v + h \cdot k \ge x$ ~v + h \cdot k \ge x~ and $v \cdot k + h \ge y$ ~v \cdot k + h \ge y~.

Since we binary search, we know the value of $v + h$ ~v + h~, call it $m$ ~m~, so we have $m + h \cdot (k - 1) \ge x$ ~m + h \cdot (k - 1) \ge x~ or $h \ge \frac{x - m}{k - 1}$ ~h \ge \frac{x - m}{k - 1}~ and a similar equation for $v$ ~v~.

We can then compare our minimum $h$ ~h~ value and minimum $v$ ~v~ value to see if a given $m$ ~m~ is possible.

Comments

There are no comments at the moment.