Jammer

Research first: the canonical statement is the Codeforces problem page: https://codeforces.com/contest/2199/problem/G. The official Kotlin Heroes 14 editorial page lists 2199G - Jammer and includes adedalic's official solution, although the tutorial text itself is still loading: https://codeforces.com/blog/entry/151783. The official code uses the same dimension-swap plus integer-square-root interval counting derived here.

Let the jammer be centered at $(x,y)$, and let $D$ be its radius-$r$ disk.

The key observation is that $D$ catches every monotone path iff it touches both opposite boundary chains:

• the upper-left chain: left side or top side;
• the lower-right chain: bottom side or right side.

In formulas, those are

$$x\le r \quad\text{or}\quad y\ge m-r,$$

and

$$n-x\le r \quad\text{or}\quad y\le r.$$

Why necessary? If the disk misses the upper-left chain, the robot can go straight up along the left border and then right along the top border, avoiding the jammer. If it misses the lower-right chain, the robot can go right along the bottom border and then up along the right border. So missing either chain means the jammer is not guaranteed to work.

Why sufficient? A connected disk touching both chains separates the southwest corner $(0,0)$ from the northeast corner $(n,m)$ inside the rectangle. Any monotone route must cross it. Also, this is still valid for the statement's lattice-point interception: every robot move is a unit horizontal/vertical segment between integer points, and the center is integer. For such a unit segment, if it intersects the disk, one endpoint is inside the disk too. So every route has some integer path point within distance $r$.

Now apply the stealth constraints:

$$x^2+y^2>r^2,$$ $$(n-x)^2+(m-y)^2>r^2.$$

The problem is symmetric under swapping axes, so assume $n\le m$ after swapping if needed. Then loop over $x=0,1,\dots,n$. This is fine because $n\cdot m\le 10^9$, so the smaller side is small enough.

For a fixed $x$, all valid $y$ values form one interval $[L,R]$.

Lower bound:

If $x\le r$, the disk already touches the left side, so the upper-left wall condition is satisfied. We only need to avoid covering the start:

$$x^2+y^2>r^2.$$

Therefore

$$L=\left\lfloor\sqrt{r^2-x^2}\right\rfloor+1.$$

If $x>r$, the start is automatically safe, but the disk must touch the top side:

$$L=\max(0,m-r).$$

Upper bound:

If $n-x\le r$, the disk already touches the right side, so the lower-right wall condition is satisfied. We only need to avoid covering the finish:

$$(n-x)^2+(m-y)^2>r^2.$$

Thus

$$R=m-1-\left\lfloor\sqrt{r^2-(n-x)^2}\right\rfloor.$$

If $n-x>r$, the finish is automatically safe, but the disk must touch the bottom side:

$$R=\min(m,r).$$

For this fixed $x$, contribute

$$\max(0,R-L+1).$$

Use a corrected integer square root. Raw floating point is how you donate a WA to the judge for no reason.

Complexity: $O(t\min(n,m))$ time and $O(1)$ memory.