Official

A - No Attacking Editorial by evima


When a rook is placed at \((i, j)\), placing pieces on the \(i\)-th row and the \(j\)-th column will be prohibited. Thus, when \(N\) rooks are placed, it is no longer possible to place pieces on any squares, so if \(A > N\), the answer is No.

Let’s consider the case where \(A \leq N\). We consider the maximum number of pawns that can be placed per column when \(A\) rooks are optimally placed.
First, pawns cannot be placed on rows where rooks are placed, so one upper limit is \(N - A\).
Additionally, for every pawn placed in a position other than the first row, the square above it will be unavailable for placing another pawn, resulting in two squares being unavailable for each pawn placed. From this, we can derive another upper limit of \(\left \lfloor \frac{N + 1}{2} \right \rfloor\).
Thus, we have obtained an upper limit of \(\min(N - A, \left \lfloor \frac{N + 1}{2} \right \rfloor)\) pieces (let \(C\) be this number). Conversely, by arranging rooks and pawns as follows, it is possible to place \(C\) pawns per column.

  • Place rooks on the even-numbered rows, such as the second, fourth, \(\dots\). If there are still rooks left after placing them on all even-numbered rows, place them on the odd-numbered rows, such as the first, third, \(\dots\).
  • Next, place pawns on the odd-numbered rows where they can be placed.

There are \(N - A\) columns where pawns can be placed, so at most \((N - A) \times C\) pawns can be placed. Thus, if \((N - A) \times C \geq B\), the answer is Yes; otherwise, the answer is No.
The computational complexity is \(\mathrm{O}(1)\) per test case, which is sufficiently small.

posted:
last update: