Strong Laser

각 행에 있는 블록의 개수를 독립적으로 구하면 전체 블록의 개수를 알 수 있다. 사실 열 방향 레이저의 정보는 필요하지 않다.

어떤 행에 블록이 $x$개 있다고 하자. 이 행에 강도 $k$인 레이저를 왼쪽에서 오른쪽으로 발사하면 다음이 성립한다.

• $x \le k$이면 레이저는 모든 블록을 관통하고 격자 밖으로 빠져나간다.
• $x > k$이면 레이저는 $(k+1)$번째 블록에서 멈춘다.

따라서 실험 결과가 $n+1$이면 그 행의 블록 개수는 $k$ 이하이고, 그렇지 않으면 $k$보다 크다. 즉, 한 번의 실험으로 각 행에 대해 블록 개수와 $k$의 대소관계를 알 수 있다.

$0 \le x \le n$이므로 각 행의 블록 개수는 이분 탐색으로 찾을 수 있다. 중요한 점은 한 번의 실험에서 모든 행에 대해 서로 다른 강도를 동시에 설정할 수 있다는 것이다. 따라서 모든 행의 이분 탐색을 병렬로 진행할 수 있다.

각 행에 대해 현재 가능한 범위를 $[L_i, R_i]$로 두고, $mid_i = \lfloor (L_i + R_i) / 2 \rfloor$를 해당 행의 레이저 강도로 설정한다. 열 레이저의 강도는 아무 값이나 넣어도 되므로 으로 둔다.

실험 결과에 따라 다음과 같이 갱신한다.

• $i$번째 행 레이저가 격자 밖으로 빠져나갔다면, 그 행의 블록 개수는 $mid_i$ 이하이므로 $R_i = mid_i$.

$n \le 100$이므로 각 행의 범위 크기는 최대 $101$이고, 이분 탐색에는 최대 $7$번의 실험이면 충분하다. 이는 제한인 $10$번 이하이다.

모든 행에 대해 $L_i = R_i$가 되면, $L_i$가 번째 행의 블록 개수이다. 따라서 정답은

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

이다.

시간 복잡도는 한 번의 실험 결과를 처리하는 데 $O(n)$이고, 실험 횟수는 최대 $7$번이므로 $O(n \log n)$이다.