Strong Laser

It is enough to determine the number of blocks in each row independently. The column lasers are not actually needed.

Suppose a row contains $x$ blocks. If we fire a laser of strength $k$ from left to right in this row, then the following holds.

• If $x \le k$, the laser penetrates all blocks and exits the grid.
• If $x > k$, the laser stops at the $(k+1)$-th block.

Therefore, if the result is $n+1$, the number of blocks in that row is at most $k$. Otherwise, it is greater than $k$. A single experiment tells us this comparison for every row.

Since $0 \le x \le n$, we can find the number of blocks in each row by binary search. The key observation is that in one experiment, we may choose different strengths for all rows simultaneously. Thus, we can run the binary searches for all rows in parallel.

For each row $i$, maintain the possible range $[L_i, R_i]$, and set $mi{d}_i=\lfloor (L_i+R_i)$ as the strength of the row laser. The column laser strengths can be arbitrary, so we set them to .

After the experiment, update as follows.

• If the laser in row $i$ exits the grid, then the row has at most $mid_i$ blocks, so set $R_i = mid_i$.

Since $n \le 100$, each row has one of at most $101$ possible counts, so at most $7$ experiments are enough. This is within the limit of $10$.

When $L_i = R_i$ for every row, $L_i$ is the number of blocks in row . The answer is

$$\sum_{i=1}^{n} L_i$$

The time complexity is $O(n \log n)$.