Blindfolded Bullseye

Đề bài

Gary có một bức tường hình vuông lớn, cao đúng \(2 \times 10^9\) nanômét và rộng \(2 \times 10^9\) nanômét. Gary đặt một tấm bia phi tiêu trên tường. Tấm bia có dạng hình tròn và bán kính nằm trong đoạn từ A đến B nanômét, kể cả hai đầu mút. Tấm bia nằm hoàn toàn trong phạm vi bức tường, nhưng có thể tiếp xúc với các cạnh tường. Khoảng cách từ tâm bia đến mỗi cạnh tường là một số nguyên nanômét.

Gary mời cô bạn Mika đến chơi một trò thú vị. Gary bịt mắt Mika và thách cô ném một phi tiêu trúng tâm bia. Để giúp cô, mỗi khi Mika ném phi tiêu vào tường, Gary sẽ cho biết phi tiêu có trúng tấm bia hay không.

Mika không biết tấm bia nằm ở đâu trên tường, nhưng vì rất giỏi ném phi tiêu, cô có thể ném chính xác đến từng nanômét. Nói cách khác, cô có thể ngắm và ném trúng chính xác bất kỳ điểm nào có khoảng cách nguyên nanômét đến mỗi cạnh tường. Ngay sau mỗi lần ném, Gary cho cô biết phi tiêu đã trúng tâm bia, trúng một phần khác của bia, hay trượt hoàn toàn và cắm vào phần tường trống.

Bạn có thể giúp Mika ném trúng tâm bia mà không dùng quá 300 phi tiêu không?

Dữ liệu vào

Nội dung vào được cung cấp theo giao thức mô tả dưới đây.

Dữ liệu ra

Ban đầu, chương trình phải đọc một dòng chứa ba số nguyên T, A và B, lần lượt biểu thị số bộ test và giá trị nhỏ nhất, lớn nhất (đều tính cả hai đầu mút) của bán kính tấm bia, theo đơn vị nanômét. (Lưu ý rằng A và B giống nhau cho mọi bộ test trong cùng một nhóm test.) Sau đó, bạn cần xử lý T bộ test.

Ta biểu diễn các điểm mà phi tiêu có thể được ngắm tới bằng các cặp \((x, y)\), trong đó \(x\) và \(y\) là các số nguyên từ \(-10^9\) đến \(10^9\), kể cả hai đầu mút. Cặp \((x, y)\) là điểm cách cạnh trái của tường \(x + 10^9\) nanômét và cách cạnh dưới của tường \(y + 10^9\) nanômét. Vì vậy, điểm \((0, 0)\) nằm chính xác tại tâm bức tường.

Với mỗi bộ test, bán kính \(R\) và tâm \((X, Y)\) của tấm bia được chọn bí mật. Các số nguyên \(R\), \(X\) và \(Y\) được bộ chấm chủ đích lựa chọn (không phải ngẫu nhiên) trong phạm vi giới hạn. Với mỗi bộ test, bạn cần thực hiện tối đa 300 lượt trao đổi với bộ chấm. Chương trình của bạn đóng vai Mika, còn chương trình chấm đóng vai Gary. Mỗi lượt gồm việc Mika chọn vị trí ném phi tiêu và Gary cung cấp thông tin về vị trí đó.

Ở lượt thứ \(i\), trước tiên chương trình in một dòng chứa hai số nguyên \(X_i\) và \(Y_i\), cả hai đều từ \(-10^9\) đến \(10^9\), kể cả hai đầu mút. Sau đó, bộ chấm trả lời bằng một dòng chứa một trong các giá trị:

• CENTER nếu \(X_i = X\) và \(Y_i = Y\).
• HIT nếu \(0 < (X - X_i)^2 + (Y - Y_i)^2 \le R^2\).
• MISS trong mọi trường hợp còn lại.

Sau khi gửi CENTER, bộ chấm sẽ chờ lượt đầu tiên của bộ test tiếp theo, nếu có.

Nếu bạn in một dòng sai định dạng hoặc chứa giá trị ngoài phạm vi, bộ chấm trả lời WRONG. Nếu đã diễn ra 300 lượt (bao gồm 300 phản hồi) mà bạn chưa nhận CENTER, hoặc nếu từng nhận WRONG, bộ chấm sẽ kết thúc toàn bộ giao tiếp, chờ chương trình của bạn kết thúc và đưa ra Wrong Answer. Ngược lại, sau khi gửi CENTER thứ T, bộ chấm kết thúc giao tiếp, chờ chương trình kết thúc và đưa ra Correct. Nếu trong lúc chờ mà chương trình vượt giới hạn thời gian hoặc bộ nhớ, phán quyết tương ứng sẽ được đưa ra. (Các phán quyết không phải thông báo gửi tới chương trình.)

Ràng buộc

• \(1 \le \mathbf{T} \le 20\).
• \(\mathbf{A} \le R \le \mathbf{B}\).
• \(-10^9 + R \le X \le 10^9 - R\).
• \(-10^9 + R \le Y \le 10^9 - R\).

Phân nhóm

Nhóm test 1 (phán quyết hiển thị)

\(\mathbf{A} = \mathbf{B} = 10^9 - 5\).

Nhóm test 2 (phán quyết hiển thị)

\(\mathbf{A} = \mathbf{B} = 10^9 - 50\).

Nhóm test 3 (phán quyết ẩn)

\(\mathbf{A} = 10^9 / 2\).
\(\mathbf{B} = 10^9\).

Giao thức tương tác

Chương trình phải tuân thủ đầy đủ thứ tự đọc, ghi, phản hồi lỗi và yêu cầu flush được mô tả trong phần dữ liệu vào/ra và công cụ kiểm thử bên dưới.

Công cụ kiểm thử

Bạn có thể dùng công cụ kiểm thử này để kiểm thử cục bộ hoặc trên nền tảng của chúng tôi. Để kiểm thử cục bộ, bạn cần chạy công cụ song song với mã nguồn; có thể dùng trình chạy tương tác của chúng tôi. Để biết thêm thông tin, hãy đọc hướng dẫn trong chú thích của tệp ấy và xem mục Bài toán tương tác trong phần câu hỏi thường gặp.

Hướng dẫn sử dụng công cụ nằm trong các chú thích bên trong công cụ. Chúng tôi khuyến khích bạn tự bổ sung bộ test. Xin lưu ý rằng dù được thiết kế để mô phỏng hệ thống chấm, công cụ này KHÔNG PHẢI hệ thống chấm thật và có thể hoạt động khác. Nếu mã nguồn vượt qua công cụ nhưng thất bại trên bộ chấm thật, hãy kiểm tra mục Lập trình trong phần câu hỏi thường gặp để bảo đảm bạn dùng cùng trình biên dịch với chúng tôi.

Tải công cụ kiểm thử

Trình chạy tương tác đã được thay đổi sau Vòng loại năm 2020. Hãy chắc chắn tải phiên bản mới nhất.

Ví dụ

  // Dòng sau đọc 20 vào t và 999999995 vào a và b.
  t, a, b = readline_int_list()
  // Bộ chấm bí mật chọn R = 999999995 (không còn lựa chọn khác) và X = -1,
  // Y = 3 (ở đây có quyền lựa chọn). (Nhóm test 1 thực tế
  // không nhất thiết dùng các giá trị trong ví dụ này.)
  // Ta thử ném vào góc trên trái của tường, và tấm bia
  // không phủ lên điểm đó.
  printline -1000000000 1000000000 to stdout
  flush stdout
  r = readline_string()  // đọc MISS.
  // Ta thử ném vào tâm tường. Lần này trúng tấm bia,
  // nhưng không trúng tâm bia.
  printline 0 0 to stdout
  flush stdout
  r = readline_string()  // đọc HIT.
  // Ta chọn cực kỳ may mắn và ném đúng vào tâm bia.
  printline -1 3 to stdout
  flush stdout
  r = readline_string()  // đọc CENTER.
  // Bộ chấm bắt đầu bộ test tiếp theo. Nó bí mật chọn R = 999999995
  // và X = 5, Y = 5.
  // Ta vô tình ném phi tiêu ra ngoài phạm vi cho phép.
  printline -1234567890 1234567890 to stdout
  flush stdout
  r = readline_string()  // đọc WRONG.
  exit  // thoát để tránh lỗi TLE không rõ nguyên nhân.

Nguồn

Google Code Jam 2020, Vòng 1B, bài Blindfolded Bullseye.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.