We'll use the terms red cells and red squares for cells and squares with flattened grass. The other cells and squares are white. Using the alien device at some coordinates is now equivalent to checking the color of a cell.

The process of finding the solution consists of two stages. The first stage is to determine the side length ~M~ of one square of the chessboard and the center ~(X_C, Y_C)~ of the red square ~F~ containing the given red cell ~(X_0, Y_0)~. The second stage is to move from ~(X_C, Y_C)~ to the center of the entire crop formation (using shifts of length ~M~ or ~2M~ along each coordinate).

The key part of this task is efficiently solving the first stage. In order to find ~M~, we should find:

• ~X_R~ — the rightmost x-coordinate of cells in ~F~,
• ~X_L~ — the leftmost x-coordinate of cells in ~F~, and
• ~Y_B~ — the bottom y-coordinate of cells in ~F~.

We describe several approaches for finding ~X_R~; it is trivial to adapt them for finding ~X_L~ and ~Y_B~.

The most obvious algorithm checks the colors of cells ~(X_0+1, Y_0)~, ~(X_0+2, Y_0)~, ~(X_0+3, Y_0)~ etc., stopping at the first white cell ~(X_R+1, Y_0)~ and using ~M~ queries in the worst case. This approach would score 40 points, as described in the Grading section of the task description.

To cut down on the number of queries, let's instead check the color of cells ~(X_0+1, Y_0), (X_0+2, Y_0), (X_0+4, Y_0), \dots, (X_0+2^k, Y_0), \dots~, stopping at the cell we call ~C_{last}~. This is the first white cell of the sequence or the first cell outside the meadow boundaries (we must be careful not to query the device in the latter case). It can be shown that all red cells left of ~C_{last}~ must belong to the square ~F~ and not to some other red square. Let ~C_{previous}~ be the rightmost red cell left of ~C_{last}~. We have used at most ~\log_2 M~ queries so far.

Now we could reset ~X_0 = C_{previous}~ and repeat the procedure described in the last paragraph until ~[C_{previous}, C_{last}]~ contains only 2 cells, after which ~C_{previous} = (X_R, Y_0)~. However, here we have used ~(\log_2 M)^2~ queries in the worst case, which is only good enough to score 70 points.

To get the full score, use binary search on the segment ~[C_{previous}, C_{last}]~ to find ~X_R: (X_R, Y_0)~ is the only red cell in that segment that has a neighboring white cell to the right. Using this algorithm we can find all of ~X_R, X_L~ and ~Y_B~ using at most ~6 \log_2 M~ queries total. Now, ~M = X_R-X_L+1, X_C = X_L+(M-1)/2, Y_C = Y_B+(M-1)/2~.

This concludes the description of the first stage. The second stage uses the alien device only a few times to detect which of 13 possible squares has ~(X_C, Y_C)~ as the center. Just checking the color of several cells having ~X_C, X_C \pm M, X_C \pm 2M~ as x-coordinates and ~Y_C, Y_C \pm M, Y_C \pm 2M~ as y-coordinates will do the trick.