Cận dưới sau lần trúng đầu tiên

Sau lần đầu bắn trúng, cần ít nhất \(W-1\) lượt nữa để thắng vì ta còn phải bắn trúng phần còn lại của tàu.

Nếu vẫn còn nhiều hơn một vị trí tàu khả dĩ, em trai sẽ có ít nhất thêm một cơ hội trả lời "trượt". Để giới hạn số lần trượt bổ sung ở đúng một, ta gọi các ô kề với những ô đã trúng. Nếu nhận một câu "trượt", ta sẽ có một dãy ô trúng với một ô trượt ở đầu mút, nhờ đó biết chính xác vị trí tàu.

Tìm lần trúng đầu tiên

Em trai có lợi nhất khi tối đa hóa số lần trượt trước lần trúng đầu. Cậu không kiểm soát được ô ta gọi, nên chỉ có thể tiếp tục trả lời "trượt" cho tới khi ta gọi một ô chắc chắn phải trúng.

Vì vậy cần một mẫu gồm ít ô nhất sao cho mọi vị trí tàu khả dĩ đều chứa ít nhất một ô trong mẫu. Ta chọn mỗi ô thứ \(W\) trên từng hàng.

Tổng số lượt là \(R\lfloor C/W\rfloor\) cho mẫu tìm kiếm, cộng \(W-1\) lượt để trúng phần còn lại của tàu, và cộng thêm 1 nếu vị trí tàu vẫn có nhiều hơn một khả năng. Trường hợp cuối xảy ra đúng khi \(C\) không chia hết cho \(W\):

Mã tham khảo C

#include <stdio.h>

int main() {
  int T, TC, R, C, W, score;

  scanf("%d", &T);
  for (TC = 1; TC <= T; TC++) {
    scanf("%d %d %d", &R, &C, &W);

    // The R * floor(C/W) for the guess pattern.
    score = R * (C / W);

    // Plus W-1 to hit the remainder of the ship.
    score += W - 1;

    // Plus 1 more guess if there is more than one
    // possibility for the position of the ship,
    // which occurs if C is not an exact multiple of W.
    if (C % W) score++;

    printf("Case #%d: %d\n", TC, score);
  }
}

Lời giải Haskell của tos.lunar trên bảng điểm là một ví dụ khác.

Với bộ Nhỏ, cũng có thể tìm kiếm đệ quy toàn bộ cây trò chơi, mô phỏng mọi lựa chọn ở lượt của ta và của em trai — tức một lời giải minimax.

Dựa trên phân tích chính thức của Google Code Jam.